You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by so...@apache.org on 2021/07/17 15:12:22 UTC
[lucene] branch main updated: LUCENE-10016: remove fanout parameter
from nearest neighbor vector search (#210)
This is an automated email from the ASF dual-hosted git repository.
sokolov pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/main by this push:
new 9b5e233 LUCENE-10016: remove fanout parameter from nearest neighbor vector search (#210)
9b5e233 is described below
commit 9b5e23396092ea1d4cfb19c8a996b8fc118c33e8
Author: Michael Sokolov <so...@falutin.net>
AuthorDate: Sat Jul 17 11:12:15 2021 -0400
LUCENE-10016: remove fanout parameter from nearest neighbor vector search (#210)
---
.../org/apache/lucene/codecs/simpletext/SimpleTextVectorReader.java | 2 +-
lucene/core/src/java/org/apache/lucene/codecs/VectorFormat.java | 2 +-
lucene/core/src/java/org/apache/lucene/codecs/VectorReader.java | 5 +----
.../org/apache/lucene/codecs/lucene90/Lucene90HnswVectorReader.java | 4 ++--
.../java/org/apache/lucene/codecs/perfield/PerFieldVectorFormat.java | 4 ++--
lucene/core/src/java/org/apache/lucene/index/CodecReader.java | 4 ++--
.../core/src/java/org/apache/lucene/index/DocValuesLeafReader.java | 3 +--
lucene/core/src/java/org/apache/lucene/index/FilterLeafReader.java | 5 ++---
lucene/core/src/java/org/apache/lucene/index/LeafReader.java | 4 +---
lucene/core/src/java/org/apache/lucene/index/MergeReaderWrapper.java | 5 ++---
lucene/core/src/java/org/apache/lucene/index/ParallelLeafReader.java | 5 ++---
.../src/java/org/apache/lucene/index/SlowCodecReaderWrapper.java | 4 ++--
lucene/core/src/java/org/apache/lucene/index/SortingCodecReader.java | 2 +-
lucene/core/src/java/org/apache/lucene/index/VectorValues.java | 4 ++--
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraph.java | 5 -----
.../org/apache/lucene/codecs/perfield/TestPerFieldVectorFormat.java | 4 ++--
lucene/core/src/test/org/apache/lucene/index/TestKnnGraph.java | 2 +-
.../src/test/org/apache/lucene/index/TestSegmentToThreadMapping.java | 2 +-
lucene/core/src/test/org/apache/lucene/util/hnsw/KnnGraphTester.java | 2 +-
.../org/apache/lucene/search/highlight/TermVectorLeafReader.java | 2 +-
.../memory/src/java/org/apache/lucene/index/memory/MemoryIndex.java | 2 +-
.../org/apache/lucene/codecs/asserting/AssertingVectorFormat.java | 4 ++--
.../test-framework/src/java/org/apache/lucene/search/QueryUtils.java | 2 +-
23 files changed, 32 insertions(+), 46 deletions(-)
diff --git a/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextVectorReader.java b/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextVectorReader.java
index 744268b..5f779a5 100644
--- a/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextVectorReader.java
+++ b/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextVectorReader.java
@@ -143,7 +143,7 @@ public class SimpleTextVectorReader extends VectorReader {
}
@Override
- public TopDocs search(String field, float[] target, int k, int fanout) throws IOException {
+ public TopDocs search(String field, float[] target, int k) throws IOException {
throw new UnsupportedOperationException();
}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/VectorFormat.java b/lucene/core/src/java/org/apache/lucene/codecs/VectorFormat.java
index ebb9976..c43bc46 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/VectorFormat.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/VectorFormat.java
@@ -99,7 +99,7 @@ public abstract class VectorFormat implements NamedSPILoader.NamedSPI {
}
@Override
- public TopDocs search(String field, float[] target, int k, int fanout) {
+ public TopDocs search(String field, float[] target, int k) {
return TopDocsCollector.EMPTY_TOPDOCS;
}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/VectorReader.java b/lucene/core/src/java/org/apache/lucene/codecs/VectorReader.java
index 6808f9a..73e815c 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/VectorReader.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/VectorReader.java
@@ -51,12 +51,9 @@ public abstract class VectorReader implements Closeable, Accountable {
* @param field the vector field to search
* @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
* @return the k nearest neighbor documents, along with their (searchStrategy-specific) scores.
*/
- public abstract TopDocs search(String field, float[] target, int k, int fanout)
- throws IOException;
+ public abstract TopDocs search(String field, float[] target, int k) throws IOException;
/**
* Returns an instance optimized for merging. This instance may only be consumed in the thread
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90HnswVectorReader.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90HnswVectorReader.java
index b2776af..08e8694 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90HnswVectorReader.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90HnswVectorReader.java
@@ -241,7 +241,7 @@ public final class Lucene90HnswVectorReader extends VectorReader {
}
@Override
- public TopDocs search(String field, float[] target, int k, int fanout) throws IOException {
+ public TopDocs search(String field, float[] target, int k) throws IOException {
FieldEntry fieldEntry = fields.get(field);
if (fieldEntry == null || fieldEntry.dimension == 0) {
return null;
@@ -252,7 +252,7 @@ public final class Lucene90HnswVectorReader extends VectorReader {
// use a seed that is fixed for the index so we get reproducible results for the same query
final Random random = new Random(checksumSeed);
NeighborQueue results =
- HnswGraph.search(target, k, k + fanout, vectorValues, getGraphValues(fieldEntry), random);
+ HnswGraph.search(target, k, k, vectorValues, getGraphValues(fieldEntry), random);
int i = 0;
ScoreDoc[] scoreDocs = new ScoreDoc[Math.min(results.size(), k)];
boolean reversed = fieldEntry.similarityFunction.reversed;
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/perfield/PerFieldVectorFormat.java b/lucene/core/src/java/org/apache/lucene/codecs/perfield/PerFieldVectorFormat.java
index f020c5e..4913df4 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/perfield/PerFieldVectorFormat.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/perfield/PerFieldVectorFormat.java
@@ -240,12 +240,12 @@ public abstract class PerFieldVectorFormat extends VectorFormat {
}
@Override
- public TopDocs search(String field, float[] target, int k, int fanout) throws IOException {
+ public TopDocs search(String field, float[] target, int k) throws IOException {
VectorReader vectorReader = fields.get(field);
if (vectorReader == null) {
return new TopDocs(new TotalHits(0, TotalHits.Relation.EQUAL_TO), new ScoreDoc[0]);
} else {
- return vectorReader.search(field, target, k, fanout);
+ return vectorReader.search(field, target, k);
}
}
diff --git a/lucene/core/src/java/org/apache/lucene/index/CodecReader.java b/lucene/core/src/java/org/apache/lucene/index/CodecReader.java
index ab49534..1a09379 100644
--- a/lucene/core/src/java/org/apache/lucene/index/CodecReader.java
+++ b/lucene/core/src/java/org/apache/lucene/index/CodecReader.java
@@ -211,7 +211,7 @@ public abstract class CodecReader extends LeafReader {
}
@Override
- public final TopDocs searchNearestVectors(String field, float[] target, int k, int fanout)
+ public final TopDocs searchNearestVectors(String field, float[] target, int k)
throws IOException {
ensureOpen();
FieldInfo fi = getFieldInfos().fieldInfo(field);
@@ -220,7 +220,7 @@ public abstract class CodecReader extends LeafReader {
return null;
}
- return getVectorReader().search(field, target, k, fanout);
+ return getVectorReader().search(field, target, k);
}
@Override
diff --git a/lucene/core/src/java/org/apache/lucene/index/DocValuesLeafReader.java b/lucene/core/src/java/org/apache/lucene/index/DocValuesLeafReader.java
index cf4f87a..4f0ace4 100644
--- a/lucene/core/src/java/org/apache/lucene/index/DocValuesLeafReader.java
+++ b/lucene/core/src/java/org/apache/lucene/index/DocValuesLeafReader.java
@@ -53,8 +53,7 @@ abstract class DocValuesLeafReader extends LeafReader {
}
@Override
- public TopDocs searchNearestVectors(String field, float[] target, int k, int fanout)
- throws IOException {
+ public TopDocs searchNearestVectors(String field, float[] target, int k) throws IOException {
throw new UnsupportedOperationException();
}
diff --git a/lucene/core/src/java/org/apache/lucene/index/FilterLeafReader.java b/lucene/core/src/java/org/apache/lucene/index/FilterLeafReader.java
index 5d00c76..c08a559 100644
--- a/lucene/core/src/java/org/apache/lucene/index/FilterLeafReader.java
+++ b/lucene/core/src/java/org/apache/lucene/index/FilterLeafReader.java
@@ -345,9 +345,8 @@ public abstract class FilterLeafReader extends LeafReader {
}
@Override
- public TopDocs searchNearestVectors(String field, float[] target, int k, int fanout)
- throws IOException {
- return in.searchNearestVectors(field, target, k, fanout);
+ public TopDocs searchNearestVectors(String field, float[] target, int k) throws IOException {
+ return in.searchNearestVectors(field, target, k);
}
@Override
diff --git a/lucene/core/src/java/org/apache/lucene/index/LeafReader.java b/lucene/core/src/java/org/apache/lucene/index/LeafReader.java
index b5b7343..95f4176 100644
--- a/lucene/core/src/java/org/apache/lucene/index/LeafReader.java
+++ b/lucene/core/src/java/org/apache/lucene/index/LeafReader.java
@@ -222,12 +222,10 @@ public abstract class LeafReader extends IndexReader {
* @param field the vector field to search
* @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
* @return the k nearest neighbor documents, along with their (searchStrategy-specific) scores.
* @lucene.experimental
*/
- public abstract TopDocs searchNearestVectors(String field, float[] target, int k, int fanout)
+ public abstract TopDocs searchNearestVectors(String field, float[] target, int k)
throws IOException;
/**
diff --git a/lucene/core/src/java/org/apache/lucene/index/MergeReaderWrapper.java b/lucene/core/src/java/org/apache/lucene/index/MergeReaderWrapper.java
index 8926946..3d925de 100644
--- a/lucene/core/src/java/org/apache/lucene/index/MergeReaderWrapper.java
+++ b/lucene/core/src/java/org/apache/lucene/index/MergeReaderWrapper.java
@@ -209,9 +209,8 @@ class MergeReaderWrapper extends LeafReader {
}
@Override
- public TopDocs searchNearestVectors(String field, float[] target, int k, int fanout)
- throws IOException {
- return in.searchNearestVectors(field, target, k, fanout);
+ public TopDocs searchNearestVectors(String field, float[] target, int k) throws IOException {
+ return in.searchNearestVectors(field, target, k);
}
@Override
diff --git a/lucene/core/src/java/org/apache/lucene/index/ParallelLeafReader.java b/lucene/core/src/java/org/apache/lucene/index/ParallelLeafReader.java
index df73fab..6ab727b 100644
--- a/lucene/core/src/java/org/apache/lucene/index/ParallelLeafReader.java
+++ b/lucene/core/src/java/org/apache/lucene/index/ParallelLeafReader.java
@@ -398,11 +398,10 @@ public class ParallelLeafReader extends LeafReader {
}
@Override
- public TopDocs searchNearestVectors(String fieldName, float[] target, int k, int fanout)
- throws IOException {
+ public TopDocs searchNearestVectors(String fieldName, float[] target, int k) throws IOException {
ensureOpen();
LeafReader reader = fieldToReader.get(fieldName);
- return reader == null ? null : reader.searchNearestVectors(fieldName, target, k, fanout);
+ return reader == null ? null : reader.searchNearestVectors(fieldName, target, k);
}
@Override
diff --git a/lucene/core/src/java/org/apache/lucene/index/SlowCodecReaderWrapper.java b/lucene/core/src/java/org/apache/lucene/index/SlowCodecReaderWrapper.java
index bc2450c..fcd58a6 100644
--- a/lucene/core/src/java/org/apache/lucene/index/SlowCodecReaderWrapper.java
+++ b/lucene/core/src/java/org/apache/lucene/index/SlowCodecReaderWrapper.java
@@ -167,8 +167,8 @@ public final class SlowCodecReaderWrapper {
}
@Override
- public TopDocs search(String field, float[] target, int k, int fanout) throws IOException {
- return reader.searchNearestVectors(field, target, k, fanout);
+ public TopDocs search(String field, float[] target, int k) throws IOException {
+ return reader.searchNearestVectors(field, target, k);
}
@Override
diff --git a/lucene/core/src/java/org/apache/lucene/index/SortingCodecReader.java b/lucene/core/src/java/org/apache/lucene/index/SortingCodecReader.java
index baf39f1..afafaa7 100644
--- a/lucene/core/src/java/org/apache/lucene/index/SortingCodecReader.java
+++ b/lucene/core/src/java/org/apache/lucene/index/SortingCodecReader.java
@@ -315,7 +315,7 @@ public final class SortingCodecReader extends FilterCodecReader {
}
@Override
- public TopDocs search(String field, float[] target, int k, int fanout) {
+ public TopDocs search(String field, float[] target, int k) {
throw new UnsupportedOperationException();
}
diff --git a/lucene/core/src/java/org/apache/lucene/index/VectorValues.java b/lucene/core/src/java/org/apache/lucene/index/VectorValues.java
index d56d7f5..ee5f763 100644
--- a/lucene/core/src/java/org/apache/lucene/index/VectorValues.java
+++ b/lucene/core/src/java/org/apache/lucene/index/VectorValues.java
@@ -82,8 +82,8 @@ public abstract class VectorValues extends DocIdSetIterator {
public enum SimilarityFunction {
/**
- * No similarity function is provided. Note: {@link VectorReader#search(String, float[], int,
- * int)} is not supported for fields specifying this.
+ * No similarity function is provided. Note: {@link VectorReader#search(String, float[], int)}
+ * is not supported for fields specifying this.
*/
NONE,
diff --git a/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraph.java b/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraph.java
index 64e1f4d..6fb7caa 100644
--- a/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraph.java
+++ b/lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraph.java
@@ -23,7 +23,6 @@ import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
-import org.apache.lucene.codecs.VectorReader;
import org.apache.lucene.index.KnnGraphValues;
import org.apache.lucene.index.RandomAccessVectorValues;
import org.apache.lucene.index.VectorValues;
@@ -47,10 +46,6 @@ import org.apache.lucene.util.SparseFixedBitSet;
* searching the graph for each newly inserted node.
* <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><code>fanout</code> the fanout parameter of {@link VectorReader#search(String, 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.
* </ul>
*
* <p>Note: The graph may be searched by multiple threads concurrently, but updates are not
diff --git a/lucene/core/src/test/org/apache/lucene/codecs/perfield/TestPerFieldVectorFormat.java b/lucene/core/src/test/org/apache/lucene/codecs/perfield/TestPerFieldVectorFormat.java
index 0c3fe5f..21fffc7 100644
--- a/lucene/core/src/test/org/apache/lucene/codecs/perfield/TestPerFieldVectorFormat.java
+++ b/lucene/core/src/test/org/apache/lucene/codecs/perfield/TestPerFieldVectorFormat.java
@@ -106,14 +106,14 @@ public class TestPerFieldVectorFormat extends BaseVectorFormatTestCase {
.leaves()
.get(0)
.reader()
- .searchNearestVectors("field1", new float[] {1, 2, 3}, 10, 1);
+ .searchNearestVectors("field1", new float[] {1, 2, 3}, 10);
assertEquals(1, hits1.scoreDocs.length);
TopDocs hits2 =
ireader
.leaves()
.get(0)
.reader()
- .searchNearestVectors("field2", new float[] {1, 2, 3}, 10, 1);
+ .searchNearestVectors("field2", new float[] {1, 2, 3}, 10);
assertEquals(1, hits2.scoreDocs.length);
}
}
diff --git a/lucene/core/src/test/org/apache/lucene/index/TestKnnGraph.java b/lucene/core/src/test/org/apache/lucene/index/TestKnnGraph.java
index 1baa9ae..1875bd8 100644
--- a/lucene/core/src/test/org/apache/lucene/index/TestKnnGraph.java
+++ b/lucene/core/src/test/org/apache/lucene/index/TestKnnGraph.java
@@ -292,7 +292,7 @@ public class TestKnnGraph extends LuceneTestCase {
private static TopDocs doKnnSearch(IndexReader reader, float[] vector, int k) throws IOException {
TopDocs[] results = new TopDocs[reader.leaves().size()];
for (LeafReaderContext ctx : reader.leaves()) {
- results[ctx.ord] = ctx.reader().searchNearestVectors(KNN_GRAPH_FIELD, vector, k, 10);
+ results[ctx.ord] = ctx.reader().searchNearestVectors(KNN_GRAPH_FIELD, vector, k);
if (ctx.docBase > 0) {
for (ScoreDoc doc : results[ctx.ord].scoreDocs) {
doc.doc += ctx.docBase;
diff --git a/lucene/core/src/test/org/apache/lucene/index/TestSegmentToThreadMapping.java b/lucene/core/src/test/org/apache/lucene/index/TestSegmentToThreadMapping.java
index 46f6dac..74888fd 100644
--- a/lucene/core/src/test/org/apache/lucene/index/TestSegmentToThreadMapping.java
+++ b/lucene/core/src/test/org/apache/lucene/index/TestSegmentToThreadMapping.java
@@ -112,7 +112,7 @@ public class TestSegmentToThreadMapping extends LuceneTestCase {
}
@Override
- public TopDocs searchNearestVectors(String field, float[] target, int k, int fanout) {
+ public TopDocs searchNearestVectors(String field, float[] target, int k) {
return null;
}
diff --git a/lucene/core/src/test/org/apache/lucene/util/hnsw/KnnGraphTester.java b/lucene/core/src/test/org/apache/lucene/util/hnsw/KnnGraphTester.java
index bb73327..ed91db2 100644
--- a/lucene/core/src/test/org/apache/lucene/util/hnsw/KnnGraphTester.java
+++ b/lucene/core/src/test/org/apache/lucene/util/hnsw/KnnGraphTester.java
@@ -423,7 +423,7 @@ public class KnnGraphTester {
IndexReader reader, String field, float[] vector, int k, int fanout) throws IOException {
TopDocs[] results = new TopDocs[reader.leaves().size()];
for (LeafReaderContext ctx : reader.leaves()) {
- results[ctx.ord] = ctx.reader().searchNearestVectors(field, vector, k, fanout);
+ results[ctx.ord] = ctx.reader().searchNearestVectors(field, vector, k + fanout);
int docBase = ctx.docBase;
for (ScoreDoc scoreDoc : results[ctx.ord].scoreDocs) {
scoreDoc.doc += docBase;
diff --git a/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TermVectorLeafReader.java b/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TermVectorLeafReader.java
index c7f898c..a6f68cb 100644
--- a/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TermVectorLeafReader.java
+++ b/lucene/highlighter/src/java/org/apache/lucene/search/highlight/TermVectorLeafReader.java
@@ -161,7 +161,7 @@ public class TermVectorLeafReader extends LeafReader {
}
@Override
- public TopDocs searchNearestVectors(String field, float[] target, int k, int fanout) {
+ public TopDocs searchNearestVectors(String field, float[] target, int k) {
return null;
}
diff --git a/lucene/memory/src/java/org/apache/lucene/index/memory/MemoryIndex.java b/lucene/memory/src/java/org/apache/lucene/index/memory/MemoryIndex.java
index f22bc8f..b22d485 100644
--- a/lucene/memory/src/java/org/apache/lucene/index/memory/MemoryIndex.java
+++ b/lucene/memory/src/java/org/apache/lucene/index/memory/MemoryIndex.java
@@ -1373,7 +1373,7 @@ public class MemoryIndex {
}
@Override
- public TopDocs searchNearestVectors(String field, float[] target, int k, int fanout) {
+ public TopDocs searchNearestVectors(String field, float[] target, int k) {
return null;
}
diff --git a/lucene/test-framework/src/java/org/apache/lucene/codecs/asserting/AssertingVectorFormat.java b/lucene/test-framework/src/java/org/apache/lucene/codecs/asserting/AssertingVectorFormat.java
index 836ebc3..4781b64 100644
--- a/lucene/test-framework/src/java/org/apache/lucene/codecs/asserting/AssertingVectorFormat.java
+++ b/lucene/test-framework/src/java/org/apache/lucene/codecs/asserting/AssertingVectorFormat.java
@@ -99,8 +99,8 @@ public class AssertingVectorFormat extends VectorFormat {
}
@Override
- public TopDocs search(String field, float[] target, int k, int fanout) throws IOException {
- TopDocs hits = delegate.search(field, target, k, fanout);
+ public TopDocs search(String field, float[] target, int k) throws IOException {
+ TopDocs hits = delegate.search(field, target, k);
assert hits != null;
assert hits.scoreDocs.length <= k;
return hits;
diff --git a/lucene/test-framework/src/java/org/apache/lucene/search/QueryUtils.java b/lucene/test-framework/src/java/org/apache/lucene/search/QueryUtils.java
index b74066d..06fa4bc 100644
--- a/lucene/test-framework/src/java/org/apache/lucene/search/QueryUtils.java
+++ b/lucene/test-framework/src/java/org/apache/lucene/search/QueryUtils.java
@@ -216,7 +216,7 @@ public class QueryUtils {
}
@Override
- public TopDocs searchNearestVectors(String field, float[] target, int k, int fanout) {
+ public TopDocs searchNearestVectors(String field, float[] target, int k) {
return null;
}