dungba88 commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2775842169
I'm also in favor of making this the default behavior. Maybe we can let the
lambda parameter to be tuned with a reasonable default value (similar to
greediness in the current collector)
benwtrent commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2773659852
@dungba88 @msokolov
Do we know where we stand with this? I wonder if we should simply use this
to replace the current buggy behavior as fanning out to segments multiple times
w
github-actions[bot] commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2756055188
This PR has not had activity in the past 2 weeks, labeling it as stale. If
the PR is waiting for review, notify the d...@lucene.apache.org list. Thank you
for your contributi
dungba88 commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2717762620
I published the simplified version here for reference:
https://github.com/dungba88/lucene/commit/278d7c919bc6ca6e1618868a892bcf3d4970cea5
--
This is an automated message from the Apac
mikemccand commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2711223110
> > Net/net I think we ought to be adding some multithreaded test capability
to KnnGraphTester.
>
> Agreed, I think a "num_search_threads" parameter would be beneficial. Then
t
msokolov commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2710427176
right that's what it looked like to me - I was only responding to the
earlier message where you said:
> The "simplified" version now only has a slight more latency compared to
"
dungba88 commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2710473316
Ah right, sorry it was a typo :)
--
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 spec
dungba88 commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2710421110
> this is where we first search pro-rated across segments, and then if any
segment has its output queue full with competitive hits, we revisit it using
the prior hits as entry points an
msokolov commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2710392951
I think the simplified version makes the most sense -- Just confirming: this
is where we first search pro-rated across segments, and then if any segment has
its output queue full with c
dungba88 commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2709963838
Ran again with the second idea that the pro-rata rate will be based on the
active segments in the current pass instead of the whole index (called
"adaptive" in the graph). However I did
dungba88 commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2707997958
I tried the idea of stopping at second pass with the original k, but the
benchmark results look weird for all algorithms, as if it doesn't matter at
all. This is much different from the
msokolov commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2704319560
Another wrinkle here is that KnngraphTester currently does not ever run its
queries multithreaded; it does not pass an Executor when it creates
IndexSearcher. Because of that we are not
msokolov commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2705100651
> Agreed, I think a "num_search_threads" parameter would be beneficial.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub
dungba88 commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2703590078
Sorry I'm back today and will try this idea first
> - What if we just set the per-leaf k to the same as global k in the second
pass, and stop at second pass? I'm curious about the
benwtrent commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2704331980
> Net/net I think we ought to be adding some multithreaded test capability
to KnnGraphTester.
Agreed, I think a "num_search_threads" parameter would be beneficial. Then
the sear
msokolov commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2694771977
see https://github.com/mikemccand/luceneutil/pull/345 for benchmarking
support
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on t
msokolov commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2694557420
> ^ I can also help playing around with the above ideas and benchmark to see
if it helps (some cases above seems to have high reentries, ~500)
Please feel free to experiment! Not
dungba88 commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2694032117
>
- Could we readjust the pro-rata rate, not based on the whole index, but
based on the effective segments?
- What if we just set the per-leaf k to the same as global k in
dungba88 commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2693679959
> I added an additional cap on this, but then realized we are already
implicitly imposing such a limit here:
@msokolov that checks if the *previous* iteration (kInLoop / 2) has ex
msokolov commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2692810655
Also, I forgot about this comment:
> Would it make sense to cap perLeafTopK by the original k? I think k is
double on every iteration, and perLeafTopK can theoretically go over th
msokolov commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2692803205
Sorry, it took me a while to get back to this. My local setup got messed up
and somehow I was exhaustively searching entire segments! Anyway I finally got
this working again, including
msokolov commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2682565353
oh darn, in all my rebasing and force-pushing I seem to have ended up with
the wrong version, grr. I will check reflog and recover...
--
This is an automated message from the Apache G
dungba88 commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2680433274
@msokolov I didn't see the change to cap `perLeafTopK` in the [latest
commit](https://github.com/apache/lucene/pull/14226/commits/5b06e168c683e3edf36987379091357c298f0f28#diff-6bf79d1f0e
benwtrent commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2679029410
> so I rebased and removed the reuse-scores part of this since it was
conflicting with other changes and doesn't seem worth preserving
@msokolov thanks for confirming and digging
msokolov commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2678966117
There were some conflicts with other recent changes, so I rebased and
removed the reuse-scores part of this since it was conflicting with other
changes and doesn't seem worth preserving
msokolov commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2678496890
I pushed a version that re-uses scores *and* limits per-leaf topK to global
topK. The former didn't make very much difference, but the latter change did
improve things quite a bit. He
dungba88 commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2676838759
Here is the graph with various values of stdev (3, 9, 16, 25). Again both
(2) and (3) converge with a stdev value of 9, and all 3 converge at a stdev
value of 16 and greediness of 0.7.
dungba88 commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2676175583
I ran some benchmark with Cohere 768 dataset for 3 different algorithms: (1)
the baseline "greedy", (2) this PR "optimistic", and (3) with only "pro-rata".
(2) and (3) will converge wit
msokolov commented on code in PR #14226:
URL: https://github.com/apache/lucene/pull/14226#discussion_r1965419004
##
lucene/core/src/java/org/apache/lucene/search/OptimisticKnnVectorQuery.java:
##
@@ -0,0 +1,205 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under on
msokolov commented on code in PR #14226:
URL: https://github.com/apache/lucene/pull/14226#discussion_r1965415548
##
lucene/core/src/java/org/apache/lucene/search/OptimisticKnnVectorQuery.java:
##
@@ -0,0 +1,205 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under on
dungba88 commented on code in PR #14226:
URL: https://github.com/apache/lucene/pull/14226#discussion_r1964980144
##
lucene/core/src/java/org/apache/lucene/search/OptimisticKnnVectorQuery.java:
##
@@ -0,0 +1,205 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under on
msokolov commented on code in PR #14226:
URL: https://github.com/apache/lucene/pull/14226#discussion_r1962256467
##
lucene/core/src/java/org/apache/lucene/search/OptimisticKnnVectorQuery.java:
##
@@ -0,0 +1,205 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under on
dungba88 commented on code in PR #14226:
URL: https://github.com/apache/lucene/pull/14226#discussion_r1960939250
##
lucene/core/src/java/org/apache/lucene/search/OptimisticKnnVectorQuery.java:
##
@@ -0,0 +1,205 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under on
benwtrent commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2664103686
@msokolov I can provide a quick patch tomorrow against main. As I said, it
would work for stuff as it is now.
--
This is an automated message from the Apache Git Service.
To respond
msokolov commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2664096507
@benwtrent I'm curious how you managed to re-use the scores. I poked around
a little and I guess it requires some new plumbing / class casts since the API
isn't really designed for it?
msokolov commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2660180526
I don't believe 16 is "special" except in the sense that it happens to be a
sweet spot is this context. We expect that as we increase that per-segment
factor we will get increased reca
benwtrent commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2660166393
> The latency improvement from re-using scores is surprisingly large. I
would have expected costs to be dominated by newly-explored nodes, but this is
cool.
@msokolov this was o
msokolov commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2660150066
The latency improvement from re-using scores is surprisingly large. I would
have expected costs to be dominated by newly-explored nodes, but this is cool.
--
This is an automated mess
benwtrent commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2657612038
I am not 100% sure whats up with the behavior. However, I switched to `16`
(also happens to be the graph conn) instead of `3`.
Its interesting how visited is lower, but recall is
msokolov commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2657368730
also - we are not really tracking "visited" properly I think
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
msokolov commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2657373529
I think maybe what happens here is that the K controls not only how many
hits are returned from each segment, but also what the "beam width" is during
search, so we could have gotten be
msokolov commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2657365313
You can tune it by changing the magic number 3 to a bigger number. I found
that with 15 I get slight better recall and slightly lower latencies than the
baseline for my test case
--
benwtrent commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2657364706
Ah, on other thought is that we are definitely scoring every seeded entry
point twice. Once when they are gathered during initial query phase, then later
through the seeded provisionin
benwtrent commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2657348683
OK, I ran it on 8M data set with 128 segments.
Indeed it visits way fewer vectors (seemingly), and is consistent across
multiple threads.
```
recall latency(ms)
msokolov commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2657317490
Well I ran some tests, and surprisingly, I saw a significant different in
both recall and latency (decreases in both). This surprised me: I expected to
see more-or-less similar results,
msokolov commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2654826667
> But, this re-entering the graph makes me think that collectors will need
to track visitation. This way the same vector path isn't visited multiple
times. Its possible that once you en
msokolov commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2654820602
Hmm github's test run failed with:
```
gradlew :lucene:core:test --tests
"org.apache.lucene.search.TestByteVectorSimilarityQuery.testFallbackToExact"
-Ptests.jvms=1 -Ptests.jv
benwtrent commented on PR #14226:
URL: https://github.com/apache/lucene/pull/14226#issuecomment-2654818796
This is indeed interesting. I eagerly wait some of the perf numbers ;).
But, this re-entering the graph makes me think that collectors will need to
track visitation. This way the
msokolov opened a new pull request, #14226:
URL: https://github.com/apache/lucene/pull/14226
### Description
This is a WIP patch to work out an idea for Knn hit collection that is
deterministic and efficient in the sense that the number of hits collected per
leaf scales with the size
49 matches
Mail list logo
