Conceptio › Archive › arXiv CS

arXiv CSopen access

Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification

· arxiv_cs

arXiv CS · Papers · License: Open Access

Open Source ↗Direct PDF ↓

data-management databases storage

databases, sql, data management, storage

arXiv:2609.15058v1 [cs.DB] 14 Sep 2026

Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification Ziqi Wang

Jingzhe Zhang

State Key Laboratory for Novel Software Technology Nanjing University, China [email protected]

Shuo Shen

Wei Hu∗

State Key Laboratory for Novel Software Technology Nanjing University, China [email protected]

State Key Laboratory for Novel Software Technology National Institute of Healthcare Data Science Nanjing University, China [email protected]

Abstract Approximate nearest neighbor search (ANNS) retrieves the most similar vectors to a query vector in high-dimensional space. Labelfiltering 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.

CCS Concepts • Information systems → Nearest-neighbor search; Specialized information retrieval.

Keywords approximate nearest neighbor search, graph-based index, vector database, label set similarity ∗

Corresponding author

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. SIGMOD ’27, Huntington Beach, CA © 2026 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-1-4503-XXXX-X/2018/06 https://doi.org/XXXXXXX.XXXXXXX

ACM Reference Format: Ziqi Wang, Jingzhe Zhang, Shuo Shen, and Wei Hu. 2026. Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification. In Proceedings of the ACM SIGMOD/PODS International Conference on Management of Data (SIGMOD ’27). ACM, New York, NY, USA, 21 pages. https://doi.org/XXXXXXX.XXXXXXX

Introduction

Approximate nearest neighbor search (ANNS) is a fundamental operation for semantic query answering, used in vector database management systems (VDBMS) [23, 39, 57, 63, 70], search engines [6, 29, 59, 68], retrieval-augmented generation (RAG) applications [8, 9, 15], etc. Enormous high-dimensional vectors are generated from texts, images, and audios by modern embedding models [43, 46, 56]. Given a query vector, rather than scanning all base vectors to obtain the exact 𝑘 nearest neighbors, ANNS indices enable to retrieve most of these neighbors with significantly lower latency. Particularly, graph-based ANNS indices [11, 12, 16, 34, 45, 65] are popular for their fast query speed and high accuracy. With growing demands for customized queries, label-filtering ANNS (LFANNS) has become prominent for semantic-constrained vector search beyond basic similarity retrieval [40, 58, 59, 66]. Label set predicates are commonly organized around three canonical positive semantics [1, 5]. For example, in a medical image retrieval system [2], a physician may query a CT image labeled “lung” and “nodule”. An equality filter strictly matches images labeled only “lung” and “nodule”, excluding cases with additional findings or comorbidities. This filter is useful for scenarios requiring precise and controlled subsets [19]. A containment filter retrieves images whose label sets include both query terms (e.g., also annotated with “CT”, “solid”, or “cancer”), ensuring a comprehensive coverage of relevant cases. An overlap filter returns images sharing at least one query label (e.g., lung-related images without nodules, or nodule images from other regions), supporting association analysis. There are three mainstream solutions for LFANNS [30]. (1) Pre– filtering scans all data objects and only computes vector similarity between the query vector and the filtered subset. Since no vector index is constructed for the subset, the linear scan becomes inefficient when the subset is large (e.g., tens of thousands of vectors). (2) Post-filtering operates on an ANN index constructed over the entire vector dataset. It first retrieves the most similar vectors using

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA

.$ ={1,8}

!! !#

." ={1,3,6}

.& ={4,6,9}

!!)

.# ={1,3,6,8}

!!" !!

!!! !+

! = 1: $! ∈ 0, 1.00

!! !#

!$ !*

!' !(

.% ={3,4,6,9}

!!"

! !+ !!) !!

! = 2: $! ∈ 0, 0.67

!!" !!

! !+ !!) !!

! = 3: $! ∈ 0, 0.33

Ziqi Wang, Jingzhe Zhang, Shuo Shen, and Wei Hu

!$ !#

!' !*

!!"

! !+ !!) !!

! = 4:$! ∈ 0, 0

! = 1: 0, 1.00 ! = 2: 0, 0.67 ! = 3: 0, 0.33 ! = 4: 0, 0 Neighbor !% layout !!! !$ !" !% !* !& !" !# !% !% !'

Figure 1: Label-stratified similarity graph (LSSG)

a retrieval size larger than 𝑘, and then retains 𝑘 vectors whose label sets satisfy the filter. It can be ineffective when the filter is highly selective and fewer than 𝑘 vectors are returned. (3) In-filtering performs filter checks during index scanning. It is commonly adopted by graph-based indices [12, 16, 34], with filter checks executed when selecting next-hop candidates. Similar to post-filtering, graph traversal may become less connected when few neighbors satisfy the filter and may terminate early at local optima [40]. To overcome the drawbacks of pre-filtering and post-filtering, as well as the early termination of in-filtering graph traversal, novel LFANNS indices [1, 5, 16, 17, 22, 32, 58, 66, 69] are proposed with label partition or label enhancement to improve query performance. However, two critical challenges in LFANNS remain largely unsolved. Challenge 1: Inconsistent support for diverse query semantics. It is difficult to design a unified index due to fundamentally different label set relations: equality queries require exact matches, containment queries require super/sub-sets, and overlap queries require partial intersections. An LFANNS index that is effective for one filter type often does not transfer well to others. For example, indices based on set containment [69] can support equality filters only by maintaining isolated auxiliary structures for each unique label set, which leads to severe index fragmentation and space overhead. Likewise, overlap queries are often handled by iterative containment searches, whose cost grows quickly as the query label set expands [5, 69]. As far as we know, no existing index provides a unified solution to ensure consistent efficiency and theoretical guarantees across all semantics. Challenge 2: Vulnerable to varying label characteristics. Another key challenge in multi-label indexing is to remain robust because the number of distinct label sets grows exponentially as the label space expands. When this number grows to millions, existing indices often face a critical scalability bottleneck: either index size increases dramatically [1, 69], or query latency becomes prohibitively high [5, 32]. The problem is further aggravated by label distribution. Many existing indices implicitly assume that labels follow skewed distributions (e.g., power-law) [1, 5, 32, 66, 69], where a large number of data objects share a small set of common labels. This assumption enables efficient label sharing and therefore more

