Metraipolis › archive › dc_2df356344942
Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification — arXiv:2609.15058
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.15058
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T02:15:14.637Z
- SHA-256 of the archived text
308c65ed66d566705ca34ed308edd888036776ad056fb16b36ea0c8058c0bf4a- Stable URL of this page
https://metraipolis.com/documento/dc_2df356344942
How to cite
Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification — arXiv:2609.15058 — arXiv (en), https://arxiv.org/abs/2609.15058 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2df356344942 (Metraipolis archive dc_2df356344942, sha256 308c65ed66d566705ca34ed308edd888036776ad056fb16b36ea0c8058c0bf4a)
BibTeX
@misc{dc2df356344942,
title = {Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification — arXiv:2609.15058},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.15058},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2df356344942; sha256 308c65ed66d566705ca34ed308edd888036776ad056fb16b36ea0c8058c0bf4a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.15058. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Approximate nearest neighbor search (ANNS) retrieves the most similar vectors to a query vector in high-dimensional space. Label-filtering ANNS (LFANNS) extends ANNS with a label filter that the labels of base vectors must satisfy a set relation (e.g., equality, containment, or overlap) with the query labels. Existing LFANNS indices suffer from inconsistent performance across different filter types and degraded scalability under varying label scale and distribution. In this paper, we define label-stratified similarity graph (LSSG), where edges connect neighboring vectors whose label sets fall within stratified similarity thresholds. To implement LSSG efficiently, we design an incremental insertion algorithm to prune redundant edges in both vector and label spaces, and leverage a MinHash structure to ensure scalability for large-scale labels. We analyze stepwise probabilities under explicit label models and explain why stricter label tiers reduce ineffective in-filtering expansions. Benchmark experiments show that LSSG achieves ideal optimality for equality queries, and 1.06x-92.9x and 1.08x-84.1x faster than the best competing index for containment and overlap, respectively, in query speed with identical accuracy and 0.35x index size. Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-09-15 in cs.DB). Categorie arXiv: Databases (cs.DB). Pagina del lavoro: https://arxiv.org/abs/2609.15058 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T01:53:21.335Z dalla pagina https://arxiv.org/catchup/cs.DB/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).