LIRA: A Learning-based Query-aware Partition Framework For Large-scale ANN Search

Abstract

Approximate nearest neighbor search is fundamental in information retrieval. Previous partition-based methods enhance search efficiency by probing partial partitions, yet they face two common issues. In the query phase, a common strategy is to probe partitions based on the distance ranks of a query to partition centroids, which inevitably probes irrelevant partitions as it ignores data distribution. In the partition construction phase, all partition-based methods face the boundary problem that separates a query's nearest neighbors to multiple partitions, resulting in a long-tailed kNN distribution and degrading the optimal nprobe (i.e., the number of probing partitions). To address this gap, we propose LIRA, a LearnIng-based queRy-aware pArtition framework. Specifically, we propose a probing model to directly probe the partitions containing the kNN of a query, which can reduce probing waste and allow for query-aware probing with nprobe individually. Moreover, we incorporate the probing

Stats

• citations3
• S2 citations—
• github stars16
• HF likes0
• heat score6.98
• arxiv keyzeng2025lira

Related papers

• A Multilabel Classification Framework For Approximate Nearest Neighbor Search (2019)0.00
• Lorann: Low-rank Matrix Factorization For Approximate Nearest Neighbor Search (2024)2.26
• PM-LSH: A Fast And Accurate In-memory Framework For High-dimensional Approximate NN And Closest Pair Search (2021)8.09
• Learning Space Partitions For Nearest Neighbor Search (2019)0.00
• A Learning-to-rank Formulation Of Clustering-based Approximate Nearest Neighbor Search (2024)4.52
• Improved Space-efficient Approximate Nearest Neighbor Search Using Function Inversion (2024)0.00
• Tao: A Learning Framework For Adaptive Nearest Neighbor Search Using Static Features Only (2021)0.00
• SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search (2021)0.00