Searches an HNSW graph to find nearest neighbors to a query vector. For more background on the
search algorithm, see HnswGraph.
<init>(org.apache.lucene.util.hnsw.NeighborQueue candidates, org.apache.lucene.util.BitSet visited)Creates a new graph searcher.
| name | type | description |
|---|---|---|
| candidates | org.apache.lucene.util.hnsw.NeighborQueue | max heap that will track the candidate nodes to explore |
| visited | org.apache.lucene.util.BitSet | bit set that will track nodes that have already been visited |
expectedVisitedNodes(int k, int graphSize)HNSW search is roughly logarithmic. This doesn't take maxConn into account, but it is a pretty good approximation.
| name | type | description |
|---|---|---|
| k | int | neighbors to find |
| graph_size | int | size of the graph |
Returns: expected number of visited nodes
search(org.apache.lucene.util.hnsw.RandomVectorScorer scorer, org.apache.lucene.search.KnnCollector knnCollector, org.apache.lucene.util.hnsw.HnswGraph graph, org.apache.lucene.util.Bits acceptOrds)See HnswGraphSearcher#search(RandomVectorScorer, KnnCollector, HnswGraph, Bits, int)
| name | type | description |
|---|---|---|
| scorer | org.apache.lucene.util.hnsw.RandomVectorScorer | the scorer to compare the query with the nodes |
| knn_collector | org.apache.lucene.search.KnnCollector | a hnsw knn collector of top knn results to be returned |
| graph | org.apache.lucene.util.hnsw.HnswGraph | the graph values. May represent the entire graph, or a level in a hierarchical graph. |
| accept_ords | org.apache.lucene.util.Bits | Bits that represents the allowed document ordinals to match, or
null if they are all allowed to match. |
search(org.apache.lucene.util.hnsw.RandomVectorScorer scorer, org.apache.lucene.search.KnnCollector knnCollector, org.apache.lucene.util.hnsw.HnswGraph graph, org.apache.lucene.util.Bits acceptOrds, int filteredDocCount)Searches the HNSW graph for the nearest neighbors of a query vector. If entry points are directly provided via the knnCollector, then the search will be initialized at those points. Otherwise, the search will discover the best entry point per the normal HNSW search algorithm.
| name | type | description |
|---|---|---|
| scorer | org.apache.lucene.util.hnsw.RandomVectorScorer | the scorer to compare the query with the nodes |
| knn_collector | org.apache.lucene.search.KnnCollector | a hnsw knn collector of top knn results to be returned |
| graph | org.apache.lucene.util.hnsw.HnswGraph | the graph values. May represent the entire graph, or a level in a hierarchical graph. |
| accept_ords | org.apache.lucene.util.Bits | Bits that represents the allowed document ordinals to match, or
null if they are all allowed to match. |
| filtered_doc_count | int | the number of docs that pass the filter |
search(org.apache.lucene.util.hnsw.RandomVectorScorer scorer, int topK, org.apache.lucene.util.hnsw.OnHeapHnswGraph graph, org.apache.lucene.util.Bits acceptOrds, int visitedLimit)Search OnHeapHnswGraph, this method is thread safe.
| name | type | description |
|---|---|---|
| scorer | org.apache.lucene.util.hnsw.RandomVectorScorer | the scorer to compare the query with the nodes |
| top_k | int | the number of nodes to be returned |
| graph | org.apache.lucene.util.hnsw.OnHeapHnswGraph | the graph values. May represent the entire graph, or a level in a hierarchical graph. |
| accept_ords | org.apache.lucene.util.Bits | Bits that represents the allowed document ordinals to match, or
null if they are all allowed to match. |
| visited_limit | int | the maximum number of nodes that the search is allowed to visit |
Returns: a set of collected vectors holding the nearest neighbors found
searchLevel(org.apache.lucene.util.hnsw.RandomVectorScorer scorer, int topK, int level, int[] eps, org.apache.lucene.util.hnsw.HnswGraph graph)Searches for the nearest neighbors of a query vector in a given level.
If the search stops early because it reaches the visited nodes limit, then the results will
be marked incomplete through NeighborQueue#incomplete().
| name | type | description |
|---|---|---|
| scorer | org.apache.lucene.util.hnsw.RandomVectorScorer | the scorer to compare the query with the nodes |
| top_k | int | the number of nearest to query results to return |
| level | int | level to search |
| eps | int[] | the entry points for search at this level expressed as level 0th ordinals |
| graph | org.apache.lucene.util.hnsw.HnswGraph | the graph values |
Returns: a set of collected vectors holding the nearest neighbors found
search(org.apache.lucene.search.KnnCollector results, org.apache.lucene.util.hnsw.RandomVectorScorer scorer, org.apache.lucene.util.hnsw.HnswGraph graph, org.apache.lucene.util.Bits acceptOrds)Search the graph for the given scorer. Gathering results in the provided collector that pass the provided acceptOrds.
| name | type | description |
|---|---|---|
| results | org.apache.lucene.search.KnnCollector | the collector to collect the results |
| scorer | org.apache.lucene.util.hnsw.RandomVectorScorer | the scorer to compare the query with the nodes |
| graph | org.apache.lucene.util.hnsw.HnswGraph | the HNSWGraph |
| accept_ords | org.apache.lucene.util.Bits | the ordinals to accept for the results |
| IOException | When accessing the vectors or graph fails | |