lizhiyuell commented on PR #16526: URL: https://github.com/apache/lucene/pull/16526#issuecomment-5790781985
> The idea makes sense. I don't have time for a deep review :(. > > I would prefer that this is an evolution of the HnswFiltered directly, instead of yet another way to do filtered HNSW search. Its experimental, and not the default. I think improving the algorithm is fine. > > One thing that troubles me, is that your benchmarks contradict ones I did. I found that Lucene's ACORN provided much better recall and latency curve vs. the plain "sweep" over a bunch of data sets, and yet your results indicate ACORN is the worst choice, for almost everything. > > Another interesting result I don't understand: the "positive correlation" (if it means that filter acceptance correlates positively with the nearest neighbors), I would expect almost all the filtered criteria to be much closer together as this would mean exploration over the filtered set would also more likely mean exploration of the nearest neighbors. Thanks a lot for the suggestions, and sorry to bother you. I did some more tests over the past week and have a few updates: * **Direct evolution of `HnswFiltered`:** I changed the implementation so that PathSeer is now directly based on `HnswFiltered` (commit https://github.com/apache/lucene/pull/16526/commits/ca956301af6161bd2b39056288350b5b8aeadbd5). The `filteredSearchThreshold` in `Hnsw` initialization is used to choose between Sweeping and PathSeer. I'm not sure if this is what you had in mind, so please let me know. * **ACORN performance:** We updated `luceneutil` to the latest version (commit https://github.com/mikemccand/luceneutil/commit/861b67084fb1ef1feef8ef32dd90248105338d1e) and reran the experiments with the previous implementation (commit https://github.com/apache/lucene/pull/16526/commits/52824941c60899a379b3568960a8fa57f8b70903). We also measured the average distance computations per query using Lucene's `visitedCount`, and tested different SIMD instruction sets, from AVX-512 to SSE-128. The result is still the same: for the uniformly distributed filter attributes generated by `luceneutil`, ACORN is slower than Sweeping for most selectivities in our experimental setup. At the same recall, ACORN only reduces distance computations when selectivity is around 0.1 or lower. At higher selectivities, it actually does more distance computations than Sweeping. Changing the SIMD instruction set changes the absolute latency, but not this trend. We do see ACORN outperforming Sweeping on negatively correlated BEIR workloads. If possible, I'd like to get more information about any representative workloads for further tests. * **Positive correlation:** Yes, here positive correlation means the filter attribute is correlated with the vector space. We build this workload from BEIR in a similar way to [this blog](https://weaviate.io/blog/speed-up-filtered-vector-search): documents from different BEIR datasets are merged together, and the source dataset is used as the filter label. For a positive-correlation workload, the query comes from dataset A and we also filter for dataset A. So vectors around the query are more likely to pass the filter, but not all nearby vectors belong to A. The local selectivity is therefore higher, but still below 1, so different filtered search methods can still show some performance difference. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
