Elastic Index Selection for Label-Hybrid AKNN Search
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912757080653824 |
|---|---|
| author | Yang, Mingyu Xia, Wenxuan Li, Wentao Wong, Raymond Chi-Wing Wang, Wei |
| author_facet | Yang, Mingyu Xia, Wenxuan Li, Wentao Wong, Raymond Chi-Wing Wang, Wei |
| contents | Real-world vector embeddings are usually associated with extra labels, such as attributes and keywords. Many applications require the nearest neighbor search that contains specific labels, such as searching for product image embeddings restricted to a particular brand. A straightforward approach is to materialize all possible indices according to the complete query label workload. However, this leads to an exponential increase in both index space and processing time, which significantly limits scalability and efficiency. In this paper, we leverage the inclusion relationships among query label sets to construct partial indexes, enabling index sharing across queries for improved construction efficiency. We introduce \textit{elastic factor} bounds to guarantee search performance and use the greedy algorithm to select indices that meet the bounds, achieving a tradeoff between efficiency and space. Meanwhile, we also designed the algorithm to achieve the best elastic factor under a given space limitation. Experimental results on multiple real datasets demonstrate that our algorithm can achieve near-optimal search performance, achieving up to 10x-500x search efficiency speed up over state-of-the-art approaches. Our algorithm is highly versatile, since it is not constrained by index type and can seamlessly integrate with existing optimized libraries. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_03212 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Elastic Index Selection for Label-Hybrid AKNN Search Yang, Mingyu Xia, Wenxuan Li, Wentao Wong, Raymond Chi-Wing Wang, Wei Databases Real-world vector embeddings are usually associated with extra labels, such as attributes and keywords. Many applications require the nearest neighbor search that contains specific labels, such as searching for product image embeddings restricted to a particular brand. A straightforward approach is to materialize all possible indices according to the complete query label workload. However, this leads to an exponential increase in both index space and processing time, which significantly limits scalability and efficiency. In this paper, we leverage the inclusion relationships among query label sets to construct partial indexes, enabling index sharing across queries for improved construction efficiency. We introduce \textit{elastic factor} bounds to guarantee search performance and use the greedy algorithm to select indices that meet the bounds, achieving a tradeoff between efficiency and space. Meanwhile, we also designed the algorithm to achieve the best elastic factor under a given space limitation. Experimental results on multiple real datasets demonstrate that our algorithm can achieve near-optimal search performance, achieving up to 10x-500x search efficiency speed up over state-of-the-art approaches. Our algorithm is highly versatile, since it is not constrained by index type and can seamlessly integrate with existing optimized libraries. |
| title | Elastic Index Selection for Label-Hybrid AKNN Search |
| topic | Databases |
| url | https://arxiv.org/abs/2505.03212 |