compact index structures. However, when the distribution goes toward uniform, such sharing opportunities diminish. As a result, indices that rely on label sharing [69] tend to become fragmented or require extensive duplication to remain effective [5]. This creates a rigid trade-off between space consumption and query efficiency, limiting robustness under real-world settings. We propose Label-Stratified Similarity Graph (LSSG), a multi-tier proximity graph that supports equality, containment, and overlap filters within a single index. The key idea is to interpret label set relations through a distance view: different query semantics correspond to searching among vertices with different degrees of label set similarity. Accordingly, LSSG organizes all vertices into tiers stratified by label set distance. Each tier enforces a label distance bound, and edges are created only between vertices whose label sets satisfy that bound. Upper tiers use tighter bounds, producing nested similarity ranges (e.g., (︀0, 1⌋︀ ⊃ (︀0, 0.67⌋︀ ⊃ (︀0, 0.33⌋︀ ⊃ (︀0, 0⌋︀ in Fig. 1). The bottom tier ((︀0, 1⌋︀) is label-agnostic and preserves global navigability, while the top tier ((︀0, 0⌋︀) connects only identical label sets for exact matching. Intermediate tiers progressively tighten label consistency for containment and overlap. Within each tier, vector similarity picks the final neighbors among label-eligible candidates, enabling progressive exploration at query. Let us consider a containment query with label set {3, 6} and query vector 𝑣𝑞 (red star in Fig. 1). Starting from a random valid entry (e.g., 𝑣 4 whose label set {1, 3, 6, 8} contains {3, 6}), a bottomtier traversal behaves like a vanilla proximity graph. It greedily follows vector-similarity edges and may move toward 𝑣 5 , but later stalls because the most promising next hops (e.g., 𝑣 6, 𝑣 7, 𝑣 10 ) are label-incompatible and cannot be expanded. The search is therefore trapped in a local minima over the filtered subset. LSSG mitigates this by escalating to a stricter tier when progress stalls. Higher tiers contain more label-consistent edges, which can reveal an in-filter bridge that is absent (or far less likely) in the label-agnostic tier. For example, LSSG can take 𝑣 5 → 𝑣 12 at tier 3 and reach the true nearest neighbor via 𝑣 12 → 𝑣 11 . Overall, lower tiers preserve global reachability, while higher tiers provide label-consistent shortcuts to escape local minima in selective regions. In summary, our main contributions are outlined below: ● We propose LSSG, a unified multi-tier proximity graph for equality, containment, and overlap filters. The progressive label set stratification unifies the semantics of the three filters in a single graph through tier-ordered in-filtering traversal. ● We introduce a stepwise metric for in-filtering traversal and analyze filter-valid expansion probabilities. Equality is preserved exactly at the top tier, while containment and overlap admit lower bounds under explicit label models. These bounds strengthen monotonically with label set similarity, explaining why intermediate tiers improve filtered navigation. We also derive a conditional logarithmic bound on expected query cost with respect to the filtered subset size. ● We conduct experiments on eight real-world datasets. LSSG improves index size by 16% and indexing time by 22% over the most build-efficient baseline [5]. At matched accuracy, it is up to 1.06x– 92.9x (avg. 19.3x) faster for containment and up to 1.08x–84.1x (avg. 15.5x) faster for overlap than the strongest competitor [69], while using 0.35x index size and 0.87x indexing time. Evaluation

Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA

Table 1: Frequently-used notations

Table 2: Comparison of LFANNS indices

Notations Descriptions

Indices

Mech.

Sem.

Robt.

Guar.

Vers.

Fidl.

Cmpl.

𝒟 = {𝒱, ℒ} Hybrid dataset 𝒟 consisting of vector dataset 𝒱 and label dataset ℒ, with mapping function 𝑙 ∶ 𝒱 → ℒ 𝛿 𝑣 (𝑣1 , 𝑣2 ) Distance between vectors 𝑣1 and 𝑣2 𝛿𝐿 (𝐿1 , 𝐿2 ) Distance between label sets 𝐿1 and 𝐿2 𝑓 Label filter. 𝑓𝑒 : equality; 𝑓𝑐 : containment; 𝑓𝑜 : overlap 𝑁 𝑣𝑡 Neighbor set of 𝑣 at tier 𝑡 𝑐𝑖𝑡 , 𝑛𝑖𝑡 𝑖 th candidate (𝑐) and neighbor (𝑛) in tier 𝑡 𝑇 Number of tiers 𝜔𝑐 Index parameter: beam width in insertion 𝑚 Index parameter: maximum out-degree 𝜙 Index parameter: IVF scanning budget 𝜏, 𝛽 Index parameter: MinHash signature length and bands

NHQ Vamana CAPS UniFilter Curator Packing RWalks UNG ELI

Part. Enhc. Part. Part. Part. Enhc. Enhc. Enhc. Part.

𝑓𝑒 𝑓𝑐 𝑓𝑒 𝑓𝑐 , 𝑓𝑜 𝑓𝑐 , 𝑓𝑜 𝑓𝑐 𝑓𝑐 𝑓𝑒 , 𝑓𝑐 𝑓𝑐 , 𝑓𝑜

× × × ✓ ✓ ✓ × × ×

× × × ✓ × × ✓ × ✓

× × × × × ✓ ✓ ✓ ✓

× × × × × × × ✓ ×

× × ✓ ✓ ✓ × × ✓ ×

LSSG

Enhc.

𝑓𝑒 , 𝑓𝑐 , 𝑓𝑜

✓

also validates scalability to hundreds of thousands of labels and millions of label sets, robustness to label distribution drift, effective tier utilization, and competitive performance against popular ANNS systems. Source code, experiment data, and appendix are available at https:// github.com/ nju-websoft/ LSSG.

Frequently used notations are present in Table 1.

2 Preliminaries 2.1 Problem Formulation

2.2

Definition 1 (ANNS). Given a 𝑑-dimensional vector dataset 𝒱 measured by a distance function 𝛿 𝑣 , for a query vector 𝑣𝑞 ∈ R𝑑 , ANNS seeks to find a result set 𝒫 ⊂ 𝒱 of 𝑘 neighbors (𝑘 ≪ ⋃︀𝒱⋃︀) to minimize 𝑘 ∑𝑖=1 𝛿 𝑣 (𝑣𝑖 , 𝑣𝑞 ), ∀𝑣𝑖 ∈ 𝒫. The main distinction between ANNS and exact 𝑘 nearest neighbor search is that non-closest vectors are allowed in trade for higher efficiency (e.g., queries per second (QPS)). The approximation accu⋃︀𝒫∩𝒯 ⋃︀ racy is usually measured by recall@𝑘, defined by 𝑘 , where 𝒯 denotes the set of 𝑘 exact nearest neighbors. Definition 2 (Label Set and Filter Type). Given a universe of labels 𝐴 = {𝑎 1, 𝑎 2, . . . , 𝑎 ⋃︀𝐴⋃︀ }, where 𝑎 𝑗 is a basic type (e.g., integer, text), a label set dataset is defined by ℒ = {𝐿1, 𝐿2, . . . , 𝐿⋃︀ℒ⋃︀ }, ∀𝐿𝑖 ⊆ 𝐴. Given a query label set 𝐿𝑞 ⊆ 𝐴, there are three label filter (𝑓 ) types: ● Equality filter: 𝑓𝑒 (𝐿𝑖 ⋃︀ 𝐿𝑞 ) = I(𝐿𝑞 = 𝐿𝑖 ), ● Containment filter: 𝑓𝑐 (𝐿𝑖 ⋃︀ 𝐿𝑞 ) = I(𝐿𝑞 ⊆ 𝐿𝑖 ), ● Overlap filter: 𝑓𝑜 (𝐿𝑖 ⋃︀ 𝐿𝑞 ) = I(𝐿𝑞 ∩ 𝐿𝑖 ≠ ∅), where I(⋅) is an indicator that equals 1 if true and 0 otherwise. Label-filtering ANNS is to find the most similar vectors whose corresponding label sets satisfy a given label filter. Definition 3 (LFANNS). Given a hybrid dataset 𝒟 = {𝒱, ℒ}, 𝑙(⋅) ∶ 𝒱 → ℒ denotes a mapping function for the corresponding label set of a vector in ℒ. Given a query vector 𝑣𝑞 ∈ R𝑑 and a query label set 𝐿𝑞 ⊆ 𝐴, LFANNS aims to find a result set ℛ ⊂ 𝒱 of 𝑘 neighbors (𝑘 ≪ ⋃︀𝒱⋃︀) to minimize ∑𝑘𝑖=1 𝛿 𝑣 (𝑣𝑖 , 𝑣𝑞 ), ∀𝑣𝑖 ∈ ℛ ∧ 𝑓 (𝑙(𝑣𝑖 ) ⋃︀ 𝐿𝑞 ) = 1, where 𝑓 ∈ {𝑓𝑒 , 𝑓𝑐 , 𝑓𝑜 }. Like ANNS, the accuracy of LFANNS is measured by recall@𝑘 as well. The filter ratio is defined as the number of passed items over ∑

Notes. Mech.: mechanism (Part.: label partition; Enhc.: label enhancement). Sem.: query semantics supported consistently by design (cf. Challenge 1). Robt.: robustness (cf. Challenge 2). Guar.: whether theoretical guarantees are provided. Vers./Fidl./Cmpl.: the three challenges in [5]: Versatility: base and query label sets contain an arbitrary number of labels; Fidelity: comparisons are only made to vectors whose label sets pass the filter; Completeness: the index returns sufficient 𝑘 vectors.

𝑓 (𝑙(𝑣𝑖 ) ⋃︀ 𝐿𝑞 )

the size of the dataset, formally 𝑣𝑖 ∈𝒱 ⋃︀𝒱⋃︀ . Query workloads with high selectivity typically exhibit a small filter ratio.

Related Work

ANNS and Filtering ANNS. There are mainly four categories of ANNS indices: tree-based [37], LSH-based [27, 54, 55, 64], clusteringbased [13, 14, 24, 33, 35], and graph-based [11, 12, 16, 34, 45, 65]. Graph-based indices are popular for fast and accurate query performance [60, 65], and their efficiency mainly relies on the monotonic search property of relative neighborhood graphs (RNG) [12, 34, 60], where edge pruning preserves this property by eliminating redundant connections based on neighborhood dominance [28, 41]. Filtering ANNS includes four categories: (1) Vector databases and some ANNS libraries [23, 31, 36, 57, 70, 71] employ cost estimation to select between pre-filtering and post-filtering strategies. (2) Predicate-agnostic indices [20, 40, 51] support arbitrary filters without requiring attribute information during index construction. (3) Range-filtering ANNS indices [21, 42, 62, 67, 74] are specifically designed for numerical attributes with filters that denote numeric ranges. (4) LFANNS indices [1, 5, 16, 17, 22, 32, 58, 66, 69] achieve high efficiency for filtering data objects whose label sets contain query-specified labels. Specialized indices for range and label filters show superiority over the first two categories [67, 69]. This paper focuses on LFANNS and discusses recent work as follows. LFANNS indices can be divided into two categories. Label-partition indices group vectors with identical labels or label sets, and groups are arranged by a tree or an inverted file (IVF) structure. Representatives include CAPS [17], ELI [69], UniFilter [66], and Curator [22]. This category is effective when filters are simple and label sets are small (e.g., base/query label sets contain fewer than five labels on average), since the index can focus on frequent labels [17, 22] or manageable label combinations [66, 69]. However, as label sets grow, the number of possible combinations explodes, which either limits support for complex queries [17, 22, 66] or incurs substantial space overhead [69]. Consequently, when a query does not match any pre-built (shared) index, it must fall back to a less compatible

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA

index (typically much larger than the true filtered subset), which can significantly reduce efficiency. Label-enhancement indices leverage label-enhanced edges to connect two vertices in a graph index via fused distance or label sharing relationships. Representatives are NHQ [58], Vamana (filtered and stitched variants) [16], RWalks [1], Packing [32], and UNG [5]. This category can handle label sets with many labels, but existing algorithms perform well only at one end of the selectivity spectrum. NHQ and RWalks are efficient when the filter is non-selective (i.e., when many vectors can pass the filter). They combine the vector distance and the label set distance using a user-defined weight. When the filter is selective, the graph traversal becomes less connected. Vamana, Packing, and UNG are powerful on query workloads with high selectivity. The graph is segmented into groups with identical labels or label sets, and enhanced by cross-group edges that connect only to a limited number of label sets satisfying overlap or containment relationships. Consequently, the traversal becomes less connected for non-selective queries [5, 66]. As summarized in Table 2, LSSG is the only index satisfying all listed criteria. Its performance consistency across all three semantics is empirically validated in Sec. 6.

Algorithm 1: SelectSimilarLabelSets Input: 𝐿𝑥 : inserted label set Output: ℒ𝐶 : similar label set dataset Index parameters :𝜙, 𝜏, 𝛽 (see Table 1) 1 if using IVF scanning then return IVFUnion(𝐿𝑥 , 𝜙); 2 else return MinHashProbe(ℒx , 𝜏, 𝛽); procedure IVFUnion(𝐿𝑥 , 𝜙) ℒ𝐶 ← empty bitmap s.t. ⋃︀ℒ𝐶 ⋃︀ = ⋃︀ℒ𝐼 ⋃︀; 5 𝐿𝑥′ ← sort 𝐿𝑥 by ascending label frequency; 6 foreach label 𝑎 ∈ 𝐿𝑥′ do 7 if ⋃︀ℒ𝐶 ⋃︀ < 𝜙 then ℒ𝐶 ← ℒ𝐶 / IVF𝑎 ; ▷ /: bitwise OR

return ℒ𝐶 ;

procedure MinHashProbe(𝐿𝑥 , 𝜏, 𝛽) ℒ𝐶 ← {}, 𝑟 ← 𝛽𝜏 ; ▷ calculate MinHash rows per band 11 for band 𝐵𝑖 ← 𝐵 1, . . . , 𝐵 𝛽 do 9

▷ 𝐵𝑖 : band is a hash table; hash: FNV-1a hashing [10]

12 13

ℒ𝐶 ← ℒ𝐶 ∪ 𝐵𝑖 (hash(𝑆𝑥 (︀𝑟 × (𝑖 − 1), 𝑟 × 𝑖⌋︀)); return ℒ𝐶 ;

Label Stratified Similarity Graph

This section follows the LSSG workflow. We first define the index topology, then construct it through similar label set selection and multi-tier insertion, and introduce tier-ordered in-filtering search.

3.1

Ziqi Wang, Jingzhe Zhang, Shuo Shen, and Wei Hu

Graph Topology Formalization

Definition 4 (Label-Stratified Similarity Graph, LSSG). Let 𝐺 = (𝑉 , 𝐸) be a label-stratified similarity graph, where 𝑉 and 𝐸 are sets of vertices and directed edges, respectively. Each vertex in 𝑉 denotes a vector, and 𝐸 is partitioned into 𝑇 subsets. The 𝑡 th (1 ≤ 𝑡 ≤ 𝑇 ) subset and 𝑉 compose a subgraph of 𝐺 in tier 𝑡: 𝐺𝑡 = (𝑉 , 𝐸𝑡 ). An edge 𝑣𝑖 → 𝑣 𝑗 ∈ 𝐸𝑡 is subject to the following two constraints: C1. ∀𝑣𝑘 ∈ 𝑉 /{𝑣𝑖 , 𝑣 𝑗 }, 𝛿 𝑣 (𝑣𝑖 , 𝑣 𝑗 ) < 𝛿 𝑣 (𝑣𝑖 , 𝑣𝑘 ) ∨ 𝛿 𝑣 (𝑣𝑖 , 𝑣 𝑗 ) < 𝛿 𝑣 (𝑣 𝑗 , 𝑣𝑘 ); C2. 𝛿𝐿 (𝑙(𝑣𝑖 ), 𝑙(𝑣 𝑗 )) ≤ 𝜃 𝑡 and ∀𝑡 ∈ (1,𝑇 ), ∀𝑣𝑘 ∈ 𝑁𝑢𝑡 /{𝑣𝑖 } ∧𝛿 𝑣 (𝑣𝑖 , 𝑣𝑘 ) 𝑡 > 𝛿 𝑣 (𝑣𝑖 , 𝑣 𝑗 ), 𝛿𝐿 (𝑙(𝑣 𝑗 ), 𝑙(𝑣𝑘 )) ≥ 𝜃 𝑡 , where 𝜃 𝑡 = 1 − 𝑇𝑡 −1 −1 and 𝑁 𝑣𝑖 is the neighbor of 𝑣𝑖 in 𝐺𝑡 . Unlike traditional ANNS graphs relying solely on vector distance 𝛿 𝑣 , LSSG couples vector proximity with label set distance 𝛿𝐿 . We use Euclidean distance for 𝛿 𝑣 and Jaccard distance for 𝛿𝐿 , which are widely adopted in LFANNS [5, 58, 69]. Other choices can also be incorporated [7, 12, 34, 45]. The triangle inequality of Jaccard distance can benefit effective label-based pruning. Constraint C1 follows the standard RNG-style diversification rule used in graph-based ANNS indices like NSG [12] and HNSW [34]. Applied within each tier, it removes redundant neighbors in vector space and preserves directional diversity. Constraint C2 is the core of LSSG’s tiered design and has two roles: (1) Stratification: the condition 𝛿𝐿 (𝑙(𝑣𝑖 ), 𝑙(𝑣 𝑗 )) ≤ 𝜃 𝑡 makes upper tiers (larger 𝑡, smaller 𝜃 𝑡 ) increasingly strict, so edges gradually concentrate among vertices with more similar (and ultimately identical) label sets. (2) Diversification: when multiple candidates appear in a similar direction in vector space, C2 prefers neighbors that are label-wise diverse. Once a closer neighbor 𝑣 𝑗 is selected, a farther neighbor 𝑣𝑘 is retained only if it is sufficiently different from 𝑣 𝑗 in label space

(i.e., 𝛿𝐿 (𝑙(𝑣 𝑗 ), 𝑙(𝑣𝑘 )) ≥ 𝜃 𝑡 ), preventing intermediate tiers from being dominated by a single label cluster and improving reachability across different label combinations. Fig. 1 illustrates the resulting hierarchy. Tier 1 (𝜃 1 = 1) serves as the backbone. Since all label set distances are ≤ 1, C2 is effectively relaxed and the graph behaves like a standard RNG-based ANNS structure, ensuring global navigability. In intermediate tiers (1 < 𝑡 < 𝑇 ), edges are selectively admitted or removed according to 𝜃 𝑡 , which steers traversal toward regions that better match a query’s label requirements. For example, in tier 2 (𝜃 2 = 0.67), an edge 𝑣 6 → 𝑣 9 can be kept because 𝛿𝐿 (𝐿3, 𝐿5 ) falls in the threshold, while a spatially close candidate 𝑣 5 is excluded if 𝛿𝐿 (𝐿3, 𝐿4 ) > 0.67. Tier 𝑇 (𝜃𝑇 = 0) connects only vertices with identical label sets, forming exact-match subgraphs that remain reachable through lower tiers.

3.2

Similar Label Set Selection

To build LSSG, we need to frequently identify candidate label sets that are likely to fall in a tier-specific threshold (i.e., 𝛿𝐿 (⋅, ⋅) ≤ 𝜃 𝑡 ), after which we compute 𝛿𝐿 to verify and filter them. A naive approach is to precompute and store 𝛿𝐿 for all label set pairs, requiring O(1) lookup but O(⋃︀ℒ⋃︀2 ) space and preprocessing. This is infeasible at scale. We use two candidate-selection strategies to avoid quadratic storage and compute exact 𝛿𝐿 only for a bounded candidate set. Progressive IVF scanning reduces memory overhead by indexing label-to-labelset membership. For each label 𝑎, we maintain a bitmap (or posting list) IVF𝑎 indicating which label sets contain 𝑎. Given an inserted label set 𝐿𝑥 , IVFUnion in Alg. 1 initializes an empty bitmap (Line 4), sorts labels in 𝐿𝑥 by ascending label frequency (Line 5), and progressively merges their bitmaps via bitwise OR (Lines 6–7) until a strict candidate budget 𝜙 (in terms of the number of 1-bits) is reached. Processing low-frequency labels first improves selectivity by activating fewer label sets, thereby reducing the candidate space and subsequent 𝛿𝐿 computations.

Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification

(a) Vector space: RNGPrune '$ 2

(!"

1 3

(%"

(""

(&"

prune ("" by "' '$ , ("" > "' (%" , (""

(b) Label space: LabelPrune increase by !! # #' "" "## "$# "%# #& {1,3,6}{1,3}{6}{1,3,6,8}{3,6,8} 1

prune !!" by "# # !"" , # !!"

< &"

Figure 2: Dual-space pruning diversification for tier 2

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA

Algorithm 2: Insert Input: 𝑣 𝑥 : vector to insert; 𝐿𝑥 : label set of 𝑣 𝑥 Output: 𝐼 : index after 𝑣 𝑥 is inserted Index parameters :𝑚, 𝜔𝑐 ,𝑇 (see Table 1) ▷ Phase 1: label set registration

if 𝐿𝑥 ∉ inserted label set dataset ℒ𝐼 then 2 insert 𝐿𝑥 into label IVF bitmaps of ℒ𝐼 ; 3 calculate signature 𝑆𝑥 and insert it into MinHash LSH;

▷ Phase 2: similar label set selection

Progressive MinHash probing. While IVF scanning is accurate and space-efficient, its probing cost can grow with the label universe size ⋃︀𝐴⋃︀ and the number of label sets ⋃︀ℒ⋃︀ (especially under high-frequency labels), and it treats all retrieved candidates uniformly, even though candidates with higher Jaccard similarity are more likely to satisfy 𝛿𝐿 ≤ 𝜃 𝑡 . To address both issues, we use the standard MinHash LSH banding technique [4] to prioritize label sets with high Jaccard similarity. MinHash probing is insensitive to ⋃︀𝐴⋃︀ during lookup and tends to retrieve more similar label sets with higher probability. We target label sets within a tier-specific distance threshold 𝜃 𝑡 (equivalently, Jaccard similarity 𝐽 ≥ 1 − 𝜃 𝑡 ), with a collision probability characterized by Theorem 3.1. Theorem 3.1. Let ℋ = {ℎ 1, ℎ 2, . . . , ℎ𝜏 } be 𝜏 independent hash functions used to form MinHash signatures. For a label set 𝐿 ⊆ 𝐴, its min min min signature is 𝑠𝐿 = (ℎ min 1 (𝐿), ℎ 2 (𝐿), . . . , ℎ𝜏 (𝐿)), where ℎ𝑖 (𝐿) = min𝑎∈𝐿 ℎ𝑖 (𝑎). Partition 𝑠𝐿 into 𝛽 bands, each containing 𝑟 = 𝛽𝜏 rows. For two label sets 𝐿1, 𝐿2 , if 𝐽 (𝐿1, 𝐿2 ) ≥ 1 −𝜃 𝑡 , the probability that they match in at least one band satisfies: 𝑃collide ≥ 1 − (1 − (1 − 𝜃 𝑡 ) ) . 𝑟 𝛽

(1)

Equality holds at the similarity boundary 𝐽 (𝐿1, 𝐿2 ) = 1 − 𝜃 𝑡 . The proof is given in Appendix A. Since 𝑃collide increases with Jaccard similarity (and thus decreases with 𝜃 𝑡 ), more similar label sets are more likely to be retrieved. This property aligns with LSSG’s tiering: higher tiers impose smaller 𝜃 𝑡 and stricter label constraints, so candidate selection increasingly prioritizes highly similar label sets. In practice, (𝜏, 𝛽) controls the recall–efficiency trade-off. A larger signature improves recall but also increases probing cost. Based on this guarantee, MinHashProbe (Lines 11–12 in Alg. 1) gathers candidate label sets ℒ𝐶 by probing 𝛽 LSH tables using the band hashes of 𝐿𝑥 ’s signature. We then compute 𝛿𝐿 only on ℒ𝐶 for the later selection of which candidates satisfy 𝛿𝐿 ≤ 𝜃 𝑡 .

3.3

Multi-tiered Insertion

Alg. 2 inserts a vector 𝑣 𝑥 with label set 𝐿𝑥 in four phases. Phase 1 (label set registration). We first check whether 𝐿𝑥 has appeared before. If 𝐿𝑥 is new, we register it in the label-to-labelset inverted structures (e.g., IVF bitmaps). When MinHash is enabled, we additionally compute the MinHash signature of 𝐿𝑥 and insert it into the corresponding LSH band tables. Phase 2 (similar label set selection). We then invoke Alg. 1 to retrieve a candidate set of label sets likely to be close to 𝐿𝑥 . For each retrieved label set 𝐿, we compute 𝛿𝐿 (𝐿𝑥 , 𝐿) and cache the results in a map 𝒥 . It is later reused to filter candidates by tier thresholds 𝜃 𝑡 without recomputing 𝛿𝐿 .

ℒ𝐶 ← SelectSimilarLabelSets(𝐿𝑥 ); 5 𝒥 ← {𝛿 𝐿 (𝐿𝑥 , 𝐿𝑦 ) ⋃︀ 𝐿 𝑦 ∈ ℒ𝐶 }; 6 𝐶 ← {}; ▷ pool for cross-tier sharing candidates 7 for tier 𝑡 ← 1, . . . ,𝑇 do 4

▷ Phase 3: filtered candidate selection

8 9 10

ℒ𝑡 ← {𝐿𝑦 ⋃︀ 𝛿𝐿 (𝐿𝑥 , 𝐿𝑦 ) ∈ 𝒥 ∩ (︀0, 𝜃 𝑡 ⌋︀}; ▷ 𝜃 𝑡 = 1 − 𝑇𝑡 −1 −1 𝐶 ← {𝑐 ⋃︀ 𝑐 ∈ 𝐶 ∧ 𝑙(𝑐) ∈ ℒ𝑡 }; ▷ retain similar label sets if ⋃︀𝐶 ⋃︀ < 𝑚 then 𝐶 ← 𝐶 ∪ BeamSearch(𝑣 𝑥 , ℒ𝑡 , 𝜔𝑐 ); ▷ Phase 4: dual-space pruning and edge update

11 12 13 14 15

𝑁 𝑣𝑡𝑥 ← RNGPrune(𝐶, 𝑚2 ); foreach vector 𝑣 𝑦 ∈ 𝑁 𝑣𝑡𝑥 do 𝑁 𝑣𝑡𝑦 ← 𝑁 𝑣𝑡𝑦 ∪ {𝑣 𝑥 }; ▷ skip Line 14 if ⋃︀𝑁 𝑣𝑡𝑦 ⋃︀ ≤ 𝑚 𝑡 𝑡 𝑁 𝑣𝑦 ← RNGPrune(𝑁 𝑣𝑦 ,𝑚) ∩ LabelPrune(𝑁 𝑣𝑡𝑦 , 𝜃 𝑡 ); return 𝐼 ;

Phase 3 (vector-space candidate collection). For each tier 𝑡, we collect candidate vertices by combining vector proximity with the tier-specific label constraint. Specifically, we restrict candidates to vertices whose label sets satisfy 𝛿𝐿 (𝐿𝑥 , 𝑙(𝑣)) ∈ (︀0, 𝜃 𝑡 ⌋︀, and perform beam search (Alg. 3) to obtain a vector-close candidate pool. When the candidate pool from Phase 2 is already sufficiently large, we optionally skip beam search to accelerate indexing, a common strategy in hierarchical graph indices [42, 62]. Phase 4 (dual-space pruning and edge update). Finally, we construct outgoing edges for 𝑣 𝑥 by enforcing the two constraints in Def. 4. We select up to 𝑚2 neighbors from the filtered candidates and keep the remaining capacity for future insertions [34], following an RNG-style pruning strategy (RNGPrune). Fig.2(a) iteratively considers candidates in ascending 𝛿 𝑣 order (𝑐 12 → 𝑐 42 → 𝑐 32 → 𝑐 22 ) and removes geometrically redundant edges (𝑐 22 in this example). For each picked neighbor 𝑣 𝑦 , we also attempt to insert the backedge into 𝑣 𝑦 ’s neighbor list. If 𝑣 𝑦 ’s list is full, we apply RNGPrune to reduce vector-space redundancy. If the remaining neighbors still satisfy the RNG constraint, we further apply LabelPrune to increase label set diversity. This dual-space pruning reserves capacity for neighbors with more diverse label sets, and reduces local graph density, which speeds up traversal convergence and, in turn, lowers the total indexing cost of candidate preparation in Phase 3. Fig. 2(b) shows LabelPrune in tier 2, where 𝜃 2 = 0.67 (rounded from 𝜃 2 = 32 , hereafter). Consider diversifying the neighbor list of a selected neighbor 𝑣 𝑦 with 𝑙(𝑣 𝑦 ) = {1, 3, 6}, and candidate neighbors 𝑛 21 ∶ {1, 3, 6}, 𝑛 22 ∶ {1, 3}, 𝑛 23 ∶ {6}, 𝑛 24 ∶ {1, 3, 6, 8}, as well as the incoming vertex 𝑣 𝑥 with 𝑙(𝑣 𝑥 ) = {3, 6, 8}. LabelPrune processes candidates in ascending 𝛿 𝑣 order and compares each candidate only

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA

Algorithm 3: BeamSearch Input: 𝑣𝑞 : query vector; ℒ𝑞 : selected label set dataset; 𝜔: beam width Output: 𝑊 = {𝑣𝑖 ⋃︀ 𝑙(𝑣𝑖 ) ∈ ℒ𝑞 }: neighbor set Index parameters :𝑚,𝑇 (see Table 1) 1 𝒱𝑟 ← selected vectors s.t. ∀𝑣 𝑟 ∈ 𝒱𝑟 , 𝑙(𝑣 𝑟 ) ∈ ℒ𝑞 ; 2 𝐶 ← 𝒱𝑟 ,𝑊 ← 𝒱𝑟 ; ▷ min-heap 𝐶 and max-heap 𝑊 sorted by 𝛿 𝑣 3 while 𝐶 ≠ ∅ do 4 𝑐 ← pop the nearest vertex to 𝑣𝑞 from 𝐶; 5 if 𝛿 𝑣 (𝑐, 𝑣𝑞 ) > max𝑤∈𝑊 𝛿 𝑣 (𝑤, 𝑣𝑞 ) then break; 6 for tier 𝑡 ← 1, . . . ,𝑇 do 7 𝑈 ← 𝑈 ∪ {𝑢 ⋃︀𝑢 ∈ 𝑁𝑐𝑡 ∧ 𝑙(𝑢) ∈ ℒ𝑞 }; 8 if number of unvisited vertices in 𝑈 > 𝑚 then 9 keep the first 𝑚 unvisited vertices and break; foreach unvisited neighbor 𝑢 ∈ 𝑈 do if ⋃︀𝑊 ⋃︀ < 𝜔 or 𝛿 𝑣 (𝑢, 𝑣𝑞 ) < max𝑤∈𝑊 𝛿 𝑣 (𝑤, 𝑣𝑞 ) then mark 𝑢 as visited and push it to 𝐶,𝑊 ;

10 11 12

while ⋃︀𝑊 ⋃︀ > 𝜔 do pop 𝑊 ;

13 14

return 𝑊 ;

against the already kept neighbors. A candidate is pruned if (1) its label set is identical to 𝑙(𝑣 𝑦 ), or (2) its label set distance to any kept neighbor is smaller than the tier threshold 𝜃 2 . Specifically, 𝑛 21 is pruned by (1) due to 𝑙(𝑛 21 ) = 𝑙(𝑣 𝑦 ). 𝑛 22 is kept as the first accepted neighbor. 𝑛 23 is also kept since 𝛿𝐿 (𝑙(𝑛 22 ), 𝑙(𝑛 23 )) = 1 <⇑ 0.67. 𝑛 24 is pruned by (2) because it is label-redundant w.r.t. the kept neighbor 𝑛 22 ∶ 𝛿𝐿 (𝑙(𝑛 22 ), 𝑙(𝑛 24 )) = 1 − 24 = 0.5 < 0.67. Finally, 𝑣 𝑥 is kept since it is sufficiently different from the kept neighbors: 𝛿𝐿 (𝑙(𝑛 22 ), 𝑙(𝑣 𝑥 )) = 0.75 > 0.67 and 𝛿𝐿 (𝑙(𝑛 23 ), 𝑙(𝑣 𝑥 )) = 0.67 <⇑ 0.67.

3.4

In-Filtering Traversal and LFANNS Query

Alg. 3 performs beam search on the filtered subgraph induced by the label set scope ℒ𝑞 (i.e., only vertices with 𝑙(𝑣) ∈ ℒ𝑞 are eligible). It starts by selecting a small set of entry vertices 𝒱𝑟 from the eligible vertices (Line 1), and initializes both the candidate min-heap 𝐶 and the result max-heap 𝑊 with 𝒱𝑟 (Line 2). Selecting entry vertices across label sets helps preserve completeness. Even when crosslabel connectivity is sparse in lower tiers, the search can still start from multiple valid label set regions rather than being trapped in a single region. This issue is inevitable if the index is not built on the fully filtered graph for every possible query, yet such a practice is impractical for LFANNS as to be discussed in Sec. 4. The traversal iteratively expands candidates (Lines 3–13). At each iteration, it pops the current closest vertex 𝑐 from 𝐶 (Line 4) and terminates early when 𝑐 is already farther than the worst element in 𝑊 (Line 5), a standard beam-search stopping criterion. For next-hop expansion, it scans neighbors of 𝑐 tier by tier and only collects those whose labels satisfy 𝑙(𝑢) ∈ ℒ𝑞 (Line 7). This in-filtering expansion enforces fidelity by preventing the search from spending steps on unqualified vertices. To align the expansion cost with the graph topology, Lines 8–9 cap the number of newly considered (unvisited) candidates to at most 𝑚, avoiding excessive 𝛿 𝑣 evaluations that are unlikely to improve the current beam. Lines 10–13 maintain the

Ziqi Wang, Jingzhe Zhang, Shuo Shen, and Wei Hu

Algorithm 4: LFANNS Input: 𝑣𝑞 : query vector; 𝐿𝑞 : query label set; 𝑓 : query filter; 𝜔𝑠 : search beam width; 𝑘: number of neighbors Output: ℛ: 𝑘 filtered approximate nearest neighbors 1 if 𝑓 = 𝑓𝑒 then ℒ𝑞 ← {𝐿𝑞 } ; 2 else if 𝑓 = 𝑓𝑐 then ℒ𝑞 ← IVFIntersetion(𝐿𝑞 , ⋃︀𝐿𝑞 ⋃︀) ; 3 else if 𝑓 = 𝑓𝑜 then ℒ𝑞 ← IVFUnion(𝐿𝑞 , ⋃︀𝐿𝑞 ⋃︀) ; 4 ℛ ← BeamSearch(𝑣 𝑞 , ℒ𝑞 , 𝜔 𝑠 ); 5 while ⋃︀ℛ⋃︀ > 𝑘 do pop 𝑅; 6 return ℛ;

two heaps so that the search continues to prioritize vertices closer to 𝑣𝑞 while bounding 𝑊 by the beam width 𝜔. Alg. 4 shows the end-to-end LFANNS query procedure on LSSG. It first transforms the query filter 𝑓 and query label set 𝐿𝑞 into a label set scope ℒ𝑞 (Lines 1–3), which specifies the admissible label sets for the query. For equality queries (𝑓𝑒 ), ℒ𝑞 is simply {𝐿𝑞 }. For containment (𝑓𝑐 ) and overlap (𝑓𝑜 ), ℒ𝑞 is obtained via bitmap intersection or union over the inverted structures induced by the labels in 𝐿𝑞 . This design supports arbitrary query label sets without assuming a fixed label cardinality, thereby satisfying versatility. Given ℒ𝑞 , the algorithm runs in-filtering beam search (Line 4) and finally retains the closest 𝑘 vectors in ℛ (Line 5).

4 Stepwise Analysis of Filter-Valid Expansion 4.1 Stepwise Oracle Proxy The key effect of LSSG is to leverage tiered label stratification to increase the probability that an expansion from a filter-valid vertex reaches another filter-valid vertex. This reduces ineffective infiltering expansions compared with a label-agnostic graph, while avoiding the infeasible cost of building a separate graph for every possible query filter. We use the oracle label-filtered RNG as a conceptual reference for filter-valid navigation. Definition 5 (Oracle Label-Filtered RNG). Given a query label set 𝐿𝑞 and a label filter 𝑓 on a hybrid dataset 𝒟 = {𝒱, ℒ}, an oracle label-filtered RNG, denoted by 𝑂 𝑓 ,𝐿𝑞 , is built on 𝒱 𝑓 ,𝐿𝑞 ⊆ 𝒱, where ∀𝑣𝑖 ∈ 𝒱 𝑓 ,𝐿𝑞 , 𝑣 𝑗 ∈ 𝒱 − 𝒱 𝑓 ,𝐿𝑞 , 𝑓 (𝑙(𝑣𝑖 ) ⋃︀ 𝐿𝑞 ) = 1, 𝑓 (𝑙(𝑣 𝑗 ) ⋃︀ 𝐿𝑞 ) = 0. Edges in 𝑂 𝑓 ,𝐿𝑞 satisfy C1 in Def. 4. Constructing 𝑂 𝑓 ,𝐿𝑞 for all possible (𝑓 , 𝐿𝑞 ) is infeasible because the query label set is not known in advance. LSSG therefore keeps a single multi-tier graph and approximates the oracle behavior only at the level of one expansion step. Let 𝑐 be the current hop selected by best-first search (Alg. 3, Line 4), and let 𝑢 ′ ∈ 𝑁𝑐𝑡 be a neighbor of 𝑐 at tier 𝑡. Denote 𝐿1 = 𝑙(𝑐) and 𝐿2 = 𝑙(𝑢 ′ ). By LSSG construction, an edge in tier 𝑡 satisfies 𝛿𝐿 (𝐿1, 𝐿2 ) = 1 − 𝐽 (𝐿1, 𝐿2 ) ≤ 𝜃 𝑡 = 1 − 𝜖𝑡 , ⋃︀𝐿 ∩𝐿 ⋃︀ equivalently 𝐽 (𝐿1, 𝐿2 ) ≥ 𝜖𝑡 , where 𝐽 (𝐿1, 𝐿2 ) = ⋃︀𝐿11 ∪𝐿22 ⋃︀ and 𝜖𝑡 ∈ (︀0, 1⌋︀. The stepwise filter-valid expansion probability is Pr(𝑢 ′ ∈ 𝑈 ) = Pr (𝑓 (𝐿2 ⋃︀ 𝐿𝑞 ) = 1 ⋂︀ 𝑓 (𝐿1 ⋃︀ 𝐿𝑞 ) = 1 ∧ 𝐽 (𝐿1, 𝐿2 ) ≥ 𝜖𝑡 ), (2)

where 𝐿𝑞 is the query label set and 𝑓 is the filter in Alg. 4. For the oracle graph 𝑂 𝑓 ,𝐿𝑞 (Def. 5), all vertices satisfy 𝑓 (⋅ ⋃︀ 𝐿𝑞 ) = 1 by construction, hence Pr(𝑢 ′ ∈ 𝑈 ) = 1 trivially. For LSSG, it measures the local probability of an expansion inside the filtered vertex set,

4.2

Containment Target Probability

1.0

250

500

750

|A| (Number of Labels)

1.00

1.00 0.88

0.75

0.76 0.64

0.50

0.52 0.40

0.25 1.0

0.28

1.5

2.0

2.5

s (Skewness Factor)

3.0

0.16

(b) s vs ε (|A|=100, µ=0.5H|A|,s)

0.88

2.5

0.76 0.64

2.0

0.52 0.40

1.5

0.28

1.0 0.6

1.00

Lower Bound of Pc

1.5

s (Skewness Factor)

2.0

3.0

0.7

0.8

0.9

1.0

ε (Jaccard Similarity)

0.16

(d) µ vs ε (|A|=100, s=1.5) 0.92

Lower Bound of Pc

For tier 𝑇 of LSSG, 𝜃𝑇 = 0 and thus 𝐽 (𝐿1, 𝐿2 ) ≥ 𝜖𝑇 = 1, which implies 𝐿1 = 𝐿2 . Hence 𝑃𝑒 = 1 in tier 𝑇 , which means once an equality-valid vertex is reached, a top-tier expansion preserves equality validity at the label level. The containment and overlap cases require additional model assumptions, stated explicitly below.

2.5

0.85 0.80 0.75 0.70 0.65 0.60 0.55 0.50 0.45 0.40

Lower Bound of Pc

● Equality: 𝑃𝑒 = Pr (𝐿𝑞 = 𝐿2 ⋃︀ 𝐿𝑞 = 𝐿1 ∧ 𝐽 (𝐿1, 𝐿2 ) ≥ 𝜖); ● Containment: 𝑃𝑐 = Pr (𝐿𝑞 ⊆ 𝐿2 ⋃︀ 𝐿𝑞 ⊆ 𝐿1 ∧ 𝐽 (𝐿1, 𝐿2 ) ≥ 𝜖); ● Overlap: 𝑃𝑜 = Pr (𝐿𝑞 ∩ 𝐿2 ≠ ∅ ⋃︀ 𝐿𝑞 ∩ 𝐿1 ≠ ∅ ∧ 𝐽 (𝐿1, 𝐿2 ) ≥ 𝜖).

(a) s vs |A| (µ=0.5H|A|,s, ε=0.8)

µ H|A|,s (Scaling Factor)

Definition 6 (Target Probabilities for Three Filters). For label sets 𝐿1, 𝐿2 and query label set 𝐿𝑞 , define:

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA

3.0

µ H|A|,s (Scaling Factor)

and is also a stepwise proxy for filtered navigation quality. For a fixed tier 𝑡, we write 𝜖 instead of 𝜖𝑡 for simplicity. Considering the three filter types in Def. 2, Pr(𝑢 ′ ∈ 𝑈 ) has corresponding forms:

s (Skewness Factor)

Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification

0.75

0.80

0.50

0.56

0.68 0.44

0.25 0.6

0.32

0.7

0.8

0.9

1.0

ε (Jaccard Similarity)

0.20

Figure 3: Simulation of Theorem 4.2 i.e., 𝑝𝑖 = 𝐻𝜇𝑖

−𝑠

⋃︀𝐴⋃︀,𝑠

⋃︀𝐴⋃︀

for 𝑖 = 1, 2, . . . , ⋃︀𝐴⋃︀ and 𝑠 ≥ 0, where 𝐻 ⋃︀𝐴⋃︀,𝑠 = ∑ 𝑗=1 𝑗 −𝑠

We analyze containment under an independent Bernoulli model. All proofs are in Appendices B and C.

is the generalized harmonic number and 𝜇 = E(︀⋃︀𝐿 ⋃︀⌋︀ ∈ (0, 𝐻 ⋃︀𝐴⋃︀,𝑠 ⌋︀ is

Definition 7 (Independent Bernoulli inclusion model). For each label 𝑎𝑖 ∈ 𝐴, let 𝑝𝑖 ∈ (︀0, 1⌋︀ be its inclusion probability, sorted so that 𝑝𝑖 ≥ 𝑝𝑖+1 . Labels are included independently in each generated label set, i.e., Pr(𝑎𝑖 ∈ 𝐿) = 𝑝𝑖 . We assume 𝐿1 , 𝐿2 , and 𝐿𝑞 are generated independently from this model unless stated otherwise.

for some 𝜌 ∈ (0, 1), and let 𝐵 = 1+𝜖 . For any 𝑞 ≥ 0, define )︀ (𝑟 + 𝑥 − 1)1−𝑞 − (𝑟 − 1)1−𝑞 ⌉︀ ⌉︀ , 𝑞 ≠ 1, ⌉︀ ⌉︀ 1−𝑞 𝑥 ≥ 0. Then, the Ψ𝑞 (𝑥) ∶= ⌋︀ 𝑟 +𝑥 −1 ⌉︀ ⌉︀ ⌉︀ ln , 𝑞 = 1, ⌉︀ ]︀ 𝑟 −1 containment target probability satisfies

We first give a distribution-agnostic lower bound for 𝑃𝑐 . Theorem 4.1 (Lower Bound of 𝑃𝑐 ). For ∀𝐿1, 𝐿2 ∈ ℒ that satisfy 𝐽 (𝐿1, 𝐿2 ) ≥ 𝜖, the worst-case lower bound of 𝑃𝑐 is 𝑃𝑐 ≥ (1 − 𝑝 max )(1−𝜖)⋃︀𝐴⋃︀,

𝑝 max = max 𝑝𝑖 . 𝑎𝑖 ∈𝐴

(3)

Further, 𝜇 = E(︀⋃︀𝐿1 ⋃︀⌋︀ = ∑𝑎𝑖 ∈𝐴 𝑝𝑖 , 𝜎 2 = V(︀⋃︀𝐿1 ⋃︀⌋︀ = ∑𝑝𝑖 ∈𝐴 𝑝𝑖 (1 − 𝑝𝑖 ), 𝜎 ) (1−𝜖)(𝜇+ ⌈︂

𝑃𝑐 ≥ (1 − 𝑝 max )

𝜉

with probability 1 − 𝜉.

(4)

Theorem 4.1 is most informative for uniform or near-uniform label distributions. For example, suppose 𝜇 = 5 and ⋃︀𝐴⋃︀ = 100, i.e., each label set contains five labels on average and the universe has 100 labels. Under a uniform distribution, 𝑝𝑖 = ⋃︀𝐴𝜇 ⋃︀ = 0.05. For 𝜖 = 0.8, the worst-case bound in Eq. (3) gives 𝑃𝑐 ≥ 0.950.2×100 = 0.358, which is always valid but conservative. With confidence 1−𝜉 = 95%, Eq. (4) ⌉︂ 0.2×(5+ 4.75 )

0.05 yields 𝑃𝑐 ≥ 0.95 = 0.859 > 0.358. In real-world systems, label distributions are often power-law (Zipf-like) [5, 44, 69, 73]. A small number of head labels occur frequently, while most tail labels are rare. In such skewed settings, the distribution-agnostic bound in Theorem 4.1 becomes overly conservative because 𝑝 max is dominated by extreme head labels. However, this looseness does not reflect actual intersection dynamics. Under a high Jaccard similarity constraint, a frequent head label is unlikely to appear in the difference set 𝐷 = 𝐿1 /𝐿2 because missing a high-frequency label in 𝐿2 would strongly penalize Jaccard similarity. Thus, the difference set tends to be dominated by labels with relatively small-to-moderate inclusion probabilities, leading to the sharper bound below.

Theorem 4.2 (Lower Bound of 𝑃𝑐 under Skewed Distribution). Let label inclusion probabilities follow the Zipf distribution,

the expected label set size. Define 𝑟 = max(2, arg min𝑖 𝐻 𝑖,𝑠 ≥ 𝜌) 𝐻

⋃︀𝐴⋃︀,𝑠

2𝜇(1−𝜖)

⎞ ⎛ 𝜇 𝜇2 𝑃𝑐 ≥ exp − Ψ𝑠 (𝐵) − 2 Ψ2𝑠 (𝐵) (1 − 𝜇𝜌(1 − 𝜖)). 𝐻 ⋃︀𝐴⋃︀,𝑠 ⎝ 𝐻 ⋃︀𝐴⋃︀,𝑠 ⎠

(5)

Theorem 4.2 complements the conservative bound in Theorem 4.1 by giving a sharper characterization under skewed label distributions. Fig. 3 shows three consistent trends: the bound improves with stronger skew and larger Jaccard threshold 𝜖, but decreases as the expected label set size 𝜇 grows. For example, at ⋃︀𝐴⋃︀ = 100, the bound increases from 𝑃𝑐 ≥ 0.56 when 𝑠 = 1 to 𝑃𝑐 ≥ 0.84 when 𝑠 = 2, and from 𝑃𝑐 ≥ 0.60 at 𝜖 = 0.6 to 𝑃𝑐 ≥ 0.79 at 𝜖 = 0.8. These trends support the same navigation intuition: stricter tiers shrink the missing-label set 𝐷 = 𝐿1 /𝐿2 , thereby increasing the probability of a containment-valid next hop expansion.

4.3

Overlap Target Probability

For overlap queries, the probability of non-overlap is maximized when the query label set is as small as possible. Theorem 4.3 (Lower Bound of 𝑃𝑜 ). Assuming that query label sets of the same size are equally likely, for any 𝐿1, 𝐿2 ∈ ℒ satisfying 𝐽 (𝐿1, 𝐿2 ) ≥ 𝜖, the overlap target probability satisfies 𝑃𝑜 ≥ 𝜖. Theorem 4.3 shows that 𝑃𝑜 increases with label set similarity. Summary. The containment and overlap analyses lead to the same design principle. As the tier threshold becomes stricter, an expansion from a filter-valid vertex is more likely to remain filter-valid. For containment, stricter tiers reduce the possible missing-label set 𝐿1 /𝐿2 . For overlap, the lower bound scales with the sharedlabel ratio induced by 𝐽 (𝐿1, 𝐿2 ) ≥ 𝜖𝑡 . Thus, lower tiers preserve global vector-space reachability, while higher tiers provide labelconsistent shortcuts. This is the core mechanism by which LSSG

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA

Ziqi Wang, Jingzhe Zhang, Shuo Shen, and Wei Hu

approaches oracle filtered navigation without constructing a separate graph for each query filter.

5 Asymptotic Complexity 5.1 Index Size LSSG is composed of graph topology and auxiliary label selection structures. Each vertex stores at most 𝑚 neighbors per tier, giving O(𝑚⋃︀𝒱⋃︀𝑇 ) graph space. This bound is further tightened by the diversification strategy (Fig. 2), which prunes redundant edges based on label and vector proximity. IVF bitmaps require O(⋃︀𝐴⋃︀⋃︀ℒ⋃︀) bits, while MinHash signatures and LSH buckets require O((𝜏 + 𝛽)⋃︀ℒ⋃︀) space. Relative to a standard proximity graph, the topology incurs the tier factor 𝑇 and the additional label selection structures.

5.2

Indexing Time

For an inserted vector 𝑣 𝑥 with label set 𝐿𝑥 , let 𝐾𝑥 be the number of label set candidates returned by IVF or MinHash, ℓ¯𝑥 be their average cardinality, and 𝐵𝑥 be the number of processed IVF bitmap words. The cost of candidate selection and Jaccard verification is )︀ ⌉︀ ⌉︀O(𝐵𝑥 ), 𝐶 label (𝑥) = O (𝐾𝑥 (⋃︀𝐿𝑥 ⋃︀ + ℓ¯𝑥 )) + ⌋︀ ⌉︀ ⌉︀ ]︀O(𝜏⋃︀𝐿𝑥 ⋃︀ + 𝛽 + 𝐾𝑥 ),

IVF, (6) MinHash.

Let 𝐻𝑥,𝑡 denote the actual number of vertices expanded at tier 𝑡. Each expansion scans at most 𝑚𝑇 neighbors, computes at most 𝑚 vector distances, and performs at most 𝑚 queue updates. Including outgoing and reverse-edge pruning, the deterministic insertion cost 𝐶 ins (𝑥) is 𝑇

𝐶 ins (𝑥) = 𝐶 label (𝑥) + O (∑ 𝐻𝑥,𝑡 (𝑚𝑇 + 𝑚𝑑 + 𝑚 log 𝜔𝑐 )) 𝑡 =1

+ O (𝑇 (𝑚𝜔𝑐 𝑑 + 𝑚 3 (𝑑 + ℓ¯𝑥 ))) .

(7)

The indexing time mainly depends on the expansion counts 𝐻𝑥,𝑡 . For a tier-induced search graph satisfying the monotonicity conditions of [12], the expected search path length is logarithmic in the graph size. With fixed beam width, this gives

E(︀𝐻𝑥,𝑡 ⌋︀ = O (log ⋃︀𝒱𝑥,𝑡 ⋃︀) ,

𝒱𝑥,𝑡 = {𝑣 ∈ 𝒱 ∶ 𝛿𝐿 (𝑙(𝑣), 𝐿𝑥 ) ≤ 𝜃 𝑡 }. (8)

Therefore, for fixed parameters and bounded label set selection cost, LSSG retains the expected O(⋃︀𝒱⋃︀ log ⋃︀𝒱⋃︀) construction time of standard proximity graph indexing, with additional costs from label selection, pruning, and tiered traversal.

5.3

Query Time

For a query (𝑣𝑞 , 𝐿𝑞 , 𝑓 ), Alg. 4 first constructs the filtered label set scope ℒ𝑞 . The scope construction cost is )︀ ⌉︀ 𝑓 = 𝑓𝑒 , ⌉︀O(1), 𝐶 scope (𝑓 , 𝐿𝑞 ) = ⌋︀ (9) ⌉︀ O(∑𝑎∈𝐿𝑞 ⋃︀IVF𝑎 ⋃︀), 𝑓 ∈ {𝑓𝑐 , 𝑓𝑜 }. ⌉︀ ]︀ Let 𝐻 𝑓 ,𝑞 be the actual number of expanded vertices and define 𝜂𝑞 = 𝑚𝑇 + 𝑚𝑑 + 𝑚 log 𝜔𝑠 . The deterministic query cost is 𝐶 query (𝑓 , 𝑞) = 𝐶 scope (𝑓 , 𝐿𝑞 ) + O(𝐻 𝑓 ,𝑞 𝜂𝑞 ).

(10)

This bound holds for any realized graph and query trace. Here, 𝑚𝑇 is the tier-scanning overhead, while stricter tiers increase the chance that scanned neighbors remain label-qualified.

Let 𝒱 𝑓 ,𝐿𝑞 = {𝑣 ∈ 𝒱 ∶ 𝑙(𝑣) ∈ ℒ𝑞 } be the filtered vertex scope. By the monotonic-search result used above, its oracle filtered graph requires O(log ⋃︀𝒱 𝑓 ,𝐿𝑞 ⋃︀) expected progress steps. Let 𝛼 𝑓 ∈ {𝑃𝑒 , 𝑃𝑐 , 𝑃𝑜 } be the filter-valid expansion lower bound from Sec. 4. Under the stepwise proxy in Sec. 4, one filter-valid expansion requires O(𝛼 𝑓−1 ) attempted expansions in expectation. Combining this factor with the oracle progress length gives the conditional estimate E(︀𝐻 𝑓 ,𝑞 ⌋︀ = O (𝛼 𝑓−1 log ⋃︀𝒱 𝑓 ,𝐿𝑞 ⋃︀). Therefore, E(︀𝐶 query (𝑓 , 𝑞)⌋︀ = 𝐶 scope (𝑓 , 𝐿𝑞 ) + O (𝛼 𝑓−1𝜂𝑞 log ⋃︀𝒱 𝑓 ,𝐿𝑞 ⋃︀) ,

(11)

which serves as the conditional search-effort estimate. For fixed 𝑇 ,𝑚, 𝜔𝑠 and 𝛼 𝑓 = Ω(1), the expected traversal cost is O(log ⋃︀𝒱 𝑓 ,𝐿𝑞 ⋃︀). Compared with traversal on a standard proximity graph, LSSG pays the tier scanning overhead but reduces ineffective expansions.

Evaluation

We evaluate LSSG by addressing the following research questions: RQ1. How does LSSG perform in construction? Can it achieve smaller index size and faster indexing speed than state-ofthe-art LFANNS indices? Is it robust to variations in vector volume and label cardinality? RQ2. How does LSSG perform in LFANNS queries? Does it consistently deliver high recall and low latency across query semantics, evolving label distributions, and diverse label characteristics, thereby addressing the two challenges in Sec. 1? RQ3. How effective are LSSG’s key design components? What are the comparative strengths of its label set selection algorithms? How do tier usage and filter-valid expansion explain the query benefits by stratification? How does LSSG scale with increasing vector and label scales?

6.1

Experiment Setup

Environment. We use a Ubuntu 20.04 LTS server with an Intel Xeon Gold 6326 CPU @ 2.90 GHz and 240 GB memory. The CPU has 16 physical cores, 512 KB L1 cache, 65,536 KB L2 cache, and 16 MB L3 cache. All indices are implemented in C++ and compiled by g++ 9.4.0 with -Ofast and -avx512f compile options enabled. Datasets. Table 3 summarizes the statistics of eight real-world benchmark datasets with Zipf-like label distributions. Datasets are evaluated under three semantics, each using ⋃︀𝑄 ⋃︀ queries (in total ⋃︀𝑄 ⋃︀ × 3). For each query semantics, label sets are generated independently. Equality queries sample existing base label sets. Containment and overlap queries sample from the dataset label universe. All queries are retained only if they admit at least 𝑘 valid answers. Query-label statistics are reported in Appendix D. ● SIFT and GIST [3] are two classic vector datasets. Following [5, 40, 58, 66], we generate synthetic integer labels. ● TripClick [48] encodes click logs from a health web search engine [47] using the DPR model [26]. Following [5, 40], we use 28 clinical labels, with remaining labels categorized as “others”. ● LAION [50] contains four million image-caption pairs, with images embedded by the CLIP model [46]. Following [40], we pick a one-million subset with 30 caption keywords as labels.

Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA

Table 3: Statistical data of the benchmark datasets

Datasets SIFT GIST TripClick LAION YTB-Video YTB-Audio Wikipedia YFCC-1M

Size

Dim

⋃︀𝐴⋃︀

⋃︀ℒ⋃︀

1,000,000 128 12 2,385 1,000,000 960 12 2,385 1,055,976 768 29 7,734 1,000,448 512 30 62,066 1,000,000 1,024 3,862 160,018 5,000,000 128 3,862 498,335 5,000,000 384 237,417 184,298 1,000,000 192 181,931 636,356

Table 4: Indexing performance

Avg/Med/P90 label set size

⋃︀𝑄 ⋃︀

2.3 / 2 / 4 2.3 / 2 / 4 1.1 / 1 / 2 2.9 / 3 / 5 3.0 / 3 / 5 3.0 / 3 / 5 5.9 / 6 / 8 8.8 / 6 / 16

10,000 1,000 1,000 1,000 200 1,000 1,000 1,000

Index size (MB) Indices

SIFT GIST Trip LAION Video Audio Wiki YFCC

ACORN Packing RWalks UNG ELI

346 310 413 228 419

346 306 413 410 440

366 311 578 318 351

347 439 552 271 745

LSSG-IVF ⋆-MinHash

311 296

204 192

199 200

271 277

Indices

SIFT GIST Trip LAION Video Audio Wiki YFCC

ACORN Packing RWalks UNG ELI

223 176 155 76 98

881 358 631 429 364

754 471 595 311 287

500 574 306 189 257

411 419 760 211 253

1,313 3,630 2,828 2,387 1,422 973 807 -

277 145 309 -

LSSG-IVF ⋆-MinHash

133 122

241 224

270 233

181 179

287 243

946 721

379 111

346 3,416 3,397 497 570 2,447 29,785 152 954 1,044 21,292 92,693 136 142

1,069 1,065

602 606

346 2,826 433 239 303

Indexing time (s)

● YTB-Video and YTB-Audio [49] share identical topic labels. Following [52], feature vectors of one million video frames and five million audio samples are used for benchmarking. ● Wikipedia [18] has five million English paragraph embeddings, encoded via all-MiniLM-L6-v2 [61]. Labels are from Wikidata P31 (instance of) and P279 (subclass of) properties. ● YFCC-1M [38] is from an image embedding dataset with 10 million vectors [53]. Following [52], main experiments use the first one million subset and YFCC-10M serves for scalability test. We compute Spearman’s 𝜌 between label Jaccard distance 𝛿𝐿 and vector L2 distance 𝛿 𝑣 by label set size quartile. Seven datasets except Wikipedia have negligible overall correlation (⋃︀𝜌⋃︀ ≤ 0.021) and quartile-wise values < 0.05. Wikipedia shows a modest positive correlation (𝜌 = 0.15 overall, 0.038–0.176 by quartile). So, the evaluated workloads generally exhibit weak label–vector correlation, which LSSG does not assume. Complete results are in Appendix D.

487 426

● Pre-filtering only computes distance between the query vector and filtered vectors to obtain exact nearest neighbors. Note that UniFilter [66] is excluded due to code unavailability, and its reported performance is comparable to UNG. Curator [22] requires filters to be known a priori with at most two labels, conflicting with our query-time filter setup for arbitrary labels. Early LFANNS studies, including Filtered-Vamana [16], Stitched-Vamana [16], NHQ [58], and CAPS [17], are omitted for inferior performance to existing baselines like UNG [5] and ELI [69].

Competitors. We compare LSSG to ten competing LFANNS baselines using their official open-source implementations. For each baseline, we use the recommended building parameters, and sweep query parameters to obtain Pareto-optimal QPS–recall curves.

Table 4 lists the indexing performance under 16-thread parallelism.

● LSSG-IVF and LSSG-MinHash differ in similar label set selection. Unless stated otherwise, they both use 𝑇 = 9, 𝑚 = 16, 𝜔𝑐 = 128, with 𝜙 = 50,000 for IVF and (𝜏, 𝛽) = (64, 16) for MinHash. ● ACORN [40] is a predicate-agnostic index. It uses bitmaps to indicate which vector IDs can pass the filter. As suggested, we set its index parameters to 𝑀 = 16, 𝑀𝛽 = 32, 𝐿 = 256,𝛾 = 30. ● Packing is the best strategy in [32]. Following their settings, we set 𝑀 = 96, efCons = 256 for the optimal query performance. ● RWalks [1] uses label vector and hybrid distance to enhance HNSW indices. We use the recommended parameters in their paper, 𝑀 = 32, efCons = 200, 𝜏 = 0, and ℎ = 0.1. ● UNG [5] builds separate Vamana indices for all label sets and adds cross-group edges to ensure connectivity. We follow them and set 𝑀 = 32, 𝐿 = 100 with 𝛿 = 6 cross-group edges. ● ELI [69] builds multiple small indices with identical parameters. We choose 𝑀 = 16, efCons = 200 with elastic factor set to 0.2 as reported the most competitive in the paper. ● FAISS [23] and VSAG [72] serve as ANNS libraries and Milvus [57] and PGVector [25] serve as VDBMS with native filtering. HNSW (𝑀 = 32, efCons = 200) and k-means IVF (n_lists = 10,000) are evaluated.

(1) Index size. LSSG-IVF and LSSG-MinHash are the smallest (or among the most compact) indices across datasets. Averaged over datasets, compared with the most space-efficient baseline UNG, LSSG-IVF and LSSG-MinHash use 0.82x and 0.84x of UNG’s size, respectively. Specifically, MinHash adds signature and LSH-bucket storage, but it often probes far fewer label sets than IVF scanning, shrinking the insertion candidate set 𝑈 and producing a sparser final graph that offsets the overhead. So, LSSG-MinHash is smaller than LSSG-IVF on SIFT, GIST, and YTB-Audio. (2) Indexing time. LSSG-MinHash achieves the best or near-best indexing time on all datasets, averaging 0.78x UNG’s and 0.87x ELI’s time (the two fastest baselines). LSSG-IVF is also comparable to UNG and ELI. This is consistent with Sec. 3.3, where LSSG combines fast similar label set selection (IVF/MinHash) with dual-space pruning to reduce extensive vector-distance computations. (3) Sensitivity to label characteristics. LSSG’s indexing cost remains stable as ⋃︀𝐴⋃︀ increases, indicating it is dominated by local graph operations rather than combinatorial label enumeration. ACORN and UNG show similar insensitivity, but several baselines degrade. Packing is fast on YFCC-1M but less competitive when ⋃︀𝐴⋃︀ is small (e.g., LAION). RWalks is highly sensitive to ⋃︀𝐴⋃︀ and fails

6.2

RQ1: Indexing Analysis

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA LSSG-IVF SIFT Equality QPS

104

0.6

0.8

1.0

0.6

0.8

Containment QPS

101

1.0

0.6

Overlap QPS

0.6

0.8

1.0

0.8

Recall@10

1.0

0.6

ELI

0.6

0.8

1.0

Pre-filter Wikipedia

105

YFCC-1M 104

104

103

103 101

101

0.6

0.8

1.0

103

102

0.6

0.8

1.0

103

0.6

0.8

1.0 4 10

103

0.8

1.0

0.6

0.8

1.0 3 10

103

102

101

0.6

0.8

1.0

Recall@10

0.8

Recall@10

1.0

0.8

1.0

0.6

0.8

1.0

0.8

1.0

103

102

0.6

0.8

1.0

0.6

0.8

1.0

100

Recall@10

1.0

1.0 4 10

102

101

0.8

103

102

0.6

103

100

0.6

102

101

103

1.0

Recall@10

UNG YTB-Audio

102

101

0.8

RWalks YTB-Video

102

101

0.6

104 103

103

1.0

102

101

0.8

103

102

0.8

103

102

0.6

103

104

1.0 4

103

Packing

LAION

104

102

ACORN

TripClick

103

104

LSSG-MinHash

GIST

104

Ziqi Wang, Jingzhe Zhang, Shuo Shen, and Wei Hu

102 101

101

0.6

0.8

Recall@10

1.0

0.6

0.8

1.0

Recall@10

0.6

Recall@10

Figure 4: Queries Per Second (QPS) of LFANNS indices

103

0.6

0.8

102

1.0

104

103

0.8

Overlap DC

0.6

1.0

RWalks UNG

105

0.8

1.0

106

0.8

1.0

106

0.6

0.8

0.6

0.8

103

0.6

0.8

Recall@10

1.0

104

0.6

0.8

1.0

105

103

0.6

0.8

1.0

0.8

Recall@10

1.0

0.6

0.8

Recall@10

1.0

Containment Overlap

YTB-Audio

Wikipedia

104

105

102

10% 30% 50% 70% 90% 10% 30% 50% 70% 90% 10% 30% 50% 70% 90% 5 10% 30% 50% 70% 90% 10 104 R=0.85 104 104 103 103

102

103

101 10% 30% 50% 70% 90%

10% 30% 50% 70% 90%

102 10% 30% 50% 70% 90% 10% 30% 50% 70% 90%

R=0.80

103

0.6

LAION

103

102

104

103

1.0

ELI Equality

104

103

104

GIST

ACORN UNG

104

3 × 101

104

0.6

LSSG-IVF LSSG-MinHash

Wikipedia 4 × 101

103

0.6

ELI Oracle

YTB-Audio

Equality QPS

Equality DC

104

Containment DC

104

LAION

Containment QPS

ACORN Packing

GIST

0.6

0.8

Recall@10

1.0

R=0.85

103

Overlap QPS

LSSG-IVF LSSG-MinHash

102

6.3

Percentile

1 4 5

10% 30% 50% 70% 90%

Percentile

3 4

10 −

10% 30% 50% 70% 90%

Percentile

10 − 10 − 10 − 10 − 10 −

10% 30% 50% 70% 90%

10 − 10 − 10 − 10 − 10 −

Percentile

10 −

0− 4

0−

on YTB-Audio, Wikipedia, and YFCC-1M due to attribute-vector enhancement overhead. ELI is fast on small-to-medium label spaces but spends large space overhead to meet the elastic factor (about twice LSSG on the first four datasets, ∼20x on YTB-Video, and ∼90x on YTB-Audio), and fails on Wikipedia and YFCC-1M as index sharing scales exponentially with labels per set (e.g., 40 labels ⇒ 240 combinations). Overall, LSSG is less affected by label cardinality than prior LFANNS indices while consistently outperforming them.

10% 30% 50% 70% 90% 1

Percentile

10% 30% 50% 70% 90%

Figure 5: Distance Computations (DC) of LFANNS indices

Avg. Filter Ratio 1 1

103

10% 30% 50% 70% 90%

Percentile

10% 30% 50% 70% 90%

Percentile

Figure 6: QPS at 0.9 recall across different selectivity percentiles. Recall is adjusted and labeled in the top-right corner when no baseline attains 0.90 recall. The bottom row shows the average filter ratio for each percentile.

RQ2: LFANNS Query Performance

Overall comparison. Fig. 4 shows QPS–Recall@10 curves in one thread (below 0.5 recall are omitted), following [5, 32, 40, 69]. ELI and Packing lack native support for equality. To avoid adding extra index components, we evaluate them by reducing equality to a strengthened containment check (i.e., candidates must contain the query labels and have the same label set cardinality). (1) Equality. LSSG and UNG show the best performance. UNG is sometimes slightly more accurate (e.g., on GIST, YTB-Audio, and Wikipedia) for its denser static Vamana underlay with looser RNG pruning. This gap reflects the underlay choice (static Vamana vs. incremental HNSW), rather than the label-filtering mechanism.

LSSG achieves a comparable QPS–Recall frontier while supporting native incremental updates through HNSW-style insertion. (2) Containment. LSSG provides the strongest overall performance. Among the baselines, UNG is most competitive, while LSSG-MinHash achieves 2.95x faster on average at matched recall. The second best ELI is strong on SIFT–LAION, where LSSGMinHash achieves 1.10x faster on average. However, ELI cannot reach 0.9 recall on YTB-Video, and on YTB-Audio, LSSG-MinHash achieves 92.9x faster at 0.9 recall. Furthermore, ELI cannot be built on Wikipedia or YFCC-1M. Packing is competitive on SIFT, GIST, YTB-Audio, and YFCC-1M, but is less consistent overall, while RWalks and ACORN show limited performance.

Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification

LAION

102

Containment QPS

103

1.0

0.6

0.8

1.0

Wikipedia

0.6

0.8

1.0

104

101

0.6

0.8

103

1.0

0.6

0.8

Overlap QPS

103

101

0.6

0.8

Recall@10

1.0

0.6

0.8

Recall@10

1.0

0.5 0.6

0.8

1.0

0.8

1.0

103

101

1.0

0.5

0.6

0.8

Recall@10

1.0

0.8

1.0

LSSG-MinHash

|A| = 512

UNG

ELI

|A| = 2, 048

|A| = 8, 192

103 102

0.7

0.9 1.0 0.5 104

104

101

0.7

0.9 1.0 0.5

0.7

0.9 1.0 0.5

103

101

0.7

0.9 1.0 0.5

103 102

0.7

0.9 1.0 0.5

103

101

0.7

0.9 1.0

0.7

0.9 1.0

0.7

0.9 1.0

103

102

0.6

104

103

100

0.6

|A| = 128

102

101

LSSG-IVF

104

101

103

PGVector-IVF PGVector-HNSW

104

101

0.8

YTB-Audio

103

0.6

Milvus-IVF Milvus-HNSW

Equality QPS

VSAG-IVF VSAG-HNSW

Containment QPS

GIST

104

FAISS-IVF FAISS-HNSW

Overlap QPS

LSSG-IVF LSSG-MinHash

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA

0.7

102

0.9 1.0 0.5 103 102

101

0.5 0.6

0.8

Recall@10

0.7

0.9 1.0 0.5

Recall@10

0.7

0.9 1.0 0.5

Recall@10

0.7

0.9 1.0 0.5

Recall@10

1.0

Figure 8: Query performance w.r.t. varying label scale ⋃︀𝐴⋃︀

Figure 7: Comparison with ANNS libraries & vector databases

(3) Overlap. LSSG and ACORN provide the strongest overall performance. On Wikipedia, LSSG-IVF reaches 0.948 recall, exceeding ACORN’s peak recall of 0.909. ELI is competitive on SIFT–LAION, where LSSG-MinHash achieves 1.34x faster on average, but degrades on larger-label workloads. On YTB-Video, LSSG-MinHash achieves 84.1x faster at 0.7 recall. UNG is generally weaker. On SIFT– TripClick, where it reaches 0.9 recall, LSSG-MinHash achieves 7.3x faster on average, with the gap increasing to 99.8x on YFCC-1M at matched recall. Packing and RWalks do not reach 0.5 recall for overlap, with peak recall of only 0.41 and 0.32 on SIFT, respectively. (4) IVF vs. MinHash in LSSG. LSSG-IVF can be slightly better on a few workloads (notably containment/overlap on YTB-Audio, Wikipedia, and YFCC-1M). MinHash probing prioritizes high similarity label sets and may miss low similarity yet admissible ones, while IVF scanning evaluates more Jaccard distances and thus covers a broader set of allowed label sets—an effect that matters more with many labels and for overlap. Despite this trade-off, LSSGMinHash builds faster and retains strong overall query throughput. Approximation to the oracle label-filtered RNG. Fig. 5 compares distance computations (DC) with an oracle label-filtered RNG (Def. 5), implemented as HNSW on the fully filtered subset. For equality, LSSG and UNG stay closest to the oracle on GIST, LAION, and YTB-Audio. On Wikipedia, UNG is within about 10 DC of the oracle. For containment, LSSG is consistently closest, while Packing is occasionally competitive and UNG, ACORN, and RWalks generally require more DC or attain lower recall. ELI degrades on YTB-Audio and cannot be built on Wikipedia. For overlap, LSSG remains closest on GIST, LAION, and YTB-Audio, with ACORN closer only on Wikipedia. Overall, LSSG most consistently approximates the oracle, empirically supporting the connection between the stepwise advantage analyzed in Sec. 4 and reduced search effort. Appendix E reports results on the remaining datasets. Performance w.r.t. different selectivity. In Fig. 6, we sort queries by selectivity and split each workload into five equal-sized percentiles. LSSG is the most stable method across the entire selectivity spectrum. Averaged over datasets, for containment, LSSG-MinHash achieves 3.87x, 0.93x, 1.51x, 3.08x, and 8.48x QPS of UNG and 8.38x, 281x, 43.1x, 57.6x, and 5.29x of ELI at identical recall, grouped by

percentiles from 10%, 30%, 50%, 70% to 90%. For overlap, the improvements over UNG are 7.1x, 39.2x, 31.3x, 47.1x, and 52.7x, and over ELI are 80.2x, 77.3x, 23.5x, 15.7x, and 6.5x. See Appendix E for results on the remaining datasets. (1) High selectivity (10%). With small filtered subsets, quickly restricting search space can be effective. Thus, UNG is competitive for containment, whose cross-group edges connect a small number of relevant label sets, explaining the smaller 3.87x average containment gap. For overlap, ELI is strongly penalized by its multi-round containment reduction, yielding a large gap (80.2x). (2) Medium selectivity (30%–70%). UNG is competitive around 30%, where LSSG-MinHash achieves 0.93x QPS on average, but UNG degrades as selectivity decreases because its per-label set subindices become increasingly fragmented, and cross-group edges are less effective for traversing across many relevant label sets. ELI is most unstable for containment in this regime (LSSG/ELI peaks at 281x at 30% and stays at 43.1x–57.6x from 50% to 70%). Its heuristic may select a shared index that is much larger than the true filtered subset, so many visited candidates are filtered out. LSSG remains stable by tiered navigation to keep progress within label-consistent regions and completing the search with a single in-filter traversal. (3) Low selectivity (90%). With large filtered subsets (common for overlap), label-agnostic traversal is less penalized, making ACORN more competitive, especially on Wikipedia. UNG becomes particularly weak for overlap and the gap grows to 52.7x, reflecting limited cross-label connectivity. ELI’s overlap gap narrows to 6.5x, suggesting multi-round overhead is less harmful when each round is only weakly selective. LSSG remains faster due to one-pass traversal. Comparison with ANNS libraries and vector databases. Fig. 7 compares LSSG with FAISS, VSAG, Milvus, and PGVector on GIST, LAION, YTB-Audio, and Wikipedia. (1) At the library level, FAISS cannot reach 0.95 recall for equality or containment on any dataset, with maximum recalls of 0.002–0.79 and 0.13–0.90, respectively. VSAG reaches high recall more often, but drops to 0.19 and 0.46 QPS at 0.95 recall for equality and containment on Wikipedia, and remains below 0.95 for equality on YTB-Audio. For overlap, FAISS remains below 0.95 recall on Wikipedia and YTB-Audio, whereas VSAG reaches 0.95 recall at only 27–52 QPS. (2) At the database level, the best Milvus and PGVector variants reach at least 0.95 recall for containment, but achieve only 16–41 and 0.6–13 QPS,

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA LSSG-MinHash

Uniform

Poisson

UNG

T1 100

104

103

ELI

Multinomial

103

102

0.8

1.0

Containment QPS

0.6

0.8

1.0

103

102

0.8

0.6

0.8

1.0

103

Overlap QPS

102

1.0

0.8

1.0

Recall@10

0.8

1.0

0.6

0.8

1.0 103

102

0.6

0.8

1.0

Recall@10

0.6

0.8

1.0

Recall@10

0.8

1.0

0.8

1.0

Recall@10

T9 Candidate

−5

−4

−3

−2

−5

−4

−3

−2

7 0.1

10 ×10 ×10 ×10 ×10 1.3 8.4 2.8 1.6

−6

−5

−4

−3

−6

−5

−4

−3

−2

−5

−3

−2

6 0.1

0 0 0 0 0 ×1 ×1 ×1 ×1 ×1 2.0 2.4 1.4 6.9 7.3

−6

−5

−4

−3

−6

−5

−4

−3

−2

−5

−3

−2

6 0.1

0 0 0 0 0 ×1 ×1 ×1 ×1 ×1 2.0 2.4 1.4 6.9 7.3

75 50 25

10 ×10 ×10 ×10 9.0 5.6 2.8

0 0 0 0 0 ×1 ×1 ×1 ×1 ×1 2.0 8.7 4.5 2.5 2.0

75 50 25 0 2 − 3 3 9 4 0.4 0.7 0.7 0.8 10

Filter Ratio

× 2.5

−2

3 3 9 4 0.4 0.7 0.7 0.8

Filter Ratio

0 0 0 0 ×1 ×1 ×1 ×1 3.6 7.6 3.4 9.7

Filter Ratio

0 0 0 0 ×1 ×1 ×1 ×1 3.6 7.6 3.4 9.7

Filter Ratio

Figure 11: Tier usage on LAION. Each bar decomposes either visited vertices or final candidates, grouped by filter ratio.

00 32

QPS

00 30 0 80

QPS

0 70 0 55

75 0 58

0 .25 .5 .75 1

0 56 0

.6 .7 .8 .9 1.0

Fraction of data inserted

0. 85

0. 86

QPS

0 65

.6 .7 .8 .9 1.0 0. 87

5 0

0 .25 .5 .75 1

Inversion fraction

T7 T8 YTB-Audio

00 30 6 0. 96 50 27

0. 96 75

0 .25 .5 .75 1

0. 95

0 0 31

0. 87

29 30 31 0 0 0 0. 0. 98 98 50 75

.6 .7 .8 .9 1.0

Fraction of data inserted

0. 86

0 .25 .5 .75 1

Visited

00 25

2 0. 96 0. 95 50 50 0

0. 95

0 45

0. 97

5 0 5 75 50 25

.6 .7 .8 .9 1.0

4 00 0. 96

16 00 0. 99 94

5 92 90

0. 99 0. 97

0. 98 0. 98

.6 .7 .8 .9 1.0

0. 95

00 20

0. 96

18 00 0. 99 96

0. 99

Equality Recall@10

99 0. 97

Containment Recall@10 0.

0. 96 0. 98

Overlap Recall@10

0 .25 .5 .75 1

× 2.5

LSSG-IVF (Recall@10) LSSG-IVF (Init. Recall) LSSG-IVF (QPS) LSSG-MinHash (Recall@10) LSSG-MinHash (Init. Recall) LSSG-MinHash (QPS) LAION YTB-Audio Unseen Labels Frequency Shift Unseen Labels Frequency Shift

0 5 − −4 −3 −2 7 0.1 10 ×10 ×10 ×10 9.0 5.6 2.8

0.6

T4 Candidate

100

Figure 9: Performance w.r.t. different label distributions

.6 .7 .8 .9 1.0

T3 LAION

100

0.6

103

Visited

0 5 − −4 −4 −3 −2 10 ×10 ×10 ×10 ×10 1.3 8.4 2.8 1.6

103

101

0.6

102

1.0

103

0.8

103

102

0.6

Equality Usage (%)

Equality QPS

104

Containment Usage (%)

Zipf

Overlap Usage (%)

LSSG-IVF 104

Ziqi Wang, Jingzhe Zhang, Shuo Shen, and Wei Hu

0 .25 .5 .75 1

Inversion fraction

Figure 10: Insertion-drift evaluation on LAION and YTBAudio with 𝜔𝑠 = 500. Dashed lines mark pre-insertion recall under the initial index. Dotted lines show QPS.

respectively. LSSG maintains high recall with substantially higher throughput across all three semantics. Overall, integrating filtering into graph traversal yields a more consistent LFANNS query than library-level filtering or database-level query processing. Results on the remaining datasets and indexing costs are in Appendix E. Performance w.r.t. varying label scale. Fig. 8 increases the label space (⋃︀𝐴⋃︀) and unique label sets (422,427 → 972,650) of LAION. LSSG is consistently superior, as tier-wise distance bounds enforce label constraints without enumerating label combinations. ELI fails at ⋃︀𝐴⋃︀ = 8,192 due to rapidly growing index-sharing search space. UNG degrades due to massive fragmented groups. Performance w.r.t. different label distributions. Following [5], we generate Uniform, Poisson, and Multinomial label distributions on LAION. Fig. 9 compares the strongest indices LSSG, UNG, and ELI. (1) LSSG performs best, as tiered traversal depends on label set distance rather than a particular frequency shape, maintaining stable navigation under all distributions. (2) For UNG, equality degrades under Uniform/Multinomial, since more diverse label sets spread the edge budget over more groups and weaken within-group connectivity. (3) ELI is competitive for containment/overlap but

unstable for equality (0.69 under Zipf and below 0.1 under others), due to equality-incompatible design and distribution sensitivity. Performance w.r.t. label insertion drift. Fig. 10 evaluates unseenlabel insertion and frequency inversion after indexing the first 50% of each dataset. Under unseen-label insertion, containment recall changes by at most 0.014 on LAION and 0.006 on YTB-Audio, while equality and overlap recalls decrease by at most 0.017. Under frequency inversion, LSSG-MinHash remains stable, where LSSG-IVF drops by up to 0.017 on YTB-Audio due to frequency-based tier assignment. This robustness comes from LSSG’s tiered thresholds. Each insertion follows the same label similarity constraints and updates only the affected local neighborhoods. MinHash further improves stability through frequency-independent candidate selection. Both variants remain nearly unchanged on LAION. Insertion throughput reaches 3,010–5,668 vectors/s, with index size growing from 130–212 MB and 520–841 MB.

6.4

RQ3: Micro Benchmarks

We dissect LSSG’s key components and quantify their impact on index size, time, and query efficiency: (1) tier-usage decomposition and parameter sensitivity, (2) filter-valid expansion ratio, (3) label set diversification (LabelPrune), (4) similar label set selection (IVF scanning vs. MinHash probing), and (5) scalability to large label space. Appendix E validates more label set distance sensitivity. Tier use and sensitivity. Fig. 11 decomposes traversal by tier. More selective filters shift visits and final candidates toward upper tiers, confirming the active usage of label-consistent edges. For containment and overlap, fewer than ten queries per dataset use only the label-agnostic bottom tier. Fig. 12(a) further shows that 𝑇 = 2 is insufficient at high recall, whereas intermediate tiers substantially improve accuracy. Larger 𝑚 and 𝜔𝑐 improve recall but incur higher indexing costs with diminishing returns. Fig. 12(b) confirms robust QPS–Recall@𝑘 for 𝑘 ∈ {1, 10, 50, 100, 500} and varying threads.

Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification Varying ωc

Varying m

ωc

0.85

0.90

Recall@k

453 Size (MB) 302 151 0 102 203 305 Time (s) 8 16

0.95

1.00

103

QPS

0.95

m=32 m=40

102

LAION

0.80

0.85

YTB-Audio

0.90

Recall@10

0.95

102 0.80

1.00

IVF IVF w/o MinHash MinHash w/o

LAION

(a) Index parameters Varying k Varying Thread Number

103

0.85

0.90

Recall@10

0.95

1.00

10 00

QPS 0.90

Recall@k

315 Size (MB) 210 105 0 135 269 404 Time (s) 32 64 128 256 512

m=8 m=16 m=24

0.85

102 1.00 0.80

Time (s)

Ovlp-MinHash Ovlp-MinHash w/o

Ovlp-IVF Ovlp-IVF w/o

YTB-Audio

LAION

0.95

ωc=256 ωc=512

QPS

0.90

Recall@k

349 Size (MB) 233 116 0 71 142 213 Time (s) 2 3

102 1.00 0.80

0.85

T =9 T =12

Cont-MinHash Cont-MinHash w/o

103

ωc=32 ωc=64 ωc=128

0.80

T =2 T =3 T =6

Size (MB)

101

QPS

103

102

Cont-IVF Cont-IVF w/o

50 0

Varying T 103

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA

YTB-Audio

104

0.90

Recall@10

0.95

1.00

φ =50

0.75

0.50

0.25

0.00

T1 T2 T3 T4 T5 T6 T7 T8 T9

0.00

Tier

Figure 13: Filter-valid expansion ratio on LAION. Tier becomes stricter and higher ratio means fewer ineffective scans.

Filter-valid expansion ratio. Fig. 13 shows the fraction of scanned tier neighbors satisfying the query filter, empirically reflecting the stepwise probability analyzed in Sec. 4. The ratio generally increases with tier strictness, yet tiers 6–7 show minor drops since stricter tiers connect more similar label sets, which can still differ in a few labels and fail the exact filter. From tier 1 to tier 9, the ratio rises on LAION/YTB-Audio from 0.12/0.02 to 1.0/1.0 for containment and from 0.62/0.08 to 1.0/1.0 for overlap. Equality remains 1.0 since the search only contains exact matches. Thus, lower tiers support broad exploration, while stricter tiers increase useful expansions. Effectiveness of label set diversification. LabelPrune removes redundant neighbors with highly similar label sets, reducing candidate processing and edge storage while preserving cross-label connectivity. As Fig. 14 shows, the query impact is small. At 0.9 recall, QPS drops by only ∼1% on LAION and < 10% on YTB-Audio, while building cost decreases substantially. On LAION, LabelPrune reduces index size by 2% (LSSG-IVF) and 10% (LSSG-MinHash), and indexing time by 51% and 33%, respectively. This aligns with Alg. 2, where a sparser intermediate graph shrinks the candidate set 𝑈 , boosting candidate selection that dominates insertion time.

103

YTB-Audio 0.90

Recall@10

0.95

1.00

0.80

0.85

0.90

0.95

1.00

0.90

0.95

1.00

Recall@10

103

YTB-Audio 0.90

Recall@10

0.95

φ =50 φ =500 φ =5,000 φ =50,000 φ =500,000

1.00

0.80

0.85

Recall@10

0.00

φ =500,000

0.25

0.00

0.50

0.25 T1 T2 T3 T4 T5 T6 T7 T8 T9

0.50

0.25

0.75

0.50

Tier

102 LAION 0.80 0.85

0.75

1.00

0.85

103

0.75

1.00

Size (MB)

YTB-Audio Valid Ratio

1.00

T1 T2 T3 T4 T5 T6 T7 T8 T9

0.75

0.50

T1 T2 T3 T4 T5 T6 T7 T8 T9

0.75

φ =50,000

LAION 0.80

Overlap QPS

1.00

φ =5,000

103

Overlap

T1 T2 T3 T4 T5 T6 T7 T8 T9

1.00

Containment

T1 T2 T3 T4 T5 T6 T7 T8 T9

LAION Valid Ratio

1.00

Equality

Containment QPS

Figure 12: Parameter sensitivity on LAION

φ =500

QPS

0.85

QPS

1.00 0.80

0.95

(b) Output size 𝑘 and query threads

0.90

Recall@k

thread=8 thread=16

0.85

k=100 k=500

thread=1 thread=2 thread=4

103

Time (s)

k=1 k=10 k=50

LAION

YTB-Audio

102 0.80

Figure 14: LSSG-IVF/MinHash performance w/o LabelPrune in the containment (Cont.) and overlap (Ovlp.) semantics

QPS

103

LAION

YTB-Audio

Figure 15: Performance w.r.t. varying IVF scanning budget 𝜙

IVF scanning budget 𝜙. Fig. 15 varies 𝜙, the number of label bitmaps scanned to form ℒ𝑞 in Alg. 3. For reference, ⋃︀ℒ⋃︀ = 62,066 on LAION and ⋃︀ℒ⋃︀ = 498,445 on YTB-Audio. (1) Increasing 𝜙 improves QPS first, and then yields diminishing gains once IVF approaches a near-full scan. On LAION, at 0.9 recall, QPS increases from 1,098 → 2,008 for containment and 2,049 → 2,770 for overlap with 𝜙 = 5,000 → 50,000, while 𝜙 = 500,000 brings little further benefit (1,803 and 2,616). On YTB-Audio, QPS similarly saturates: 2,473 → 3,170 → 3,239 for containment and 268 → 802 → 838 for overlap with 𝜙 = 5,000 → 50,000 → 500,000. (2) Larger 𝜙 increases bitmap unions and Jaccard computations during insertion and can add more out-neighbors. On YTB-Audio, indexing time grows as 𝜙 increases (785 → 946 → 1,613 s), while index size grows mildly (997 → 1,069 → 1,071 MB). (3) A practical knee point. For large label scales, moderate 𝜙 can be near-optimal. On YTB-Audio, 𝜙 = 50,000 is close to 𝜙 = 500,000 in QPS at 0.9 recall (3,170 vs. 3,239; 802 vs. 838) but shortens indexing time by 41% (946 vs. 1,613). MinHash probing analysis. Fig. 16 shows the analysis on YTBAudio for Sec. 3.2 by varying (𝜏, 𝛽) in Eq. (1). (1) Reducing the probing selectivity by decreasing 𝜏 or increasing 𝛽 on the diagonal

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA

Ziqi Wang, Jingzhe Zhang, Shuo Shen, and Wei Hu

Containment: Recall@10 0.98

512 .8243 .8286 .9027 .9638 .9788

Containment: QPS 638 512 625.86 627.00 471.96 377.27 387.83

256 .8248 .8872 .9577 .9797 .9787

256 638.01 480.69 428.01 364.09 359.30

128 .8666 .9477 .9781 .9815 .9808

128 555.19 439.99 392.49 357.08 368.49

64 .9357 .9682 .9797 .9791 NaN

64 457.36 414.61 353.64 388.43 NaN

We propose LSSG, a multi-tier proximity graph that addresses two key LFANNS challenges: consistency across query semantics and robustness to diverse label characteristics. LSSG enforces label constraints via distribution-agnostic stratification by label set similarity, and scales to large label space with efficient similar label set selection and dual-space pruning. We derive lower bounds on filter-valid next-hop probabilities under explicit label models, explaining how stricter tiers reduce ineffective expansions. Experiments across datasets, label scales and distributions, selectivity regimes, and insertion-drift settings confirm fast query in different semantics and robust incremental construction. Future work includes extending from label sets to sparse vectors for dense–sparse hybrid search and supporting richer filters such as regular expression.

32 409.16 373.74 394.94 NaN NaN 128 0.82 8 16 32 64 128 353 Overlap: Recall@10 Overlap: QPS 0.96 438 512 .6268 .6326 .7209 .8978 .9556 512 425.80 425.19 319.31 262.55 272.40

32 .9683 .9770 .9798 NaN 8 16 32 64

256 .6299 .7049 .8786 .9518 .9557

256 438.01 343.93 293.94 260.79 267.02

128 .6711 .8504 .9453 .9542 .9571

128 336.61 294.32 271.46 266.60 258.26

64 .8164 .9104 .9577 .9547 NaN

64 311.74 261.50 269.82 269.64 NaN

32 .9208 .9547 .9559 NaN 8 16 32 64

NaN

32 285.50 269.67 278.01 NaN NaN 128 0.63 8 16 32 64 128 258 Index Size (MB) Indexing Time (s) 1534 4483 1015 1178 1481 1534 512 529 503 549 669 1606

512

933

256

865

953

1177

1289

1394

256

528

530

649

1579

2578

128

840

1023

1152

1241

1361

128

522

611

1347

2086

4483

917

1065

1162

1225

NaN

600

728

1915

4162

NaN

32 1019 8

1120

1157

NaN

750

1469

3851

NaN

128 840

128 503

Acknowledgments

Figure 16: Performance w.r.t. varying MinHash 𝜏, 𝛽

Datasets

Indices

QPS-Recall@10

Size (MB) Time (s)

0.85

0.90 0.95

Packing LSSG-IVF ⋆-MinHash

2,826 239 303

145 379 111

1,160 659 8,788 4,120 8,393 3,346

313 880 766

Packing YFCC-10M LSSG-IVF ⋆-MinHash

2,424 2,413 2,935

4,409 7,289 2,729

12 491 414

56 55

YFCC-1M

246 207

We thank all reviewers for their valuable feedback. This work was supported in part by the National Natural Science Foundation of China (No. 62676187) and the Postgraduate Research & Practice Innovation Program of Jiangsu Province (No. 26CXJH0355).

References

Table 5: Performance with large-scale labels Indexing

Conclusion

from upper left to bottom right to get higher collision probability increases recall but often lowers QPS due to longer traversals. (2) Overly selective probing removes edges between moderately similar label sets, which are more important for overlap. For example, at 𝛽 = 8, increasing 𝜏 from 32 to 512 reduces recall by 0.14 for containment and 0.29 for overlap. (3) Index size increases with 𝛽, and can be non-monotonic in 𝜏 when 𝜏 ≤ 16 because larger 𝜏 sparsifies the graph (smaller) and lengthens signatures (larger). Indexing time increases with smaller 𝜏 and larger 𝛽 since more collisions make larger candidate pools and more 𝛿𝐿 computations. Index scalability. Table 5 tests scalability on YFCC-10M (200,386 labels and ∼4M unique label sets) using released 10,000 containment queries. (1) MinHash improves index scalability. LSSG-MinHash reduces indexing time by 62% relative to LSSG-IVF, with a 21% larger index size. Its QPS remains close (gap < 16% at 0.9 recall). (2) As dataset size increases, index size scales as 𝑂(⋃︀𝒱⋃︀) and indexing time as 𝑂(⋃︀𝒱⋃︀ log ⋃︀𝒱⋃︀). Concretely, LSSG-MinHash shows a 9.6x size increase and a 24.5x indexing-time increase, consistent with Sec. 5. (3) For other baselines, they hit scalability limits. UNG reaches only 0.6 peak recall at 0.93 QPS. ELI fails at this label scale due to exponential index-sharing enumeration. Packing builds in reasonable time but remains non-competitive in QPS.

[1] Anas Ait Aomar, Karima Echihabi, Marco Arnaboldi, Ioannis Alagiannis, Damien Hilloulin, and Manal Cherkaoui. 2025. RWalks: Random Walks as Attribute Diffusers for Filtered Vector Search. Proc. ACM Manag. Data 3, 3 (2025), 26 pages. [2] Ceyhun Burak Akgül, Daniel L. Rubin, Sandy Napel, Christopher F. Beaulieu, Hayit Greenspan, and Burak Acar. 2011. Content-Based Image Retrieval in Radiology: Current Status and Future Directions. Journal of Digital Imaging 24, 2 (2011), 208–222. [3] Laurent Amsaleg and Hervé Jégou. 2026. Evaluation of Approximate Nearest Neighbors: Large Datasets. http://corpus-texmex.irisa.fr/. [4] A.Z. Broder. 1997. On the resemblance and containment of documents. In SEQUENCES. IEEE, Positano, Italy, 21–29. [5] Yuzheng Cai, Jiayang Shi, Yizhuo Chen, and Weiguo Zheng. 2024. Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 2, 6 (2024), 27 pages. [6] Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021. SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search. In NeurIPS. Curran Associates Inc., Red Hook, NY, USA, 14 pages. [7] Tingyang Chen, Cong Fu, Kun Wang, Xiangyu Ke, Yunjun Gao, Wenchao Zhou, Yabo Ni, and Anxiang Zeng. 2025. Maximum Inner Product is Query-Scaled Nearest Neighbor. Proc. VLDB Endow. 18, 6 (2025), 1770–1783. [8] Yangshen Deng, Zhengxin You, Long Xiang, Qilong Li, Peiqi Yuan, Zhaoyang Hong, Yitao Zheng, Wanting Li, Runzhong Li, Haotian Liu, Kyriakos Mouratidis, Man Lung Yiu, Huan Li, Qiaomu Shen, Rui Mao, and Bo Tang. 2025. AlayaDB: The Data Foundation for Efficient and Effective Long-context LLM Inference. In SIGMOD-Companion. ACM, Berlin, Germany, 364–377. [9] Wenqi Fan, Yujuan Ding, Liangbo Ning, Shijie Wang, Hengyun Li, Dawei Yin, Tat-Seng Chua, and Qing Li. 2024. A Survey on RAG Meeting LLMs: Towards Retrieval-Augmented Large Language Models. arXiv:2405.06211 [cs.CL] [10] Glenn Fowler, Landon Curt Noll, Kiem-Phong Vo, Donald E. Eastlake 3rd, and Tony Hansen. 2026. The FNV Non-Cryptographic Hash Algorithm. RFC 9923. https://www.rfc-editor.org/info/rfc9923 [11] Cong Fu, Changxu Wang, and Deng Cai. 2022. High Dimensional Similarity Search With Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility. IEEE Trans. Pattern Anal. Mach. Intell. 44, 8 (2022), 4139–4150. [12] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast Approximate Nearest Neighbor Search with the Navigating Spreading-out Graph. Proc. VLDB Endow. 12, 5 (2019), 461–474. [13] Jianyang Gao, Yutong Gou, Yuexuan Xu, Yongyi Yang, Cheng Long, and Raymond Chi-Wing Wong. 2025. Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 3, 3 (2025), 26 pages. [14] Jianyang Gao and Cheng Long. 2024. RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 2, 3 (2024), 27 pages. [15] Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, Meng Wang, and Haofen Wang. 2024. Retrieval-Augmented Generation

Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification

for Large Language Models: A Survey. arXiv:2312.10997 [cs.CL] [16] Siddharth Gollapudi, Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy, Nikit Begwani, Swapnil Raz, Yiyong Lin, Yin Zhang, Neelam Mahapatro, Premkumar Srinivasan, Amit Singh, and Harsha Vardhan Simhadri. 2023. FilteredDiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters. In WWW. ACM, Austin, TX, USA, 3406–3416. [17] Gaurav Gupta, Jonah Yi, Benjamin Coleman, Chen Luo, Vihan Lakshman, and Anshumali Shrivastava. 2023. CAPS: A Practical Partition Index for Filtered Similarity Search. arXiv:2308.15014 [cs.IR] [18] Huggingface. 2026. Wikipedia-22-12-en Embeddings with all-MiniLM-L6v2. https://huggingface.co/datasets/maloyan/wikipedia-22-12-en-embeddingsall-MiniLM-L6-v2. [19] Kyung Hoon Hwang, Haejun Lee, Geon Koh, Debra Willrett, and Daniel L. Rubin. 2017. Building and Querying RDF/OWL Database of Semantically Annotated Nuclear Medicine Images. Journal of Digital Imaging 30, 1 (2017), 4–10. [20] Patrick Iff, Paul Bruegger, Marcin Chrapek, David Kochergin, Maciej Besta, and Torsten Hoefler. 2026. Benchmarking Filtered Approximate Nearest Neighbor Search Algorithms on Transformer-based Embedding Vectors. arXiv:2507.21989 [cs.DB] [21] Mengxu Jiang, Zhi Yang, Fangyuan Zhang, Guanhao Hou, Jieming Shi, Wenchao Zhou, Feifei Li, and Sibo Wang. 2025. DIGRA: A Dynamic Graph Indexing for Approximate Nearest Neighbor Search with Range Filter. Proc. ACM Manag. Data 3, 3 (2025), 26 pages. [22] Yicheng Jin, Yongji Wu, Wenjun Hu, Bruce M. Maggs, Jun Yang, Xiao Zhang, and Danyang Zhuo. 2026. Curator: Efficient Vector Search with Low-Selectivity Filters. arXiv:2601.01291 [cs.DB] [23] Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2021. Billion-Scale Similarity Search with GPUs. IEEE Trans. Big Data 7, 3 (2021), 535–547. [24] Herve Jégou, Matthijs Douze, and Cordelia Schmid. 2011. Product Quantization for Nearest Neighbor Search. IEEE Trans. Pattern Anal. Mach. Intell. 33, 1 (2011), 117–128. [25] Andrew Kane. 2026. pgvector: Open-source vector similarity search for Postgres. https://github.com/pgvector/pgvector. [26] Vladimir Karpukhin, Barlas Oğuz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen tau Yih. 2020. Dense Passage Retrieval for OpenDomain Question Answering. arXiv:2004.04906 [cs.CL] [27] Yifan Lei, Qiang Huang, Mohan Kankanhalli, and Anthony K. H. Tung. 2020. Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring. In SIGMOD. ACM, Portland, OR, USA, 2589–2599. [28] Binhong Li, Xiao Yan, and Shangqi Lu. 2026. Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search. arXiv:2510.05975 [cs.DS] [29] Jie Li, Haifeng Liu, Chuanghua Gui, Jianyu Chen, Zhenyuan Ni, Ning Wang, and Yuan Chen. 2018. The Design and Implementation of a Real Time Visual Search System on JD E-commerce Platform. In Middleware. ACM, Rennes, France, 9–16. [30] Mocheng Li, Xiao Yan, Baotong Lu, Yue Zhang, James Cheng, and Chenhao Ma. 2025. Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study. Proc. ACM Manag. Data 3, 6 (2025), 26 pages. [31] Zhaoheng Li, Silu Huang, Wei Ding, Yongjoo Park, and Jianjun Chen. 2025. SIEVE: Effective Filtered Vector Search with Collection of Indexes. Proc. VLDB Endow. 18, 11 (2025), 4723—-4736. [32] Jiarui Luo, Miao Qiao, Chaoji Zuo, and Dong Deng. 2025. Tag-Filtered Approximate Nearest Neighbor Search. In ICDE. IEEE, Hong Kong, China, 3642–3654. [33] Vasilis Mageirakos, Bowen Wu, and Gustavo Alonso. 2025. Cracking Vector Search Indexes. Proc. VLDB Endow. 18, 11 (2025), 3951–3964. [34] Yu A. Malkov and D. A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Trans. Pattern Anal. Mach. Intell. 42, 4 (2020), 824–836. [35] Jason Mohoney, Anil Pacaci, Shihabur Rahman Chowdhury, Umar Farooq Minhas, Jeffery Pound, Cedric Renggli, Nima Reyhani, Ihab F. Ilyas, Theodoros Rekatsinas, and Shivaram Venkataraman. 2024. Incremental IVF Index Maintenance for Streaming Vector Search. arXiv:2411.00970 [cs.DB] [36] Jason Mohoney, Anil Pacaci, Shihabur Rahman Chowdhury, Ali Mousavi, Ihab F. Ilyas, Umar Farooq Minhas, Jeffrey Pound, and Theodoros Rekatsinas. 2023. HighThroughput Vector Similarity Search in Knowledge Graphs. Proc. ACM Manag. Data 1, 2 (2023), 25 pages. [37] Marius Muja and David G. Lowe. 2014. Scalable Nearest Neighbor Algorithms for High Dimensional Data. IEEE Trans. Pattern Anal. Mach. Intell. 36, 11 (2014), 2227–2240. [38] BigANN Organizers. 2026. NeurIPS’23 Competition Track: Big-ANN. https://bigann-benchmarks.com/neurips23.html. [39] James Jie Pan, Jianguo Wang, and Guoliang Li. 2024. Survey of Vector Database Management Systems. VLDB J. 33 (2024), 1591–1615. [40] Liana Patel, Peter Kraft, Carlos Guestrin, and Matei Zaharia. 2024. ACORN: Performant and Predicate-Agnostic Search over Vector Embeddings and Structured Data. Proc. ACM Manag. Data 2, 3 (2024), 27 pages. [41] Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang, and Jianliang Xu. 2023. Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases. Proc. ACM Manag. Data 1, 1 (2023), 27 pages.

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA

[42] Zhencan Peng, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. 2025. Dynamic Range-Filtering Approximate Nearest Neighbor Search. Proc. VLDB Endow. 18, 10 (2025), 13 pages. [43] Jeffrey Pennington, Richard Socher, and Christopher Manning. 2014. GloVe: Global Vectors for Word Representation. In EMNLP. ACM, Doha, Qatar, 1532– 1543. [44] Steven T. Piantadosi. 2014. Zipf’s Word Frequency Law in Natural Language: A Critical Review and Future Directions. Psychonomic Bulletin & Review 21, 5 (2014), 1112–1130. [45] Runwen Qiu and Jing Tang. 2025. Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph. Proc. ACM Manag. Data 3, 6 (2025), 26 pages. [46] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. 2021. Learning Transferable Visual Models from Natural Language Supervision. In ICML. PMLR, Virtual, 8748–8763. [47] Navid Rekabsaz, Oleg Lesota, Markus Schedl, Jon Brassey, and Carsten Eickhoff. 2021. TripClick: The Log Files of a Large Health Web Search Engine. In SIGIR. ACM, Virtual, 2507–2513. [48] Navid Rekabsaz, Oleg Lesota, Markus Schedl, Jon Brassey, and Carsten Eickhoff. 2026. TripClick: The Log Files of a Large Health Web Search Engine. https: //tripdatabase.github.io/tripclick/. [49] Google Research. 2026. YouTube-8M: A Large and Diverse Labeled Video Dataset for Video Understanding Research. https://research.google.com/youtube8m/ index.html. [50] Christoph Schuhmann. 2021. LAION-400-Million Open Dataset. https://laion.ai/ blog/laion-400-open-dataset/. [51] Gaurav Sehgal and Semih Salihoğlu. 2025. NaviX: A Native Vector Index Design for Graph DBMSs With Robust Predicate-Agnostic Search Performance. Proc. VLDB Endow. 18, 11 (2025), 4438–4450. [52] Jiayang Shi, Yuzheng Cai, and Weiguo Zheng. 2025. Filtered Approximate Nearest Neighbor Search: A Unified Benchmark and Systematic Experimental Study [Experiment, Analysis & Benchmark]. arXiv:2509.07789 [cs.DB] [53] Harsha Vardhan Simhadri, Martin Aumüller, Amir Ingber, Matthijs Douze, George Williams, Magdalen Dobson Manohar, Dmitry Baranchuk, Edo Liberty, Frank Liu, Ben Landrum, et al. 2024. Results of the Big ANN: NeurIPS’23 Competition. arXiv:2409.17424 [cs.IR] [54] Yufei Tao, Ke Yi, Cheng Sheng, and Panos Kalnis. 2009. Quality and Efficiency in High Dimensional Nearest Neighbor Search. In SIGMOD. ACM, Providence, RI, USA, 563–576. [55] Yao Tian, Xi Zhao, and Xiaofang Zhou. 2024. DB-LSH 2.0: Locality-Sensitive Hashing With Query-Based Dynamic Bucketing. IEEE Trans. Knowl. Data Eng. 36, 3 (2024), 1000–1015. [56] Michael Tschannen, Alexey Gritsenko, Xiao Wang, Muhammad Ferjad Naeem, Ibrahim Alabdulmohsin, Nikhil Parthasarathy, Talfan Evans, Lucas Beyer, Ye Xia, Basil Mustafa, Olivier Hénaff, Jeremiah Harmsen, Andreas Steiner, and Xiaohua Zhai. 2025. SigLIP 2: Multilingual Vision-Language Encoders with Improved Semantic Understanding, Localization, and Dense Features. arXiv:2502.14786 [cs.CV] [57] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, Kun Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, and Charles Xie. 2021. Milvus: A Purpose-Built Vector Data Management System. In SIGMOD. ACM, Xi’an, China, 2614–2627. [58] Mengzhao Wang, Lingwei Lv, Xiaoliang Xu, Yuxiang Wang, Qiang Yue, and Jiongkang Ni. 2023. An Efficient and Robust Framework for Approximate Nearest Neighbor Search with Attribute Constraint. In NeurIPS, Vol. 36. Curran Associates, Inc., New Orleans, LA, USA, 15738–15751. [59] Mengzhao Wang, Boyu Tan, Yunjun Gao, Hai Jin, Yingfeng Zhang, Xiangyu Ke, Xiaoliang Xu, and Yifan Zhu. 2025. Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Search. arXiv:2508.01405 [cs.DB] [60] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search. Proc. VLDB Endow. 14, 11 (2021), 1964–1978. [61] Wenhui Wang, Furu Wei, Li Dong, Hangbo Bao, Nan Yang, and Ming Zhou. 2020. MiniLM: Deep Self-Attention Distillation for Task-Agnostic Compression of Pre-Trained Transformers. arXiv:2002.10957 [cs.CL] [62] Ziqi Wang, Jingzhe Zhang, and Wei Hu. 2025. WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 3, 6 (2025), 27 pages. [63] Chuangxian Wei, Bin Wu, Sheng Wang, Renjie Lou, Chaoqun Zhan, Feifei Li, and Yuanzhe Cai. 2020. AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data. Proc. VLDB Endow. 13, 12 (2020), 3152–3165. [64] Jiuqi Wei, Botao Peng, Xiaodong Lee, and Themis Palpanas. 2024. DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search. Proc. VLDB Endow. 17, 9 (2024), 2241–2254. [65] Jiadong Xie, Jeffrey Xu Yu, and Yingfan Liu. 2025. Graph Based K-Nearest Neighbor Search Revisited. ACM Trans. Database Syst. 50, 4 (2025), 30 pages.

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA

Ziqi Wang, Jingzhe Zhang, Shuo Shen, and Wei Hu

[66] Jiadong Xie, Jeffrey Xu Yu, Siyi Teng, and Yingfan Liu. 2025. Beyond Vector Search: Querying With and Without Predicates. Proc. ACM Manag. Data 3, 6 (2025), 26 pages. [67] Yuexuan Xu, Jianyang Gao, Yutong Gou, Cheng Long, and Christian S. Jensen. 2024. iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search. Proc. ACM Manag. Data 2, 6 (2024), 26 pages. [68] Yuming Xu, Hengyu Liang, Jin Li, Shuotao Xu, Qi Chen, Qianxi Zhang, Cheng Li, Ziyue Yang, Fan Yang, Yuqing Yang, Peng Cheng, and Mao Yang. 2023. SPFresh: Incremental In-Place Update for Billion-Scale Vector Search. In SOSP. ACM, Koblenz, Germany, 545–561. [69] Mingyu Yang, Wenxuan Xia, Wentao Li, Raymond Chi-Wing Wong, and Wei Wang. 2025. Elastic Index Select for Label-Hybrid Search in Vector Database. arXiv:2505.03212 [cs.DB] [70] Wen Yang, Tao Li, Gai Fang, and Hong Wei. 2020. PASE: PostgreSQL UltraHigh-Dimensional Approximate Nearest Neighbor Search Extension. In SIGMOD. ACM, Portland, OR, USA, 2241–2253. [71] Qianxi Zhang, Shuotao Xu, Qi Chen, Guoxin Sui, Jiadong Xie, Zhizhen Cai, Yaoqi Chen, Yinxuan He, Yuqing Yang, Fan Yang, Mao Yang, and Lidong Zhou. 2023. VBASE: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity. In OSDI. USENIX Association, Boston, MA, USA, 377–395. [72] Xiaoyao Zhong, Haotian Li, Jiabao Jin, Mingyu Yang, Deming Chu, Xiangyu Wang, Zhitao Shen, Wei Jia, George Gu, Yi Xie, Xuemin Lin, Heng Tao Shen, Jingkuan Song, and Peng Cheng. 2025. VSAG: An Optimized Search Framework for Graph-Based Approximate Nearest Neighbor Search. Proc. VLDB Endow. 18, 12 (2025), 14 pages. [73] George Kingsley Zipf. 2016. Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology. Addison-Wesley Publishing, Boston, MA, USA. [74] Chaoji Zuo, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. 2024. SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 2, 1 (2024), 26 pages.

Proof of Theorem 3.1

Proof. By the MinHash property, for any random function ℎ𝑖 , Pr (ℎ𝑖min (𝐿1 ) = ℎ𝑖min (𝐿2 )) = 𝐽 (𝐿1, 𝐿2 ) ≥ 1 − 𝜃 𝑡 . Since the hash functions are independent, the probability that 𝐿1, 𝐿2 match in all 𝛽𝜏 𝜏

hash values of a single band is at least (1 −𝜃 𝑡 ) 𝛽 , and the prabability that they do not match in any of the 𝛽 band is at most (1 − (1 − 𝜏 𝛽

The term 𝐾(𝐿1, 𝐿2 ) does not yet incorporate the similarity constraint between 𝐿1 and 𝐿2 . Under 𝐽 (𝐿1, 𝐿2 ) ≥ 𝜖, the size of the difference set 𝐿1 /𝐿2 is controlled by Lemma 2. Lemma 2. If 𝐽 (𝐿1, 𝐿2 ) ≥ 𝜖, then ⋃︀𝐿1 /𝐿2 ⋃︀ ≤ (1 − 𝜖)⋃︀𝐿1 ⋃︀. ⋃︀𝐿 ∩𝐿 ⋃︀

Proof. As ⋃︀𝐿1 ∪ 𝐿2 ⋃︀ ≥ ⋃︀𝐿1 ⋃︀, 𝐽 (𝐿1, 𝐿2 ) = ⋃︀𝐿11 ∪𝐿22 ⋃︀ ≥ 𝜖, we have ⋃︀𝐿1 ∩ 𝐿2 ⋃︀ ≥ 𝜖⋃︀𝐿1 ⋃︀, and ⋃︀𝐿1 /𝐿2 ⋃︀ = ⋃︀𝐿1 ⋃︀ − ⋃︀𝐿1 ∩ 𝐿2 ⋃︀ ≤ (1 − 𝜖)⋃︀𝐿1 ⋃︀. □ Lemma 2 formalizes the basic effect of label set similarity: a larger Jaccard threshold leaves fewer labels in 𝐿1 that may be absent from 𝐿2 . This is the combinatorial reason why stricter tiers improve containment consistency.

B.1

Proof of Theorem 4.1

Proof. Combining Lemma 1 and Lemma 2, we have 𝐾(𝐿1, 𝐿2 ) ≥

(1−𝜖)⋃︀𝐿1 ⋃︀ . ∏ (1 − 𝑝 max ) ≥ (1 − 𝑝 max )

(15)

𝑎𝑖 ∈𝐿1 /𝐿2

Since the point-wise lower bound in Eq. (15) holds for all pairs 𝐿1, 𝐿2 , we can take expectation w.r.t. the conditional distribution of 𝐿1, 𝐿2 given 𝐿𝑞 ⊆ 𝐿1 and 𝐽 (𝐿1, 𝐿2 ) ≥ 𝜖 as follows: 𝑃𝑐 = E𝐿1 ,𝐿2 )︀𝐾(𝐿1, 𝐿2 ) ⋃︀ 𝐽 (𝐿1, 𝐿2 ) ≥ 𝜖⌈︀.

(16)

Replace ⋃︀𝐿1 /𝐿2 ⋃︀ with Lemma 2 and use the maximum probability among all labels, taking the fact that ⋃︀𝐿1 ⋃︀ ≤ ⋃︀𝐴⋃︀: 𝑃𝑐 ≥ E [︀(1 − 𝑝 max )(1−𝜖)⋃︀𝐿1 ⋃︀ ⋃︀ 𝐽 (𝐿1, 𝐿2 ) ≥ 𝜖⌉︀ ≥ (1 − 𝑝 max )(1−𝜖)⋃︀𝐴⋃︀ . (17) By Chebyshev’s inequality, Pr (⋃︀𝐿1 ⋃︀ ≤ 𝜇 + ⌈︂𝜎 ) ≥ 1 − 𝜉, replacing 𝜉

𝛽

𝜃 𝑡 ) ) . Taking the complementary event gives us the probability that 𝐿1, 𝐿2 match in at least one band in Eq. (1). □

⋃︀𝐿1 ⋃︀ in Eq. (15) gives us a high-confidence bound in Eq. (4), where 𝜇 ≪ ⋃︀𝐴⋃︀ in real-world datasets. □

Proofs for Containment Lower Bound

We next characterize the skewed setting. Let 𝒥 ∶ 𝐽 (𝐿1, 𝐿2 ) ≥ 𝜖 and 𝐷 = 𝐿1 /𝐿2 . The following lemma bounds the probability that a specific label appears in the difference set under the high-Jaccard constraint.

We first derive the containment kernel for fixed 𝐿1 and 𝐿2 . Without the Jaccard similarity constraint, the containment probability conditioned on fixed 𝐿1 and 𝐿2 is given by Lemma 1.

(12)

Lemma 3. Let event 𝒥 ∶ 𝐽 (𝐿1, 𝐿2 ) ≥ 𝜖, 𝐷 = 𝐿1 /𝐿2 . ∀𝑎𝑖 ∈ 𝐴, Pr(𝑎𝑖 ∈ 𝐷 ⋃︀ 𝒥 ) ≤ (1 − 𝜖)(1 − 𝑝𝑖 )𝑝𝑖 .

(13)

Proof. Pr(𝑎𝑖 ∈ 𝐷 ⋃︀ 𝒥 ) = Pr(𝑎𝑖 ∈ 𝐿1 ⋃︀ 𝒥 ) Pr(𝑎𝑖 ∉ 𝐿2 ⋃︀ 𝑎𝑖 ∈ 𝐿1, 𝒥 ). Given 𝑎𝑖 ∈ 𝐿1 and 𝒥 with Lemma 2, ⋃︀𝐿1 /𝐿2 ⋃︀ ≤ (1 −𝜖)⋃︀𝐿1 ⋃︀ means that at most (1 − 𝜖) fraction of elements in 𝐿1 can be missing from 𝐿2 with probability 1 − 𝑝𝑖 , i.e. Pr(𝑎𝑖 ∉ 𝐿2 ⋃︀ 𝑎𝑖 ∈ 𝐿1, 𝒥 ) ≤ (1 − 𝜖)(1 − 𝑝𝑖 ):

Lemma 1. For any fixed non-empty 𝐿1, 𝐿2 ∈ ℒ, Pr(𝐿𝑞 ⊆ 𝐿2 ⋃︀ 𝐿𝑞 ⊆ 𝐿1, 𝐿1, 𝐿2 ) =

∏ (1 − 𝑝𝑖 ) ∶= 𝐾(𝐿1, 𝐿2 ).

𝑎𝑖 ∈𝐿1 /𝐿2

Proof. By definition of conditional probability: Pr(𝐿𝑞 ⊆ 𝐿2 ⋃︀ 𝐿𝑞 ⊆ 𝐿1, 𝐿1, 𝐿2 ) =

Pr(𝐿𝑞 ⊆ 𝐿1 ∩ 𝐿2 ⋃︀ 𝐿1, 𝐿2 ) . Pr(𝐿𝑞 ⊆ 𝐿1 ⋃︀ 𝐿1, 𝐿2 )

As for two arbitrary sets 𝑆 and 𝑇 , Pr(𝑆 ⊆ 𝑇 ) = ∏𝑎𝑖 ∉𝑇 Pr(𝑎𝑖 ∉ 𝑆) = ∏𝑎𝑖 ∉𝑇 (1 − 𝑝𝑖 ), we have Pr(𝐿𝑞 ⊆ 𝐿2 ⋃︀ 𝐿𝑞 ⊆ 𝐿1, 𝐿1, 𝐿2 ) =

∏𝑎𝑖 ∉(𝐿1 ∩𝐿2 ) (1 − 𝑝𝑖 ) . ∏𝑎𝑖 ∉𝐿1 (1 − 𝑝𝑖 )

Pr(𝑎𝑖 ∈ 𝐷 ⋃︀ 𝒥 ) = Pr(𝑎𝑖 ∈ 𝐿1 ⋃︀ 𝒥 ) Pr(𝑎𝑖 ∉ 𝐿2 ⋃︀ 𝑎𝑖 ∈ 𝐿1, 𝒥 ) ≤ (1 − 𝜖)(1 − 𝑝𝑖 )𝑝𝑖 .

(18) □

(14)

With relation between sets 𝐿1 /(𝐿1 ∩𝐿2 ) = 𝐿1 /𝐿2 , Pr(𝐿𝑞 ⊆ 𝐿2 ⋃︀ 𝐿𝑞 ⊆ 𝐿1, 𝐿1, 𝐿2 ) = ∏𝑎𝑖 ∈𝐿1 /𝐿2 (1 − 𝑝𝑖 ), which is defined as 𝐾(𝐿1, 𝐿2 ). □ Lemma 1 shows that, given any label sets 𝐿1 and 𝐿2 , the containment target fails only when 𝐿𝑞 contains a label in 𝐿1 that does not belong to 𝐿2 . Thus, every label in 𝐿1 /𝐿2 must be absent from 𝐿𝑞 , giving the product term 𝐾(𝐿1, 𝐿2 ).

Lemma 3 explains the intuition behind the Zipf-skewed bound. Although head labels have large inclusion probabilities, they are less likely to dominate 𝐷 under a high-Jaccard constraint. Intuitively, if a frequent label appears in 𝐿1 , omitting it from 𝐿2 consumes part of the limited missing-label budget imposed by 𝐽 (𝐿1, 𝐿2 ) ≥ 𝜖. Therefore, under skewed marginals, the difference set is more likely to be formed by lower-probability labels, making 𝐾(𝐿1, 𝐿2 ) = ∏𝑎𝑖 ∈𝐷 (1−𝑝𝑖 ) larger than what the worst-case 𝑝 max bound suggests.

Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification

B.2

Proof of Theorem 4.2

Proof. Let 𝑝𝑖 ∶= 𝐻𝜇𝑖

−𝑠

⋃︀𝐴⋃︀,𝑠

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA

(3) Combine bounds by the Bayes’ theorem. ⋃︀𝐴⋃︀

, 𝐻 ⋃︀𝐴⋃︀,𝑠 ∶= ∑ 𝑗=1 𝑗 −𝑠 , 𝑠 ≥ 0 and define 𝑟 ∶=

𝑃𝑐 = E(︀𝐾(𝐿1, 𝐿2 ) ⋃︀ 𝒥 ⌋︀

𝐻 max(2, arg min𝑖 𝐻 𝑖,𝑠 ≥ 𝜌). Hence, the prefix {𝑎 1, . . . , 𝑎𝑟 } contains ⋃︀𝐴⋃︀,𝑠

≥ E(︀𝐾(𝐿1, 𝐿2 )1(𝒜) ⋃︀ 𝒥 ⌋︀ ≥ E(︀𝐾(𝐿1, 𝐿2 ) ⋃︀ 𝒥 , 𝒜⌋︀ ⋅ Pr(𝒜 ⋃︀ 𝒥 )

at least a 𝜌-fraction of the Zipf mass. As in the theorem statement, let 𝒥 ∶= {𝐽 (𝐿1, 𝐿2 ) ≥ 𝜖}, 𝒜 ∶= {𝐷 ⊆ {𝑎𝑟 , . . . , 𝑎 ⋃︀𝐴⋃︀ }}.

⎛ ⎞ 𝜇 𝜇2 ≥ exp − Ψ𝑠 (𝐵) − 2 Ψ2𝑠 (𝐵) (1 − 𝜇𝜌(1 − 𝜖)), 𝐻 ⋃︀𝐴⋃︀,𝑠 ⎝ 𝐻 ⋃︀𝐴⋃︀,𝑠 ⎠

(1) Bound the expected tail mass. For fixed 𝑞 ≥ 0 and ∀𝑥 ≥ 0, )︀ (𝑟 + 𝑥 − 1)1−𝑞 − (𝑟 − 1)1−𝑞 ⌉︀ ⌉︀ , 𝑞 ≠ 1, ⌉︀ ⌉︀ 1−𝑞 Ψ𝑞 (𝑥) ∶= ⌋︀ ⌉︀ 𝑟 +𝑥 −1 ⌉︀ ⌉︀ 𝑞 = 1. ⌉︀ ]︀ln 𝑟 − 1 ,

(19)

Since 𝑡 ↦ 𝑡 −𝑞 is decreasing on (︀1, ∞), for any integer 𝑦 ≥ 1, 𝑟 +𝑦−1

∑ 𝑖

−𝑞

≤∫

𝑟 +𝑦−1

𝑡 −𝑞 𝑑𝑡 = Ψ𝑞 (𝑦),

where 𝐵 =

2𝜇(1−𝜖) 1+𝜖 . This establishes the claimed lower bound.

(27)

□

Proofs for Overlap Lower Bound

For overlap queries, we analyze the complementary event that a query overlaps 𝐿1 but does not overlap 𝐿2 . The following lemma shows that this non-overlap probability is maximized when the query label set is as small as possible.

(20)

Lemma 4. Pr(𝐿𝑞 ∩ 𝐿2 = ∅ ⋃︀ 𝐿𝑞 ∩ 𝐿1 ≠ ∅) is maximized at ⋃︀𝐿𝑞 ⋃︀ = 1.

where the equality follows by direct evaluation of the integral (with the logarithmic form when 𝑞 = 1). Therefore, on 𝒜,

Proof. Define 𝐿𝐴 = 𝐿1 ∩ 𝐿2, 𝐿𝐵 = 𝐿1 /𝐿2, 𝐿𝐶 = 𝐿2 /𝐿1, 𝐿𝐷 = (𝐿1 ∪ 𝐿2 )𝑐 , and 𝑎 = ⋃︀𝐿𝐴 ⋃︀, 𝑏 = ⋃︀𝐿𝐵 ⋃︀, 𝑐 = ⋃︀𝐿𝐶 ⋃︀, 𝑑 = ⋃︀𝐿𝐷 ⋃︀. Then, ⋃︀𝐿1 ⋃︀ = 𝑎 +𝑏, ⋃︀𝐿2 ⋃︀ = 𝑎 + 𝑐, ⋃︀𝐿1 ∪ 𝐿2 ⋃︀ = ⋃︀𝑎 + 𝑏 + 𝑐⋃︀. Define 𝜅 = ⋃︀𝐿𝑞 ⋃︀,

𝑟 −1

𝑖=𝑟

∑ 𝑝𝑖 ≤

𝑎𝑖 ∈𝐷

𝜇 𝐻 ⋃︀𝐴⋃︀,𝑠

Ψ𝑠 (⋃︀𝐷⋃︀),

∑ 𝑝𝑖 ≤ 2

𝑎𝑖 ∈𝐷

𝜇2 Ψ2𝑠 (⋃︀𝐷⋃︀). 𝐻 ⋃︀2𝐴⋃︀,𝑠

(21)

𝑓 (𝜅) = Pr(𝐿𝑞 ∩ 𝐿2 = ∅ ⋃︀ 𝐿𝑞 ∩ 𝐿1 ≠ ∅) =

Pr(𝐿𝑞 ∩𝐿2 =∅ ∧ 𝐿𝑞 ∩𝐿1 ≠∅) . Pr(𝐿𝑞 ∩𝐿1 ≠∅)

(28) 1−𝜖 (⋃︀𝐿1 ⋃︀ + ⋃︀𝐿2 ⋃︀), we get Using ⋃︀𝐷⋃︀ ≤ ⋃︀𝐿1 ⋃︀ + ⋃︀𝐿2 ⋃︀ − 2⋃︀𝐿1 ∩ 𝐿2 ⋃︀ ≤ 1+𝜖

2𝜇(1 − 𝜖) E(︀⋃︀𝐷⋃︀ ⋃︀ 𝒥 , 𝒜⌋︀ ≤ E(︀⋃︀𝐷⋃︀ ⋃︀ 𝒥 ⌋︀ ≤ ∶= 𝐵. 1+𝜖

(22)

Moreover, Ψ𝑞 is concave on 𝑥 ≥ 0 for 𝑞 ≥ 0 since Ψ𝑞′′ (𝑥) = −𝑞(𝑟 + 𝑥 − 1)−𝑞−1 ≤ 0. Hence, by Jensen’s inequality, ⎨ ⎬ ∫︀∫︀∫︀ ⎝ ⎠ 𝜇 ∫︀∫︀ ⎠ E⎝ Ψ𝑠 (𝐵), ⎝ ∑ 𝑝𝑖 ∫︀∫︀∫︀∫︀ 𝒥 , 𝒜⎠ ≤ 𝐻 ⎝𝑎𝑖 ∈𝐷 ∫︀∫︀ ⎠ ⋃︀𝐴⋃︀,𝑠 ⎪ ⎮ ⎬ ⎨ ∫︀∫︀ ⎠ ⎝ 𝜇2 2 ∫︀∫︀∫︀ ⎠ E⎝ ⎝ ∑ 𝑝𝑖 ∫︀∫︀∫︀∫︀ 𝒥 , 𝒜⎠ ≤ 𝐻 2 Ψ2𝑠 (𝐵). ⎠ ⎝𝑎𝑖 ∈𝐷 ∫︀∫︀ ⋃︀𝐴⋃︀,𝑠 ⎮ ⎪

𝐿𝑞 must be contained by (𝐿𝐴 ∪ 𝐿𝐵 )𝑐 = 𝐿𝐶 ∪ 𝐿𝐷 . 𝑓 (𝜅) = (23) which is non-increasing in 𝜅 because 𝑏 𝑓 (1) = 𝑎+𝑏 .

(2) Bound the event kernel and control the complement. 𝐾(𝐿1, 𝐿2 ) = ∏ (1 − 𝑝𝑖 ) = exp 𝑎𝑖 ∈𝐷

⎛ ⎞ ∑ ln(1 − 𝑝𝑖 ) . ⎠ ⎝𝑎𝑖 ∈𝐷

(24)

Under the standard long-tail condition on 𝒜 (i.e., assuming 𝑝𝑖 ≤ 0.6 for all 𝑖 ≥ 𝑟 ), we use ln(1 − 𝑥) ≥ −𝑥 − 𝑥 2 for 𝑥 ∈ (︀0, 0.6⌋︀ and obtain ⎛ ⎞ 𝜇 𝜇2 E(︀𝐾(𝐿1, 𝐿2 ) ⋃︀ 𝒥 , 𝒜⌋︀ ≥ exp − Ψ𝑠 (𝐵) − 2 Ψ2𝑠 (𝐵) . (25) 𝐻 𝐻 ⎝ ⋃︀𝐴⋃︀,𝑠 ⎠ ⋃︀𝐴⋃︀,𝑠 For 𝒜𝑐 , by Lemma 3, Pr(𝒜𝑐 ⋃︀ 𝒥 ) = Pr (⋃{𝑎𝑖 ∈ 𝐷} ⋁︀ 𝒥 ) 𝑖<𝑟

≤ (1 − 𝜖) ∑ 𝑝𝑖 (1 − 𝑝𝑖 ) ≤ (1 − 𝜖) ∑ 𝑝𝑖 ≤ 𝜇𝜌(1 − 𝜖), 𝑖<𝑟

𝑖<𝑟

(26) thus Pr(𝒜 ⋃︀ 𝒥 ) ≥ 1 − 𝜇𝜌(1 − 𝜖).

The numerator of 𝑓 (𝜅) is the probability of a joint event. 𝐿𝑞 ∩𝐿2 = ∅ iff. 𝐿𝑞 cannot contain any elements from 𝐿2 = 𝐿𝐴 ∪𝐿𝐶 , and thus 𝐿𝑞 must be contained in (𝐿𝐴 ∪𝐿𝐶 )𝑐 = 𝐿𝐵 ∪𝐿𝐷 . Given 𝐿𝑞 ⊆ 𝐿𝐵 ∪𝐿𝐷 , since 𝐿𝐷 ∩ 𝐿1 = ∅, 𝐿𝑞 ∩ 𝐿1 ≠ ∅ means that there is at least one element from 𝐵. Thus, (𝐿𝑞 ⊆ 𝐿𝐵 ∪ 𝐿𝐷 ) ∧ (𝐿𝑞 ∩ 𝐿𝐵 ≠ ∅). The number of 𝑑 𝜅-element subsets satisfying the above condition is (𝑏+𝑑 𝜅 ) − (𝜅 ). The dominator of 𝑓 (𝜅) equals to 1−Pr(𝐿𝑞 ∩𝐿1 = ∅), and for 𝐿𝑞 ∩𝐿1 = ∅, (𝑏+𝑑 )−(𝑑 ) 𝜅 𝜅

(⋃︀𝐴⋃︀ )−(𝑐+𝑑 ) 𝜅 𝜅

𝑓 (𝜅+1) < 1. Therefore, 𝑓 (𝜅) ≤ 𝑓 (𝜅)

□

Lemma 4 reduces the worst case of overlap preservation to singleton query labels. Thus, to lower-bound 𝑃𝑜 , it suffices to minimize the probability that a singleton label overlapping 𝐿1 also belongs to 𝐿2 under the Jaccard constraint.

C.1

Proof of Theorem 4.3

Proof. We consider the probability from the complement without the Jaccard constraint: 𝑃𝑜′ = 1 − Pr(𝐿𝑞 ∩ 𝐿2 = ∅ ⋃︀ 𝐿𝑞 ∩ 𝐿1 ≠ ∅).

(29)

By Lemma 4, 𝑃𝑜′ is minimized at ⋃︀𝐿𝑞 ⋃︀ = 1, thus the lower bound of ⋃︀𝐿 ∩𝐿 ⋃︀ 𝑃𝑜 is to minimize 𝑃𝑜′ subject to ⋃︀𝐿11 ∪𝐿22 ⋃︀ ≥ 𝜖. Using the same notation in the proof of Lemma 4, the object is to find the lower bound of 𝑎 𝑎 𝑎 𝜖 𝑎+𝑏 subject to 𝑎+𝑏+𝑐 ≥ 𝜖. 𝑎+𝑏+𝑐 ≥ 𝜖 ⇔ 𝑎 ≥ 1−𝜖 (𝑏 + 𝑐): 𝜖 (𝑏 + 𝑐) 𝜖(𝑏 + 𝑐) 𝑎 ≥ 𝜖1−𝜖 = =∶ 𝑓 (𝑐). 𝑎 +𝑏 (𝑏 + 𝑐) + 𝑏 𝑏 + 𝜖𝑐 1−𝜖

(30)

Taking the derivative, 𝑑𝑑𝑐𝑓 = (𝑏+𝜖𝑐)2 ≥ 0. So, the worst case lower 𝑎 bound is taken at 𝑐 = 0, i.e. 𝐿2 ⊆ 𝐿1 , which gives us 𝑎+𝑏 ≥ 𝜖. □ 𝜖𝑏(1−𝜖)

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA

Ziqi Wang, Jingzhe Zhang, Shuo Shen, and Wei Hu

Table 6: Query-set workload statistics

Datasets

Semantics

Equality Containment Overlap Equality GIST Containment Overlap Equality TripClick Containment Overlap Equality LAION Containment Overlap Equality YTB-Video Containment Overlap Equality YTB-Audio Containment Overlap Equality Wikipedia Containment Overlap Equality YFCC-1M Containment Overlap SIFT

Labels

Sets

12 588 12 611 12 622 12 589 12 611 12 622 29 249 29 305 29 503 30 491 30 504 30 524 135 120 177 143 279 174 675 652 731 680 820 708 32,780 9,673 1,520 2,689 5,960 9,756 186 450 261 502 4753 939

Table 7: Indexing performance of ANNS systems

Indices

SIFT GIST Trip LAION Video Audio

Wiki YFCC

2.3 2.3 2.3 2.3 2.3 2.3 2.0 2.1 2.7 2.5 2.7 2.8 2.2 2.2 3.1 2.7 2.7 3.1 5.8 1.7 5.9 2.9 3.1 9.0

FAISS-IVF FAISS-HNSW VSAG-IVF VSAG-HNSW

13 138 207 177

27 672 236 867

53 688 170 810

12 135 138 186

Milvus-IVF Milvus-HNSW PGVector-IVF PGVector-HNSW

8 11 11 488 488 516 37 304 1,037 478 4,016 1,024

10 12 39 488 488 2,441 656 3,914 167 638 3,905 2,453

40 2,441 493 2,793

8 488 58 505

LSSG-IVF LSSG-MinHash

311 296

271 277

602 606

239 303

Indices

SIFT GIST Trip LAION Video Audio

FAISS-IVF FAISS-HNSW VSAG-IVF VSAG-HNSW

1,546 9,107 8,043 30 149 129 94 473 350 31 82 79

4,880 9,994 3,507 10,920 1,851 71 74 192 400 42 253 595 250 457 119 46 59 163 311 29

Milvus-IVF Milvus-HNSW PGVector-IVF PGVector-HNSW

84 438 87 678 90 631 238 1,092

387 350 583 923

269 440 446 279 410 483 356 750 447 544 1,128 1,136

968 1,257 1,237 2,841

103 132 180 276

LSSG-IVF LSSG-MinHash

133 122

270 233

181 179

487 426

379 111

2 2 2 2 2 2 2 2 3 2 3 3 2 2 3 2 2 3 6 2 6 3 3 6

4 4 4 4 4 4 3 3 4 4 4 5 4 4 5 5 5 5 7 3 9 3 3 16

Dataset Details

Label–vector correlation. We compute Spearman’s 𝜌 between label Jaccard distance and vector L2 distance for all datasets. Base vectors are ranked by their label set size ⋃︀𝐿 ⋃︀ and split into four equal-count quartile buckets: Q1 contains the smallest 25% of label sets and Q4 the largest 25%. Fig. 17 shows negligible correlations on seven datasets and a modest positive correlation on Wikipedia. Thus, the evaluated workloads generally lack strong global label– vector correlation, which LSSG does not assume. Instead, label stratification improves local in-filtering navigation by increasing the likelihood of label-qualified next-hop candidates. Query workload statistics. Table 6 reports query-side effective labels, distinct query label sets, and query label set size distributions for all filter semantics. Most equality and containment queries are compact, with median size 2–3 and P90 at most 7. Overlap queries are broader. YFCC-1M overlap uses 4,753 effective query labels with average/median/P90 size 9.0/6/16, while Wikipedia overlap uses 5,960 effective query labels with size 5.9/6/9. These statistics complement Table 3 and show that the workloads cover both compact query labels and large, diverse label spaces.

Index size (MB)

Label set size Avg Med P90

Additional Experiments

Approximation to the oracle on other datasets. Fig. 18 compares distance computations (DC) against the oracle HNSW on the remaining four datasets. On SIFT and TripClick, the label space is small and containment filters are highly selective, so all methods operate on relatively small filtered subsets and exhibit similar

41 134 137 203

204 192

37 145 117 233

199 200

26 136 155 246

47 672 148 209

136 1,069 142 1,065

Indexing time (s)

241 224

287 243

946 721

Wiki YFCC

DC behavior close to the oracle. In contrast, the gap widens on YTB-Video and YFCC-1M, whose larger label spaces make crosslabel navigation more difficult. LSSG is the closest approximation among LFANNS indices, indicating better navigation efficiency under large-scale label constraints. Selectivity breakdown on other datasets. Fig. 19 reports QPS across selectivity percentiles on the remaining four datasets. On SIFT and TripClick where the label universe is small, ELI, UNG, and LSSG are broadly comparable across percentiles. On YFCC-1M, ELI fails to construct and UNG cannot reach 0.9 recall across all selectivity percentiles in the overlap semantic. ACORN performs strongly for overlap on low-selectivity percentiles, consistent with its connectivity advantage when a large fraction of candidates pass the filter. Indexing performance of ANNS systems. Table 7 illustrates the index size and indexing time of the systems compared in Fig. 7. Across eight datasets, LSSG incurs moderate construction costs, with median index size and indexing time of 287 MB and 229 s, respectively. FAISS and VSAG HNSW variants build quickly with moderate space, whereas IVF variants are compact but substantially slower to construct (median time: 302–6,462 s). Milvus and PGVector provide integrated filtering but often incur larger index size and comparable or higher construction time (median: 380–1,008 s). The two LSSG variants have similar costs, and offer a balanced construction trade-off while achieving stronger LFANNS performance. Query performance of ANNS systems on other datasets. Fig. 20 shows the system results on SIFT, TripClick, YTB-Video, and YFCC1M. FAISS remains recall-limited, attaining at most 0.13–0.91 for

Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification

SIFT

GIST

ρ = −0.004

600

Overall

300 600

L2 Distance

Q1 (0–25%): |L| = 1

300

ρ = 0.004

600

ρ = 0.008

Q1 (0–25%): |L| = 1

ρ = 0.011 12

ρ = 0.017

10 2

450 Q2 (25–50%): |L| ∈ [1, 2]

300

ρ = −0.011

600

Q2 (25–50%): |L| ∈ [1, 2]

ρ = 0.008

Q3 (50–75%): |L| ∈ [2, 3]

300

ρ = 0.006

600 450

Q2 (25–50%): |L| = 1

ρ = −0.002

Q3 (50–75%): |L| = 1

ρ = 0.009

ρ = −0.004

1.2

0.8

ρ = 0.003

Q3 (50–75%): |L| ∈ [3, 4]

ρ = 0.005

1.2

ρ = 0.048 ∗ ∗∗

ρ = 0.014

1.4

Q1 (0–25%): |L| ∈ [1, 6] 150

5 Q3 (50–75%): |L| ∈ [3, 4] 1.2

ρ = 0.025 ∗ ∗

320 Q2 (25–50%): |L| ∈ [3, 6]

ρ = 0.176 ∗ ∗∗ 480

ρ = 0.005

400 Q3 (50–75%): |L| = 6

ρ = 0.006 1.5

320 Q3 (50–75%): |L| ∈ [6, 10]

ρ = 0.100 ∗ ∗∗ 480

ρ = 0.033 ∗ ∗∗

400

1.4

ρ = −0.004

400 Q2 (25–50%): |L| = 6

1.4

10 Q3 (50–75%): |L| ∈ [3, 4]

Q1 (0–25%): |L| ∈ [1, 3]

ρ = 0.170 ∗ ∗∗ 480

5 Q2 (25–50%): |L| ∈ [2, 3] 1.2 ρ = 0.015 ρ = −0.014 1.5 15

ρ = 0.001

300

1.4 Q1 (0–25%): |L| ∈ [1, 2]

ρ = −0.009 1.5

Overall

ρ = 0.038 ∗ ∗∗ 450

Q2 (25–50%): |L| ∈ [2, 3]

320

Overall

1.2

ρ = 0.010∗

400

ρ = 0.001 1.5

YFCC-1M

ρ = 0.150 ∗ ∗∗ 480

1.4

Overall

10 Q1 (0–25%): |L| ∈ [1, 2]

Wikipedia

ρ = −0.005 1.5

Overall

ρ = 0.007

YTB-Audio 15 10

Q2 (25–50%): |L| ∈ [2, 3]

1.2

0.8

ρ = 0.021 ∗ ∗∗

1.2

0.8

YTB-Video 30

Q1 (0–25%): |L| ∈ [1, 2]

8 Q3 (50–75%): |L| ∈ [2, 3]

ρ = −0.001

450

Overall

Q1 (0–25%): |L| = 1

ρ = 0.004

0.8

450

Overall

ρ = −0.004 12

LAION 1.2 1

Overall

ρ = −0.012

ρ = 0.016 ∗ ∗∗

450

TripClick

ρ = 0.004 12

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA

Q4 (75–100%): |L| ∈ [1, 8] 0.8 Q4 (75–100%): |L| ∈ [4, 12] 10 Q4 (75–100%): |L| ∈ [4, 21] 5 Q4 (75–100%): |L| ∈ [4, 23] Q4 (75–100%): |L| ∈ [6, 17] 320 Q4 (75–100%): |L| ∈ [10, 1332] 300 Q4 (75–100%): |L| ∈ [3, 8] 1 Q4 (75–100%): |L| ∈ [3, 8] 0.0 0.5 1.0 0.0 0.5 1.0 0.0 0.5 1.0 0.0 0.5 1.0 0.0 0.5 1.0 0.0 0.5 1.0 0.0 0.5 1.0 0.0 0.5 1.0

Jaccard Distance

Figure 17: Correlation between pairwise Jaccard distance and L2 distance. Darker regions indicate more object pairs. The red curve shows E(︀𝛿 𝑣 (𝑣 1, 𝑣 2 ) ⋃︀ 𝛿𝐿 (𝑙(𝑣 1 ), 𝑙(𝑣 2 ))⌋︀, and Spearman’s coefficient 𝜌 is marked at the top right corner.

0.6

0.8

Recall@10

1.0

0.8

1.0

104

0.6

0.8

Recall@10

1.0

0.6

0.8

Recall@10

1.0

0.6

0.8

Recall@10

1.0

101 10% 30% 50% 70% 90% 10% 30% 50% 70% 90% 103

103

102 103

100 10% 30% 50% 70% 90% 10% 30% 50% 70% 90%

10% 30% 50% 70% 90%

Percentile

0−

10% 30% 50% 70% 90%

Percentile

10% 30% 50% 70% 90%

R=0.70

101

Figure 18: DC of LFANNS indices on other datasets

102

103 10% 30% 50% 70% 90%

103

104 104

103

105

0.6

10% 30% 50% 70% 90%

Percentile

104

1.0

0.8

0.6

1.0 6

10% 30% 50% 70% 90%

Percentile

0.8

10 − 10 − 10 − 10 − 10 −

0.6

1.0

10% 30% 50% 70% 90% 10% 30% 50% 70% 90% 10% 30% 50% 70% 90% 104 R=0.80 104

10 −

Overlap DC

0.8

10% 30% 50% 70% 90%

103

0.6

103

104

103

104

103

10 −

1.0

0.8

YFCC-1M

105

10 −

0.6

Containment Overlap

R=0.85

1.0

10 −

0.8

105

103

0.6

104

1.0

0.8

ELI Equality

YTB-Video

104

10 − 10 − 10 − 10 − 10 −

0.6

104

Equality QPS

1.0

102

ACORN UNG

TripClick

105

Containment QPS

Containment DC

0.8

SIFT

104

103

0.6

LSSG-IVF LSSG-MinHash

104

103 102

ELI Oracle

YFCC-1M

105

104 103

RWalks UNG

YTB-Video

Overlap QPS

104

ACORN Packing

TripClick

Equality DC

SIFT

Avg. Filter Ratio 1 1

LSSG-IVF LSSG-MinHash

10% 30% 50% 70% 90%

Percentile

10% 30% 50% 70% 90%

Percentile

equality and 0.60–0.93 for containment across these datasets. On YTB-Video overlap, it reaches only 0.89 recall. At 0.95 recall for containment, the best VSAG, Milvus, and PGVector variants achieve 18– 136, 17–122, and 9–44 QPS, respectively, while LSSG remains on the upper QPS–recall frontier. Although library implementations can be competitive for overlap on SIFT, TripClick, and YFCC-1M, their performance varies substantially across workloads and degrades on YTB-Video. Overall, LSSG provides more consistent high-recall performance across datasets and filter semantics.

weakening progressive navigation. (2) MinHash benefits from metric alignment. Non-Jaccard distances hurt LSSG-MinHash more than LSSG-IVF, since MinHash is an unbiased estimator for Jaccard similarity but not for the other distance measures.

Impact of different label set distances. Fig. 21 compares tiering on LAION using distances induced by alternative label set simi⋃︀𝐿 ∩𝐿 ⋃︀ 2⋃︀𝐿1 ∩𝐿2 ⋃︀ larities, including cosine ( ⌈︂ 1 2 ), Dice ( ⋃︀𝐿1 ⋃︀+⋃︀𝐿 ), and overlap 2 ⋃︀

Impact of the Jaccard threshold distribution. In Def. 4, we use uniformly spaced Jaccard-distance thresholds across tiers. We log(𝑡 ) additionally evaluate logarithmic (𝜃 𝑡 = 1− log(𝑇 ) ), exponential (𝜃 𝑡 =

overlap distance degrades containment because it provides weaker granularity for separating tiers, underutilizing higher tiers and

2 𝑇 −1 1− ), and quadratic (𝜃 𝑡 = 1−( 𝑇𝑡 −1 𝑒−1 −1 ) ) schedules. As shown in Fig. 22, LSSG-MinHash is robust across all threshold schedules, suggesting that its probing step tolerates moderate changes in tier

⋃︀𝐿1 ⋃︀×⋃︀𝐿2 ⋃︀ ⋃︀𝐿1 ∩𝐿2 ⋃︀ ( min(⋃︀𝐿1 ⋃︀,⋃︀𝐿2 ⋃︀) ). (1) Jaccard is the best fit for tiering. Stratification by

Figure 19: Selectivity breakdown on other datasets

exp( 𝑡 −1 )−1

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA

102

YFCC

103

102

0.6

0.8

1.0

0.6

0.8

102

0.8

102

0.6

102

101

1.0

Overlap QPS

0.6

0.8

Recall@10

1.0

0.6

0.8

1.0

103

102

101

1.0

0.6

0.8

1.0

0.6

0.8

Recall@10

1.0

0.6

104

103

104

YTB-Video

101

Containment QPS

104

0.8

1.0

0.8

1.0

0.6

104

0.8

1.0

102

0.8

Recall@10

1.0

0.6

0.8

Recall@10

0.85

0.95

103

102 1.00 0.80

0.85

0.90

102

0.80

0.85

0.90

Recall@10

0.95

0.85

0.90

0.95

103

102

0.85

LSSG-IVF

1.00 0.80

0.85

0.90

0.95

1.00

0.90

0.95

1.00

0.95

1.00

0.95

1.00

LSSG-IVF 0.90

0.95

1.00 0.80

103

0.85

103

102

LSSG-MinHash 0.85

0.90

0.95

LSSG-MinHash

1.00 0.80

0.85

0.90

103 102

102

LSSG-MinHash

0.95

101 0.80

1.00

103

LSSG-IVF

102

LSSG-IVF

103

LSSG-MinHash

0.90

102

0.80

Overlap Overlap QPS

Containment QPS

LSSG-IVF

102

Dice

Quadratic

YTB-Audio

103

101 0.80

1.0

103

102 0.80

Overlap QPS

Cosine

103

Exponential

LSSG-IVF

0.6

Figure 20: Query performance of ANNS systems on other datasets Jaccard

103

0.80

102

0.6

Logarithmic

LAION

Containment QPS

102

Equality QPS

104

Uniform

PGVector-IVF PGVector-HNSW

Overlap QPS

TripClick

104

Milvus-IVF Milvus-HNSW

0.85

LSSG-MinHash

0.90

Recall@10

0.95

1.00 0.80

0.85

0.90

Recall@10

Figure 22: Impact of Jaccard distance threshold distribution All 27 configs

LSSG-MinHash

1.00 0.80

0.85

0.90

Recall@10

0.95

1.00

QPS

SIFT

VSAG-IVF VSAG-HNSW

Containment QPS

FAISS-IVF FAISS-HNSW

Equality

LSSG-IVF LSSG-MinHash

Ziqi Wang, Jingzhe Zhang, Shuo Shen, and Wei Hu

QPS

Overlap

104 103 SIFT 80

100

QPS QPS

104

103 LAION 85

100

103 102 50

100

102

Recall@10

Recommended

102

102 SIFT 60 70

103 80

100

LAION

Recall@10

100

Min indexing time

104 103

101

102 80

100

100 102

100

101

102 80

101

103

Recall@10

100 YTB-Audio 70 80 102

104

Best per workload

103

102

50 103

104

102 70 104

100

103 50

103 102

103 YTB-Audio 60 80

103

103 104

Min indexing time

104

All 27 configs

Equality

Best per workload

104

Recall@10

ELI Containment QPS

Baseline parameter audit. To ensure fair baseline tuning, we evaluate all 27 construction configurations of UNG and ELI on SIFT, LAION, and YTB-Audio. For UNG, we sweep 𝑀 ∈ {16, 32, 64}, 𝐿build ∈ {50, 100, 200}, and 𝛿 ∈ {3, 6, 12}. For ELI, we sweep 𝑀 ∈ {8, 16, 32}, efc ∈ {128, 200, 256}, and 𝑒 ∈ {0.2, 0.4, 0.6}. Fig. 23 shows all swept results and highlights the recommended, query-best, and minimum indexing time settings. Table 8 reports the construction costs of the recommended and query-best settings. For containment, tuning UNG improves QPS by 1.23–1.33x, but the gains are accompanied by construction or cross-semantic penalties. The query-best settings require 1.12–2.25x indexing time of the recommended setting. Index size increases by 83% on SIFT and 37% on YTB-Audio. They also degrade other semantics: for equality, QPS drops by 13% on SIFT and 14% on YTB-Audio, while on LAION the maximum recall decreases from 0.877 to 0.832. For overlap, the best settings show the same trade-off. On SIFT, the 1.40x QPS gain reduces that for equality and containment by 21% and 23%, while increasing index size and indexing time by 55% and

Overlap

granularity. LSSG-IVF is more sensitive. Non-uniform schedules can over-emphasize a narrow similarity range, while the uniform schedule covers a broader spectrum of label set similarity and yields better containment and overlap performance in our experiments.

UNG Containment QPS

Figure 21: Comparison of different label set distances

Recommended

100 80

Recall@10

100

Recall@10

Figure 23: Query-side parameter audits

Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification

Table 8: Parameter audits of UNG and ELI. “Rec.” is the index size and indexing time on the recommended settings. The recommend settings are (32, 100, 6) for UNG and (16, 200, 0.2) for ELI. “Query-best” is the setting with the best query performance per workload (blue curves in Fig. 23).

Sem.

Rec. (MB / s)

Query-best setting

Query-best (MB / s)

SIFT

Eq. Cont. Ovlp.

228 / 76 228 / 76 228 / 76

(16, 50, 3) (64, 200, 6) (64, 100, 3)

169.6 / 33.7 417.6 / 170.8 353.1 / 89.5

LAION

Eq. Cont. Ovlp.

271 / 189 271 / 189 271 / 189

(16, 50, 12) (16, 200, 6) (64, 50, 12)

234.7 / 87.9 193.3 / 211.2 346.3 / 126.5

Indices Datasets

UNG

Eq. 954 / 1,422 (32, 100, 12) 1,220.5 / 1,716.4 YTB-Audio Cont. 954 / 1,422 (64, 200, 6) 1,303.5 / 1,870.6 Ovlp. 954 / 1,422 (64, 200, 12) 1,552.8 / 1,843.1

ELI

SIFT

Eq. Cont. Ovlp.

419 / 98 419 / 98 419 / 98

(16, 200, 0.2) (16, 128, 0.6) (16, 128, 0.4)

419 / 98 615.0 / 88.8 615.0 / 88.8

LAION

Eq. Cont. Ovlp.

745 / 257 745 / 257 745 / 257

(32, 256, 0.2) 1,331.2 / 399.1 (8, 128, 0.6) 597.0 / 182.7 (16, 128, 0.4) 968.0 / 245.0

Eq. 92,693 / 807 (32, 256, 0.4) 94,141.4 / 912.1 YTB-Audio Cont. 92,693 / 807 (32, 256, 0.6) 94,915.3 / 989.3 Ovlp. 92,693 / 807 (32, 256, 0.6) 94,915.3 / 989.3

18%. On LAION and YTB-Audio, the maximum recall for overlap increases from 0.877/0.778 to 0.903/0.812, but QPS for equality decreases by 13%/14% and index size increases by 28%/63%; YTB-Audio also requires 30% longer indexing. Thus, UNG’s query-best settings

SIGMOD ’27, June 13–19, 2027, Huntington Beach, CA

improve the target workloads by trading off construction cost or performance under other filter semantics, rather than providing a uniformly stronger replacement. ELI exhibits a clearer dependence on both dataset and filter semantics. The recommended 𝑒 = 0.2 gives the best accuracy for equality on SIFT and LAION, whereas containment favors 𝑒 = 0.6 and overlap favors 𝑒 = 0.4 on these datasets. Tuning improves QPS by 2.08–3.95x for containment and by at most 1.64x for overlap, but reduces maximum recall for equality by 10.6% on SIFT and 6.3% on LAION. These settings are therefore not uniformly stronger replacements. Even (16, 128, 0.2), which retains 𝑒 = 0.2 and improves several SIFT/LAION workloads, loses on YTB-Audio overlap, where the recommended setting achieves the best result. The best setting for containment on YTB-Audio instead increases indexing time by 23%. Thus, no alternative among the 27 configurations consistently improves the recommended setting across all datasets and semantics. In summary, using the query-best audited configurations changes some point-wise winners but not the overall cross-semantics comparison. LSSG-MinHash remains 1.33–5.24x faster than query-best UNG on all three containment workloads, while no audited UNG configuration reaches 0.95 recall for overlap on LAION or YTBAudio. Query-best ELI is 2.63x and 4.49x faster than LSSG-MinHash on SIFT and LAION for containment and matches LSSG-MinHash on SIFT for overlap. Conversely, LSSG-MinHash is 1.20x faster on LAION for overlap and 32.0x/10.1x faster on YTB-Audio for containment/overlap. Thus, tuning changes individual winners but yields no baseline with consistent dominance across the audited datasets and semantics compared. LSSG retains the advantage of consistently strong performance across all semantics with one index. Received 17 April 2026; revised 20 August 2026; accepted 12 September 2026

Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification

Related documents