msokolov commented on a change in pull request #2022: URL: https://github.com/apache/lucene-solr/pull/2022#discussion_r519004731
########## File path: lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraph.java ########## @@ -0,0 +1,235 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.lucene.util.hnsw; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.Comparator; +import java.util.HashSet; +import java.util.List; +import java.util.Random; +import java.util.Set; +import java.util.TreeSet; + +import org.apache.lucene.index.KnnGraphValues; +import org.apache.lucene.index.VectorValues; + +import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS; +import static org.apache.lucene.util.VectorUtil.dotProduct; +import static org.apache.lucene.util.VectorUtil.squareDistance; + +/** + * Navigable Small-world graph. Provides efficient approximate nearest neighbor + * search for high dimensional vectors. See <a href="https://doi.org/10.1016/j.is.2013.10.006";>Approximate nearest + * neighbor algorithm based on navigable small world graphs [2014]</a> and <a + * href="https://arxiv.org/abs/1603.09320";>this paper [2018]</a> for details. + * + * This implementation is actually more like the one in the same authors' earlier 2014 paper in that + * there is no hierarchy (just one layer), and no fanout restriction on the graph: nodes are allowed to accumulate + * an unbounded number of outbound links, but it does incorporate some of the innovations of the later paper, like + * using a priority queue to perform a beam search while traversing the graph. The nomenclature is a bit different + * here from what's used in those papers: + * + * <h3>Hyperparameters</h3> + * <ul> + * <li><code>numSeed</code> is the equivalent of <code>m</code> in the 2012 paper; it controls the number of random entry points to sample.</li> + * <li><code>beamWidth</code> in {@link HnswGraphBuilder} has the same meaning as <code>efConst</code> in the 2016 paper. It is the number of + * nearest neighbor candidates to track while searching the graph for each newly inserted node.</li> + * <li><code>maxConn</code> has the same meaning as <code>M</code> in the later paper; it controls how many of the <code>efConst</code> neighbors are + * connected to the new node</li> + * <li><code>fanout</code> the fanout parameter of {@link VectorValues#search(float[], int, int)} + * is used to control the values of <code>numSeed</code> and <code>topK</code> that are passed to this API. + * Thus <code>fanout</code> is like a combination of <code>ef</code> (search beam width) from the 2016 paper and <code>m</code> from the 2014 paper. + * </li> + * </ul> + * + * <p>Note: The graph may be searched by multiple threads concurrently, but updates are not thread-safe. Also note: there is no notion of + * deletions. Document searching built on top of this must do its own deletion-filtering.</p> + */ +public final class HnswGraph { + + // each entry lists the neighbors of a node, in node order + private final List<List<Neighbor>> graph; + + HnswGraph() { Review comment: Right, we do not instantiate this class at search time, although we do use the static `search` method, which only relies on the abstract vector and graph values. Heap usage is quite high! It will scale with graph fanout * number of vectors. For each node, we store a PriorityQueue of Neighbor objects; each Neighbor has an int node id and a float score. I think for 1M vectors, with fanout of 64, we'll see around 1.5G heap usage, with lots of tiny objects on the heap during flush/merge. This can be dramatically reduced by eliminating the Neighbor objects in favor of parallel arrays, and the priority queues can then store int ordinals rather than object pointers, but I think that can be a fast follow? ---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org
