Google Git
Sign in
apache / lucene / 65d30ca1af15ecbec28618338aebe097e5516afc
commit65d30ca1af15ecbec28618338aebe097e5516afc[log] [tgz]
authorKaival Parikh <46070017+kaivalnp@users.noreply.github.com>Fri Dec 01 23:32:00 2023 +0530
committerGitHub <noreply@github.com>Fri Dec 01 13:02:00 2023 -0500
treeced157ddee64e09e2ef934a509cc839abfbeca6e
parent0e96b9cd8c1267acee02684bcac5be89d60b3bf4 [diff]
Prevent extra similarity computation for single-level graphs (#12866)

### Description

[`#findBestEntryPoint`](https://github.com/apache/lucene/blob/4bc7850465dfac9dc0638d9ee782007883869ffe/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphSearcher.java#L151) is used to determine the entry point for the last level of HNSW search

It finds the single best-scoring node from [all upper levels](https://github.com/apache/lucene/blob/4bc7850465dfac9dc0638d9ee782007883869ffe/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphSearcher.java#L159) - but performs an [unnecessary computation](https://github.com/apache/lucene/blob/4bc7850465dfac9dc0638d9ee782007883869ffe/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphSearcher.java#L157) (along with [recording one visited node](https://github.com/apache/lucene/blob/4bc7850465dfac9dc0638d9ee782007883869ffe/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraphSearcher.java#L154)) when the graph just has 1 level (so the entry node is just the overall graph's entry node)

Also added a test to demonstrate this (fails without the changes in PR) -- where we visit `graph.size() + 1` nodes when the `topK` is high (should be a maximum of `graph.size()`)

---------

Co-authored-by: Kaival Parikh <kaivalp2000@gmail.com>
4 files changed
tree: ced157ddee64e09e2ef934a509cc839abfbeca6e
  1. .github/
  2. buildSrc/
  3. dev-docs/
  4. dev-tools/
  5. gradle/
  6. help/
  7. lucene/
  8. .asf.yaml
  9. .dir-locals.el
  10. .git-blame-ignore-revs
  11. .gitattributes
  12. .gitignore
  13. .hgignore
  14. .lift.toml
  15. build.gradle
  16. CONTRIBUTING.md
  17. gradlew
  18. gradlew.bat
  19. LICENSE.txt
  20. NOTICE.txt
  21. README.md
  22. settings.gradle
  23. versions.lock
  24. versions.props
README.md

Apache Lucene

Lucene Logo

Apache Lucene is a high-performance, full-featured text search engine library written in Java.

Build Status

Online Documentation

This README file only contains basic setup instructions. For more comprehensive documentation, visit:

Building

Basic steps:

  1. Install OpenJDK 17 or 18.
  2. Clone Lucene's git repository (or download the source distribution).
  3. Run gradle launcher script (gradlew).

We‘ll assume that you know how to get and set up the JDK - if you don’t, then we suggest starting at https://jdk.java.net/ and learning more about Java, before returning to this README.

See Contributing Guide for details.

Contributing

Bug fixes, improvements and new features are always welcome! Please review the Contributing to Lucene Guide for information on contributing.

Discussion and Support