jimczi commented on code in PR #12962:
URL: https://github.com/apache/lucene/pull/12962#discussion_r1452096401
##########
lucene/core/src/java/org/apache/lucene/index/LeafReader.java:
##########
@@ -240,11 +241,19 @@ public final PostingsEnum postings(Term term) throws
IOException {
* @param acceptDocs {@link Bits} that represents the allowed documents to
match, or {@code null}
* if they are all allowed to match.
* @param visitedLimit the maximum number of nodes that the search is
allowed to visit
+ * @param globalScoreQueue the global score queue used to track the top
scores collected across
+ * all leaves
* @return the k nearest neighbor documents, along with their
(searchStrategy-specific) scores.
* @lucene.experimental
*/
public final TopDocs searchNearestVectors(
- String field, float[] target, int k, Bits acceptDocs, int visitedLimit)
throws IOException {
+ String field,
+ float[] target,
+ int k,
+ Bits acceptDocs,
+ int visitedLimit,
+ BlockingFloatHeap globalScoreQueue)
Review Comment:
I wonder if we could introduce a `CollectorManager` similar to what we have
for `TopDocs`? This global queue should be an implementation detail of the
collector imo.
##########
lucene/core/src/java/org/apache/lucene/search/TopKnnCollector.java:
##########
@@ -27,25 +29,72 @@
*/
public final class TopKnnCollector extends AbstractKnnCollector {
+ // greediness of globally non-competitive search: [0,1]
+ private static final float DEFAULT_GREEDINESS = 0.9f;
private final NeighborQueue queue;
+ private final float greediness;
+ private final FloatHeap nonCompetitiveQueue;
+ private final FloatHeap updatesQueue;
+ private final int interval = 0x3ff; // 1023
Review Comment:
This interval is important since we need to ensure that we don't use the
global queue too early. Did you check with different values? I'd expect that a
smaller interval could affect recall.
##########
lucene/core/src/java/org/apache/lucene/search/TopKnnCollector.java:
##########
@@ -27,25 +29,72 @@
*/
public final class TopKnnCollector extends AbstractKnnCollector {
+ // greediness of globally non-competitive search: [0,1]
+ private static final float DEFAULT_GREEDINESS = 0.9f;
private final NeighborQueue queue;
+ private final float greediness;
+ private final FloatHeap nonCompetitiveQueue;
+ private final FloatHeap updatesQueue;
+ private final int interval = 0x3ff; // 1023
Review Comment:
It's also important to check the order of execution. For instance what
happens if all segments are executed serially (rather than in parallel), does
it changes the recall?
##########
lucene/core/src/java/org/apache/lucene/search/TopKnnCollector.java:
##########
@@ -27,25 +29,72 @@
*/
public final class TopKnnCollector extends AbstractKnnCollector {
+ // greediness of globally non-competitive search: [0,1]
+ private static final float DEFAULT_GREEDINESS = 0.9f;
private final NeighborQueue queue;
+ private final float greediness;
+ private final FloatHeap nonCompetitiveQueue;
+ private final FloatHeap updatesQueue;
+ private final int interval = 0x3ff; // 1023
+ private final BlockingFloatHeap globalSimilarityQueue;
+ private boolean kResultsCollected = false;
+ private float cachedGlobalMinSim = Float.NEGATIVE_INFINITY;
/**
* @param k the number of neighbors to collect
* @param visitLimit how many vector nodes the results are allowed to visit
*/
- public TopKnnCollector(int k, int visitLimit) {
+ public TopKnnCollector(int k, int visitLimit, BlockingFloatHeap
globalSimilarityQueue) {
super(k, visitLimit);
+ this.greediness = DEFAULT_GREEDINESS;
this.queue = new NeighborQueue(k, false);
+ this.globalSimilarityQueue = globalSimilarityQueue;
+
+ if (globalSimilarityQueue == null) {
+ this.nonCompetitiveQueue = null;
+ this.updatesQueue = null;
+ } else {
+ this.nonCompetitiveQueue = new FloatHeap(Math.max(1, Math.round((1 -
greediness) * k)));
+ this.updatesQueue = new FloatHeap(k);
+ }
}
@Override
public boolean collect(int docId, float similarity) {
- return queue.insertWithOverflow(docId, similarity);
+ boolean localSimUpdated = queue.insertWithOverflow(docId, similarity);
+ boolean firstKResultsCollected = (kResultsCollected == false &&
queue.size() == k());
+ if (firstKResultsCollected) {
+ kResultsCollected = true;
+ }
+
+ boolean globalSimUpdated = false;
+ if (globalSimilarityQueue != null) {
+ updatesQueue.offer(similarity);
+ globalSimUpdated = nonCompetitiveQueue.offer(similarity);
+
+ if (kResultsCollected) {
+ // as we've collected k results, we can start do periodic updates with
the global queue
+ if (firstKResultsCollected || (visitedCount & interval) == 0) {
+ cachedGlobalMinSim =
globalSimilarityQueue.offer(updatesQueue.getHeap());
Review Comment:
This way of updating the global queue periodically doesn't bring much if `k`
is close to the size of the queue. For instance if `k` is 1000, we only save 24
updates with this strategy. That's fine I guess especially considering that the
interval is not only to save concurrent update in the queue but also to ensure
that we are far enough in the walk of the graph.
--
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.
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
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
