ESG: Elastic Graphs for Range-Filtering Approximate k k -Nearest Neighbor Search
Mingyu Yang 1,2 , Wentao Li 3 , Zhitao Shen 4 , Chuan Xiao 5 , Wei Wang 1,2 · 2025
Read ESG: Elastic Graphs for Range-Filtering Approximate k k -Nearest Neighbor Search by Mingyu Yang 1,2 , Wentao Li 3 , Zhitao Shen 4 , Chuan Xiao 5 , Wei Wang 1,2 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-04018.txt.
Introduction
Mingyu Yang and co-authors speed up a search task that joins closeness in vector space with a numeric range filter. Their 2025 paper deals with range-filtering approximate nearest neighbor search: given a query vector and a range, return the k stored points inside the range that lie closest to the query. Past methods pay a growing overhead as the database grows.
Their insight is elastic: letting a few out of range points into the search does not break its bounded cost. With that relaxation, the needed subranges drop to at most two. On real datasets the methods ran one and a half to six times faster than leading rivals, while keeping accuracy high.
Catalog record
| CREATOR | Mingyu Yang 1,2 , Wentao Li 3 , Zhitao Shen 4 , Chuan Xiao 5 , Wei Wang 1,2 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 72 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-04018
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
ESG: Elastic Graphs for Range-Filtering Approximate k k -Nearest Neighbor Search Mingyu Yang 1,2 , Wentao Li 3 , Zhitao Shen 4 , Chuan Xiao 5 , Wei Wang 1,2 Abstract . Range-filtering approximate k k -nearest neighbor (RFAKNN) search takes as input a vector and a numeric value, returning k k points from a database of N N high-dimensional points. The returned points must satisfy two criteria: their numeric values must lie within the specified query range, and they must be approximately the k k nearest points to the query vector. A straightforward approach to processing RFAKNN queries is to filter out points outside the query range and then perform a search on the remaining in-range points. While indexing can speed up this process, ensuring correctness would require indexing all possible O ( N 2 ) O(N^{2}) query ranges, which is infeasible due to severe storage constraints. Lossy compression techniques have been explored to create compact indexes for these ranges, but they often compromise query accuracy because of the inherent loss of information. To address these challenges, existing methods index only a subset of ranges, organized within a segment tree. At query time, the query range is decomposed into multiple subranges stored in the segment tree. Although these methods improve accuracy, they introduce significant query overhead since processing a single query requires combining indexes from O ( log N ) O(\log N) subranges. To strike a better balance between query accuracy and efficiency, we propose novel methods that relax the strict requirement for subranges to exactly match the query range. This elastic relaxation is based on a theoretical insight: allowing the controlled inclusion of out-of-range points during the search does not compromise the bounded complexity of the search process. Building on this insight, we prove that our methods reduce the number of required subranges to at most two , eliminating the O ( log N ) O(\log N) query overhead inherent in existing methods. Extensive experiments on real-world datasets demonstrate that our proposed methods outperform state-of-the-art approaches, achieving performance improvements of 1.5x to 6x while maintaining high accuracy. 1. Introduction The problem of k -nearest neighbor (KNN) search in high-dimensional spaces has received increasing attention, especially with recent advancements in deep learning and large language models ( Lewis et al. 2020 ) . Due to the curse of dimensionality ( Indyk and Motwani 1998 ) , finding the exact k nearest neighbors often becomes computationally demanding. As a result, the variant known as approximate k -nearest neighbor (AKNN) search has been extensively studied. Numerous methods have been proposed for AKNN search ( Gionis et al. 1999 ; Datar et al. 2004 ; Huang et al. 2015 ; Zheng et al. 2020 ; Sun et al. 2014 ; Gan et al. 2012 ; Raginsky and Lazebnik 2009 ; Ge et al. 2014 ; André et al. 2015 ; Kalantidis and Avrithis 2014 ; Wang and Deng 2020 ; Gao and Long 2024 ; Beygelzimer et al. 2006 ; Blalock and Guttag 2017 ; Gupta et al. 2022 ; Guo et al. 2016 ; Yue et al. 2023 ; Jégou et al. 2011 ; Babenko and Lempitsky 2015 ) , among which graph-based approaches ( Harwood and Drummond 2016 ; Lu et al. 2021 ; Peng et al. 2023 ; Fu et al. 2019 ; Fu et al. 2022 ; Jayaram Subramanya et al. 2019 ) have emerged as particularly effective. Graph-based methods, such as {\mathsf{HNSW}} ( Malkov and Yashunin 2020 ) , build graphs as the index for AKNN search and demonstrate superior performance compared to alternative methods. Driven by the demands of applications, Range-Filtering Approximate k -Nearest Neighbors (RFAKNN) search extends the traditional AKNN search problem by incorporating additional numerical constraints. In such scenarios, data points typically consist of two components: a vector and an associated numerical attribute. Formally, given a database \mathcal{D} of N data points, where each point v_{i} is associated with a numerical value 1 1 1 We apply the re-ranking strategy in ( Zuo et al. 2024 ) to map the attribute value of a point v_{i} to its position i in \mathcal{D} . Thus, both the cardinality of \mathcal{D} and the range are N=|\mathcal{D}| . i , an RFAKNN query takes as input a vector q and a range [l_{q},r_{q}] , and returns k points as the result. These points should satisfy two conditions: their numerical values must lie within the query range [l_{q},r_{q}] , and they must be approximately the k closest points to the query vector q . By introducing a range as a filter to exclude data points outside the specified range, RFAKNN enables more targeted and meaningful nearest-neighbor retrieval. For example, in e-commerce applications, each product typically has a price attribute. By specifying a price range during an AKNN search, users can filter out products beyond their budget, improving the relevance of search results. Similarly, RFAKNN has broad applicability in Retrieval-Augmented Generation (RAG) ( Engels et al. 2024 ) , vehicle search ( Zuo et al. 2024 ) , and face recognition ( Wei et al. 2020 ) . Table 1 . We compare our methods with existing solutions. Among them, {\mathsf{PreFiltering}} , {\mathsf{PostFiltering}} , and {\mathsf{SuperPostFiltering}} primarily focus on search within a single graph index. {\mathsf{SeRF}} ( Zuo et al. 2024 ) is a compression-based method, while {\mathsf{SegmentTree}} ( Engels et al. 2024 ) and {\mathsf{IRANGE}} ( Xu et al. 2024 ) are reconstruction-based approaches. The Scalability and Query Efficiency are confirmed by our experimental study. Theoretical Guarantee indicates whether the methods provide query time complexity analysis. Adaptability assesses if the methods can extend beyond graph-based indexing (for each range). Additionally, Half-Bounded RFAKNN is to check whether tailored methods are designed specifically for this type of query. Feature {\mathsf{ESG}} (Our) {\mathsf{PreFiltering}} {\mathsf{PostFiltering}} {\mathsf{SuperPostFiltering}} ( Engels et al. 2024 ) {\mathsf{SeRF}} ( Zuo et al. 2024 ) {\mathsf{SegmentTree}} ( Engels et al. 2024 ) {\mathsf{IRANGE}} ( Xu et al. 2024 ) Scalability \star\star\star \star\star\star \star\star\star \star\star \star\star\star \star\star\star \star\star Query Efficiency \star\star\star \star \star \star\star\star \star\star \star\star \star\star\star Theoretical Guarantee ✓ \times \times \times \times ✓ \times Adaptation ✓ ✓ ✓ ✓ \times ✓ \times Half-Bounded RFAKNN ✓ \times \times \times ✓ \times \times Search Principles. To process RFAKNN queries, adopting a graph index (such as {\mathsf{HNSW}} ) originally designed for AKNN search is a straightforward approach. The main challenge lies in handling the additional query ranges and two commonly used principles for this are: 1) {\mathsf{PreFiltering}} , which filters out points whose numeric values fall outside the query range. Since it ensures that only in-range points are included, the resulting graph index may become less-connected after removing out-of-range points. Conducting RFAKNN searches on such a sparse graph often leads to reduced query accuracy. 2) {\mathsf{PostFiltering}} , which retains all points, including those that fall outside the query range. It progressively identifies points near the query point but only adds a point to the result if its numeric values fall within the query range. Although {\mathsf{PostFiltering}} avoids the sparsity issue, it can operate on a graph index containing a large number of out-of-range points, which can slow down query processing. While further optimizations such as