Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.06721 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911725783089152 |
|---|---|
| author | Xia, Wenxuan Yang, Mingyu Li, Wentao Wang, Wei |
| author_facet | Xia, Wenxuan Yang, Mingyu Li, Wentao Wang, Wei |
| contents | Approximate k-Nearest Neighbor (AKNN) search is widely used in vector databases. When vectors carry additional attributes (e.g., labels or numerical values), filtered AKNN search retrieves the nearest vectors to a query vector under attribute constraints. Most existing methods use a fixed termination condition, searching the entire index while respecting attribute filters. However, this leads to substantial redundant computations, since different queries require different amounts of search effort, and thus misses early termination opportunities for easy queries. This paper proposes a lightweight model to estimate the search cost of filtered AKNN queries and enable adaptive termination: For easy queries, the search stops early to reduce latency, while for hard queries, it continues longer to preserve accuracy. The key challenge is accurate cost prediction under attribute filters. To address this, we show that information collected during an early probing phase (e.g., attribute distributions and intermediate distance statistics) can effectively predict the overall search cost. Experiments on six real-world datasets demonstrate 1.1-3.7 speedup over state-of-the-art baselines at 95% recall, while maintaining search accuracy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_06721 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | E2E: Efficient Filtered AKNN Search via Adaptive Termination Xia, Wenxuan Yang, Mingyu Li, Wentao Wang, Wei Databases Approximate k-Nearest Neighbor (AKNN) search is widely used in vector databases. When vectors carry additional attributes (e.g., labels or numerical values), filtered AKNN search retrieves the nearest vectors to a query vector under attribute constraints. Most existing methods use a fixed termination condition, searching the entire index while respecting attribute filters. However, this leads to substantial redundant computations, since different queries require different amounts of search effort, and thus misses early termination opportunities for easy queries. This paper proposes a lightweight model to estimate the search cost of filtered AKNN queries and enable adaptive termination: For easy queries, the search stops early to reduce latency, while for hard queries, it continues longer to preserve accuracy. The key challenge is accurate cost prediction under attribute filters. To address this, we show that information collected during an early probing phase (e.g., attribute distributions and intermediate distance statistics) can effectively predict the overall search cost. Experiments on six real-world datasets demonstrate 1.1-3.7 speedup over state-of-the-art baselines at 95% recall, while maintaining search accuracy. |
| title | E2E: Efficient Filtered AKNN Search via Adaptive Termination |
| topic | Databases |
| url | https://arxiv.org/abs/2602.06721 |