msokolov commented on a change in pull request #2022:
URL: https://github.com/apache/lucene-solr/pull/2022#discussion_r518997811
##########
File path: lucene/core/src/java/org/apache/lucene/index/VectorValues.java
##########
@@ -74,6 +74,18 @@ public BytesRef binaryValue() throws IOException {
throw new UnsupportedOperationException();
}
+ /**
+ * Return the k nearest neighbor documents as determined by comparison of
their vector values
+ * for this field, to the given vector, by the field's search strategy. If
the search strategy is
+ * reversed, lower values indicate nearer vectors, otherwise higher scores
indicate nearer
+ * vectors. Unlike relevance scores, vector scores may be negative.
+ * @param target the vector-valued query
+ * @param k the number of docs to return
+ * @param fanout control the accuracy/speed tradeoff - larger values give
better recall at higher cost
Review comment:
Yeah this probably needs to be field level. Different strokes for
different collections of vectors. I'm not sure how to expose since the
parameters will be different for different ANN implementations. Might be a good
use case for generic IndexedField.attributes?
##########
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
Review comment:
Yes, although this class is agnostic as to the interpretation of these
nodes. They could just as well be docIds, or social security numbers. But yeah,
the only usage is as you describe, so I'll add a note to the javadoc.
----------------------------------------------------------------
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
