Label stratified graphs speed up approximate nearest neighbor searches
Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification
Databases
Summary
Finding close matches to a query in large, complex data can be slow, especially when items have labels that must meet certain conditions. The authors propose a new way to organize data into layers based on labels, reducing unnecessary comparisons during search. Their method also uses a special hashing technique to handle many labels efficiently. Tests show their approach is faster and smaller in size than previous methods when searching with specific label rules.
What this means in practice
- •For recommendation system engineers: Accelerate content recommendations by quickly finding similar items that match user tags or interests with label-aware searches.
- •For image retrieval developers: Improve search speed for large image databases by efficiently filtering based on image annotations during nearest neighbor queries.
Authors
Ziqi Wang, Jingzhe Zhang, Shuo Shen, Wei Hu
Abstract
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.