ESG: Elastic Graphs for Range-Filtering Approximate k-Nearest Neighbor Search
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910904330747904 |
|---|---|
| author | Yang, Mingyu Li, Wentao Shen, Zhitao Xiao, Chuan Wang, Wei |
| author_facet | Yang, Mingyu Li, Wentao Shen, Zhitao Xiao, Chuan Wang, Wei |
| contents | Range-filtering approximate $k$-nearest neighbor (RFAKNN) search takes as input a vector and a numeric value, returning $k$ points from a database of $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$ nearest points to the query vector. To strike a better balance between query accuracy and efficiency, we propose novel methods that relax the strict requirement for subranges to \textit{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 \textit{two}, eliminating the $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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_04018 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | ESG: Elastic Graphs for Range-Filtering Approximate k-Nearest Neighbor Search Yang, Mingyu Li, Wentao Shen, Zhitao Xiao, Chuan Wang, Wei Databases Range-filtering approximate $k$-nearest neighbor (RFAKNN) search takes as input a vector and a numeric value, returning $k$ points from a database of $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$ nearest points to the query vector. To strike a better balance between query accuracy and efficiency, we propose novel methods that relax the strict requirement for subranges to \textit{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 \textit{two}, eliminating the $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. |
| title | ESG: Elastic Graphs for Range-Filtering Approximate k-Nearest Neighbor Search |
| topic | Databases |
| url | https://arxiv.org/abs/2504.04018 |