lizhiyuell opened a new pull request, #16526: URL: https://github.com/apache/lucene/pull/16526
### Description This PR introduces [PathSeer](https://dl.acm.org/doi/10.1145/3802098), an adaptive filtered HNSW search strategy, for Lucene's filtered HNSW search. #### Motivation Existing filtered HNSW strategies can perform very differently across workloads. In particular, the best strategy may change with filter selectivity and query-filter correlation, making it difficult for a fixed strategy to perform consistently well across different filtering regimes. PathSeer aims to improve this adaptivity and provide a more robust recall-performance trade-off across workloads. #### Approach PathSeer combines **distance-first-then-filter** traversal with **filter-first-then-distance** traversal. The key idea is to preserve the connectivity and navigability of the search subgraph while opportunistically avoiding unnecessary vector similarity computations. Compared with the original PathSeer design described in the paper, this PR adapts the algorithm for better compatibility with Lucene's existing HNSW index. It does not modify the graph structure or on-disk index format; instead, **two-hop neighbors**, similar to those used by ACORN, are used in place of the original expanding-zone neighbors. Since two-hop neighbors may be relatively far from the query, this version only explores them while the candidate heap is not yet full. In addition, when traversing neighbors that do not satisfy the filter, PathSeer uses only filter-first-then-distance traversal for their subsequent expansion. This helps limit unnecessary distance computations in attribute-correlated workloads. #### Benchmark We evaluated PathSeer in two benchmark settings: the standard **luceneutil Cohere v3 Wikipedia workload**, covering different filter selectivities and search-effort configurations, and **BEIR-based workloads**, covering different filter selectivities and query-filter correlation settings. Selected results from the BEIR-based workloads are shown below, and the complete results are provided in the attached benchmark report. <img width="3276" height="978" alt="tput_recall_BEIR_500000_0 1_NEG" src="https://github.com/user-attachments/assets/f7ba17c7-86fd-4164-ba05-925faa129302"; /> <img width="3279" height="978" alt="tput_recall_BEIR_500000_0 1_POS" src="https://github.com/user-attachments/assets/eb11f89b-d7d2-4e1a-9a7e-66a230c0ebb3"; /> <img width="3276" height="978" alt="tput_recall_BEIR_500000_0 4_NEG" src="https://github.com/user-attachments/assets/12d5cabc-1d53-4ecd-a505-f6b85b875b4a"; /> <img width="3279" height="978" alt="tput_recall_BEIR_500000_0 4_POS" src="https://github.com/user-attachments/assets/9989b95f-876d-4e14-9667-4b27ca631749"; /> The results show that PathSeer provides a more robust recall-performance trade-off across the tested filtering regimes. Across the Cohere benchmark, PathSeer improves average throughput over all baselines by 35.19% at the 90% recall target and 39.45% at the 95% recall target. Across the BEIR workloads, the corresponding average improvements are 96.60% and 87.34%. **Full benchmark report:** [pathseer_lucene_benchmark_report.pdf](https://github.com/user-attachments/files/31212091/pathseer_lucene_benchmark_report.pdf) -- 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]
