WorksComputer Science
Dynamic Graph Indexing for Label-Filtered Approximate Nearest Neighbor Search
Abstract
Approximate nearest neighbor search (ANNS) over high-dimensional vectors is a core primitive in modern retrieval systems. In practice, objects are often also associated with labels (e.g., attributes or keywords), and retrieval must combine vector similarity with explicit label-based filtering, giving rise to label-filtered ANNS. This task is challenging because label filtering and ANNS favor very different index structures, selective filters fragment the admissible search space, and updates complicate index maintenance. To address these challenges, we propose DYLAN, a dynamic composite index for label-filtered ANNS supporting containment, overlap, and their conjunctions and disjunctions. DYLAN organizes label sets by shared prefixes in a frequency-ordered trie and selectively shares HNSW-style graph indices across trie-induced subsets, so that each trie region has a constant-factor covering index while each object participates in only logarithmically many indices. To mitigate fragmentation, DYLAN performs a cross-region multi-graph search that exploits ancestor-level indices as bridges between otherwise isolated trie regions. To support insertions, it adopts a threshold-based maintenance scheme that rebuilds shared indices only when necessary, yielding low amortized update cost. Extensive experiments with real data show that DYLAN consistently improves query throughput at comparable recall, by up to two orders of magnitude on challenging label-rich datasets, while retaining competitive memory, construction, and update costs.
Authors’ Contact Information: Mengxu Jiang, [email protected], The Chinese University of Hong Kong, Hong Kong; Zhi Yang, [email protected], The Chinese University of Hong Kong, Hong Kong; Fangyuan Zhang, Harbin Institute of Technology, Shenzhen, China, [email protected]; Yin Yang, Hamad Bin Khalifa University, Doha, Qatar, [email protected]; Sibo Wang, [email protected], The Chinese University of Hong Kong, Hong Kong.
This work is licensed under a Creative Commons Attribution 4.0 International License.
© 2026 Copyright held by the owner/author(s).
ACM 2836-6573/2026/12-ART335
https://doi.org/10.1145/3856330
Introduction
Recent advances in machine learning, especially large language models (LLMs), have significantly increased the demand for managing high-dimensional vector data. Through a machine learning model, an unstructured object, such as an image or a full-text article, can be mapped to a high-dimensional vector called its embedding, in such a way that objects close in the vector space are often semantically related. For example, under a vision-language model such as CLIP [29], the image of a pill and the textual instructions of the corresponding medicine map to nearby embeddings. This enables semantic retrieval over unstructured data, typically through approximate nearest neighbor search (ANNS) [20], which is supported effectively in modern vector database systems [12, 13, 37].
In practice, however, retrieval is rarely based on vector similarity alone. Each object is often also associated with a set of labels, such as categories, tags, or keywords. For example, medical articles may be tagged as “papers in reputed medical journals”, “manufacturer instructions”, or “social posts”. Accordingly, ANNS is often augmented with explicit label-based filtering, e.g., retrieving only papers in reputed medical journals and manufacturer instructions, so as to provide stronger control over the source of information. Such a query is referred to as label-filtered ANNS [19].
Main challenges. Although both ANNS and label-based filtering have been studied extensively, their combination remains challenging because the two tasks favor fundamentally different index structures. Label filtering is typically supported by set-oriented structures such as inverted lists [45], whereas ANNS is usually supported by graph-based indices such as HNSW [26]. A straightforward approach is to choose one of these structures, which leads to either pre-filtering (i.e., employing a label index to filter objects but performing ANNS index-free) or post-filtering (index-based ANNS with post-processing to filter the results with labels). The former may incur a costly scan over a large candidate set, whereas the latter often requires substantial over-retrieval to maintain recall.
A more integrated direction, called in-filtering [28], performs filtering during graph traversal. Specifically, when processing a label-filtered ANNS query on an HNSW-style graph [26], the search expands only neighbors that satisfy the filter. The main difficulty is that a selective filter may eliminate a large fraction of graph edges, effectively sparsifying the admissible subgraph and making many qualified objects unreachable, which leads to false dismissals and low recall. Existing techniques alleviate this issue by exploring larger local neighborhoods, e.g., via two-hop expansion [28, 32], but this increases traversal cost and still does not exploit the structure of label-set relationships. In particular, such methods are largely label-agnostic: they treat the filter as a generic predicate rather than explicitly indexing how label sets relate to one another.
Existing label-aware solutions. To our knowledge, only a limited number of label-aware ANNS indices have been proposed, and existing solutions still address only part of the problem. Table 1 summarizes representative methods in terms of label awareness, query efficiency across predicates, update support, and label scalability. Label filter types (i.e., containment/overlap/complex) are formally defined in Section 2.1. Update support and label scalability are assessed from each method’s reported behavior.
| Method | Label Aware | Containment | Overlap | Complex | Vector | Label set | Label Scalability |
| ACORN [28] | × | Low | Low | Low | ✓ | ✓ | High |
| NaviX [32] | × | Low | Low | Low | ✓ | ✓ | High |
| Filtered-DiskANN [19] | ✓ | Low | Medium | × | ✓ | ✓ | High |
| RWalks [5] | ✓ | Medium | Medium | × | × | × | Low |
| UNG [11] | ✓ | Medium | Medium | × | ✓ | × | High |
| UniFilter [41] | ✓ | Low | × | × | ✓ | Partial | High |
| Curator [23] | ✓ | Medium | Medium | Medium | ✓ | ✓ | High |
| DYLAN (Ours) | ✓ | High | High | High | ✓ | ✓ | High |
Table 1. Comparison of label-filtered ANNS methods. ✓: full support; ×: no support; “Partial”: limited support. Query-efficiency ratings summarize the empirical trends in § 4. “High”: consistently reaches the target recall and is among the fastest across reported datasets; “Medium”: reaches the recall but with clearly lower throughput or only on some datasets; “Low”: often falls short or is substantially slower. Label scalability is rated by how index space grows with the label universe. “High”: near-constant or slowly growing; “Low”: a growth rate that becomes prohibitive.
A first line of work augments a single graph index with label information. Filtered-DiskANN [19] incorporates labels into both index construction and search and supports incremental updates, but focuses on overlap filters, performs poorly on containment filters, and does not extend to complex predicates. RWalks [5] instead guides retrieval by a hybrid score combining vector proximity with label similarity, avoiding a hard admissibility check during expansion; however, it encodes labels into vector-like representations, so its index expands substantially with many distinct label types, and updates are not explicitly addressed. As reflected in Table 1, both fail to preserve enough edges that guide the search from one qualified object to another, and hence struggle with highly selective label filters, as shown in our experiments.
Another line of work adopts a partitioned multi-graph design. Notably, UNG [11] groups objects by distinct label sets and builds a separate graph index for each group, which fragments the vector space and weakens global navigability. UNG alleviates this with a label navigating graph (LNG) connecting related subgraphs, but cross-region connectivity may still be insufficient for queries spanning multiple regions, hurting recall. Inserting a new label set may also trigger widespread changes in the LNG, slowing down updates.
A third category materializes filter states, e.g., UniFilter [41] combines an HNSW graph with an AND/OR-style graph for label relationships. Targeting containment queries, it caps the size of its auxiliary label index, so its memory stays bounded as the label universe grows; the price, as reflected in Table 1, is that new labels are only partially absorbed and query performance degrades substantially on label-rich datasets.
Finally, Curator [23] applies an IVF-based index for filtered ANNS under low selectivity, whose search effectiveness is weaker than that of graph-based ANNS indices as acknowledged in [23].
Our solution. We propose DYnamic Label-filtered Approximate Nearest neighbor search (DYLAN), an index for label-filtered ANNS with efficient updates. DYLAN supports containment, overlap, and complex predicates composed via conjunction and disjunction. In this paper, we assume the index fits in main memory, and our implementation is single-threaded.
Our starting point is simple: organizing data objects in a shared-prefix label trie (efficient for label-based filtering), and then materializing graph indices (effective for ANNS) over trie-induced subsets of vectors. The challenge, however, is that materializing a graph index for every trie node incurs prohibitive space and update costs for a large trie, whereas maintaining graph indices only at lower-level (i.e., fine-grained) trie nodes fragments the search space and restricts the global navigability required by graph-based ANNS; moreover, updates may substantially change the trie structure and invalidate pre-built graph indices. DYLAN therefore builds on three key ideas: selective graph materialization, cross-region graph navigation, and threshold-based maintenance of shared graph indices.
Concretely, DYLAN is built in two phases. The first constructs a label trie capturing the relationships among label sets in the data: each non-root node carries a label and a prefix formed by the labels on the root-to- path, each object is assigned to the leaf whose prefix matches its label set, and the objects assigned to leaves in the subtree rooted at form the trie region of . The second phase selectively materializes multiple HNSW-style graph indices embedded in , rather than building one for every trie node. Each object participates in only logarithmically many graph indices, keeping the total index size near-linear (Theorem 3.9), while the shared index covering a trie region contains at most a constant factor more objects than the region itself, thereby avoiding substantial degradation in search efficiency. Intuitively, graph indices near the root capture more global vector relationships across broader label regions, whereas those near the leaves preserve denser local connectivity among objects with highly similar label sets.
Given a query vector with a label predicate , the filtered search space often spans multiple trie regions. DYLAN first identifies a set of trie nodes whose subtrees jointly cover the filtered object set: the regions of containment and overlap predicates are located directly on the trie, whereas a complex predicate is recursively decomposed into sub-predicates combined by conjunction or disjunction, whose regions are computed separately and then combined. Searching the corresponding graph indices in isolation is ineffective, because the search may become trapped in local optima and miss promising candidates in other regions. DYLAN therefore performs a cross-region multi-graph search, further exploiting the graph indices at common ancestors of the nodes in ; these ancestor-level indices may contain cross-subtree connections that serve as effective bridges across otherwise isolated trie regions, restoring the global navigability needed by graph-based ANNS.
DYLAN also supports dynamic updates. Following common practice in dynamic graph-based ANNS indices [22, 41, 43], deletions are handled lazily by marking deleted objects as invalid and skipping them during search. Insertions are more challenging: a single insertion may affect multiple shared graph indices along the corresponding root-to-leaf path, and an eager strategy would trigger the construction of new graph indices or the rebuilding of existing ones. DYLAN therefore adopts a threshold-based maintenance scheme, which rebuilds a shared graph index only when its size mismatch with the target region exceeds a prescribed threshold, yielding a provably bounded amortized insertion cost while preserving the search effectiveness of the maintained indices.
Extensive experiments on multiple real datasets validate the effectiveness of DYLAN. Our main contributions are as follows.
We propose the DYLAN index, which introduces a selective graph materialization scheme on a label trie for effective label-filtered ANNS, while keeping the index size near-linear.
We design a cross-region multi-graph search algorithm that exploits ancestor graph indices to bridge fragmented trie regions, balancing query efficiency and accuracy.
We develop a threshold-based maintenance scheme for dynamic updates, with a provably bounded amortized insertion cost.
Extensive experiments show that DYLAN achieves superior query efficiency at similar recall levels, with favorable update and indexing costs across multiple datasets for label-filtered ANNS.
Preliminaries
Problem Definition
Let be a dataset containing objects, where each object is represented as a vector in . Given two vectors , let represent their distance, e.g., Euclidean distance in . We define nearest neighbor search as follows.
Definition 2.1 (Nearest Neighbor Search (NNS)). Given an object set consisting of objects, a query vector , and a positive integer , the nearest neighbor search returns a set of vectors with the top- smallest distances to , such that , we have .
Next, we focus on the situation in which each object in is further associated with a label set. For instance, Figure 1 shows a set of objects where each object is associated with a set of integer-valued labels, e.g., has a label set .
Figure 1. Example of a label-filtered nearest neighbor search
We define label-filtered NNS as follows.
Definition 2.2 (Label-Filtered NNS). Given an object set where each object is associated with a label set , a query is defined as , where is a query vector and is a label filtering predicate. The label-filtered NNS returns the -nearest neighbors to within the subset , i.e., the objects satisfying the label filter constraint .
In the above definition, a common notion for the filter predicate (e.g., [11]) is , which include (i) containment: given a query label set , an object with label set satisfies iff , and (ii) overlap: iff . In addition, we can combine predicates using logical connectors to form complex filters: Conjunction: iff and ; Disjunction: iff or . Here and can themselves be complex label filters.
In the example of Figure 1, given a query vector (represented by a cross) and , an NNS on returns and , which are closest to . Meanwhile, given a query label set and the predicate , the label-filtered NNS returns and , which are the closest objects to whose label sets contain both query labels 1 and 3. Now consider two query label sets and , and let . Then satisfies , while , , , satisfy . Hence, the filtered object set is , and the label-filtered NNS returns the top- objects from this set, namely and .
Exact NNS in a high-dimensional space is computationally expensive due to the curse of dimensionality [20]. Hence, approximate nearest neighbor search (ANNS) is widely used [5, 11], which offers a tradeoff between query efficiency and result quality (commonly measured by recall). In particular, let be the exact label-filtered NNS result and is the ANNS result for the same query. We define , which is when .
HNSW
Among existing ANNS algorithms, graph-based methods [17, 26, 35], notably hierarchical navigable small world (HNSW) [26], have demonstrated superior performance in terms of the trade-off between query time and accuracy. Given a set of vectors in , it builds a proximity graph , in which each vertex corresponds to a vector in and each directed edge connects a pair of vertices according to a pre-defined proximity rule under the distance metric of § 2.1. In the particular case of HNSW, consists of layers, each of which contains a proximity graph known as a navigable small world (NSW); let be the graph at layer . The number of vertices decreases exponentially from the bottom layer to the top layer , and the maximum out-degree is at and at all higher layers, where is a system parameter.
Search. To process an ANNS query , HNSW starts from an entry vertex in the highest layer and iteratively descends the layers, using the vertex closest to at the current layer as the entry point for the next. At the bottom layer , it performs a greedy search maintaining a candidate queue of discovered vertices to be expanded and a result queue of up to closest vertices to seen so far. At each step, the vertex closest to is extracted from ; the search terminates once it is farther from than the farthest vertex in , and otherwise its out-neighbors are examined and eligible vertices are inserted into both queues, with truncated to size . Finally, the top- closest vertices in are returned. A larger value of the system parameter $ef increases the number of vertices visited before termination, leading to higher recall with increased query cost, and vice versa.
Construction and updates. The proximity graph is built incrementally, by sequentially inserting vertices into an initially empty . To insert a vertex , the algorithm first determines its highest level using a truncated geometric distribution, and then inserts from level down to . At each level, a greedy layer search with construction parameter collects a bounded candidate set of vertices close to , which is then pruned to form the out-neighbor set within the out-degree limit: candidates are sorted by their distance to , and a candidate is discarded if it is dominated by an already selected , i.e., and . Each selected neighbor adds to , and is pruned in the same way if it exceeds the limit. Since has a constant expected value, building an HNSW graph of vectors takes time and space, where denotes the insertion cost of a single vector. Insertions are thus already covered by the construction procedure; for deletions, HNSW commonly employs soft deletion, marking a vertex as deleted without removing it from the graph structure and skipping it in future searches.
Our Solution: DYLAN
Next, we present the proposed DYLAN indexing scheme. § 3.1 introduces the label trie and the selective graph materialization scheme. § 3.2 and § 3.3 describe the cross-region query processing algorithm and the update mechanism based on threshold-based maintenance, respectively. These three components correspond to the three core challenges outlined in the introduction: index materialization, cross-region navigability, and dynamic maintenance. Table 2 summarizes the common notations used in the paper.
| Symbol | Meaning |
| Given set of objects and its cardinality | |
| Label set of object | |
| Distance between and | |
| Query label filter and the query vector | |
| Set of objects whose label sets satisfy | |
| Maximum out-degree of HNSW (except vertices in the bottom layer whose out-degree is ) | |
| Size of the candidate set during graph search and graph construction, respectively | |
| Label trie in DYLAN | |
| Set of objects falling into the subtree of | |
| Out-neighbor set of vertex in graph index | |
| Parent and children of node | |
| Trie node whose materialized graph used by | |
| Child with the same log_size as node | |
| Materialized graph of log size that contains |
Table 2. Frequently used notations
Index Structure
Recall from § 1 that DYLAN organizes objects in a frequency-ordered label trie and selectively materializes HNSW-style graph indices over trie-induced subsets: the trie captures how label sets relate to one another, while the graph indices preserve vector-space navigability within and across the resulting subsets. Materializing a graph index for every trie node, however, would lead to prohibitive space and update costs. DYLAN therefore selectively shares graph indices among trie nodes, while bounding the additional search space introduced by such sharing. We next describe the label trie and the selective graph materialization scheme.
Label trie. The DYLAN index employs a label trie to organize the labels of the given object set . To avoid confusion, in the following we use different terms to distinguish elements of the trie and the HNSW graph: in particular, a node always resides in the trie, whereas a vertex appears in the graph.
Each graph vertex represents an object. In the following, denotes the ID of the object represented by a vertex, whereas denotes its corresponding vector. As detailed later, graph adjacency lists store only object IDs, while the vectors are stored separately in a global vector array.
Let be the label universe, and let denote the frequency of label . We sort the labels in descending order of frequency and assign them integer IDs accordingly. We further introduce a special terminal label with frequency zero and treat it as larger than every ordinary label ID.
During trie construction, the labels in each are traversed in increasing ID order, followed by the terminal label .
This ordering is purely frequency-based and assumes no semantic hierarchy among labels. Then, the label trie is defined as follows.
Definition 3.1 (Label trie). Given the label universe of , the label trie is a rooted tree whose root is unlabeled and carries no ordinary label on its path, whose other internal nodes represent ordinary labels in , and whose leaves represent the terminal label #; ordinary-label IDs strictly increase along every root-to-leaf path.
For a node , let denote the set of ordinary labels on the path from the root to , and let denote the objects assigned to leaves in the subtree rooted at . Thus, each node represents a trie region consisting of objects that share ; this region serves as the basic unit for graph materialization described next. We use to denote the parent of , and to denote its children, where each pair indicates that child corresponds to label .
Example 3.2. Consider again the object set in Figure 1. Its label universe contains six original labels, and we append the special terminal label # to every object’s label set. Figure 2a shows the label trie in the DYLAN index. Node , for instance, corresponds to label 2 and , following the path root--. Its parent is , and its two children are (with label 3) and (with terminal label #). Accordingly, , since the ordered label sequences of all four objects begin with labels 1 and 2.
In particular, and terminate at , while and are assigned to and , respectively.
Figure 2. The DYLAN index for object set in Figure 1.
Graph indices integrated in . As will be clarified later in § 3.2, given a query label filter , we decompose the filtered object set into the union of subsets, each corresponding to a subtree rooted at a node in . Formally, we can find a node set in , where . We then aim to assign each node a graph index through which all objects in can be searched efficiently, while keeping the total index space bounded. Rather than materializing a separate graph index for every trie node, DYLAN materializes graph indices only at selected nodes and allows other nodes to share them. We bound the additional search space incurred by such sharing using the notion of an -approximate index.
Definition 3.3 (α-Approximate Index). Given a graph index built on an object set and a target object set , we say is an -approximate index for iff. and .
Here, bounds the size of the indexed object set relative to the target object set. Specifically, if is an -approximate index for , then contains all objects in and at most vertices in total, including at at most vertices outside . To bound the number of such additional vertices under graph sharing, we group trie nodes by the sizes of their corresponding trie regions. For each trie node and materialized graph , let and , respectively. If is the root or , we materialize an HNSW index on and set . Otherwise, we set , so that shares the graph index assigned to its parent. Here, points to the trie node whose materialized graph is assigned to ; hence, denotes the graph index used to search . This design yields the following guarantee2.
Lemma 3.4. For any node in , the initial graph index built by Alg. 1 is a 2-approximate index for .
By Lem. 3.4 and Def. 3.3, the initially constructed index contains all objects in and at most vertices in total, i.e., at most additional vertices outside . After dynamic insertions, this local bound is relaxed to , as will be established in Thm. 3.15. To record graph sharing in the trie, if a child of node satisfies , then , and we set . Such a child is unique, as stated below.
Lemma 3.5. For any node in the trie , there exists at most one child of such that .
Although an object may appear as a vertex in multiple materialized graph indices, its vector is stored only once. As illustrated in Figure 3, DYLAN uses a separated memory layout, in which graph adjacency lists store only neighbor object IDs, while all vectors are stored in a global vector array. This additional level of indirection may incur extra memory accesses during graph traversal. However, our experiments on HNSW show that it has negligible impact (less than 1%) on query performance. See Appendix § 9.§ 6 for details.
Figure 3. Memory Layout of DYLAN.
Example 3.6. Continuing Figure 2, we have and , giving and . Since and their logarithmic sizes differ, we materialize on . In contrast, has the same logarithmic size as its parent and therefore shares , i.e., and . As illustrated in Figure 3, although appears in multiple materialized graphs, its vector is stored only once in the global vector array and retrieved through its object ID. Note that in each example we only show the layer 0 of each graph index.
Auxiliary structures. To efficiently access the selectively materialized graphs during query processing, DYLAN maintains two auxiliary structures. For each object ID , an array points to the materialized graph with that contains as a vertex, or is NULL if no such graph exists.
We also maintain an inverted list for each label : if the edge from a node to its child is labeled , then is inserted into . During query processing, locates the graphs containing a given object and locates the trie nodes reachable by label (§ 3.2).
Example 3.7. Continuing Figure 2 and Figure 3, one can check that and , while records the materialized graphs containing : , , and .
Base index construction. Alg. 1 inserts all objects into the label trie and updates the inverted lists (Lines 1–3 and 10–18), then recursively materializes or shares graph indices according to , updating and the heavy-child pointers (Lines 19–29).
Connectivity enhancement. Finally, we apply supplementEdges as an additional connectivity enhancement (Lines 5–8 and 30–35). For an object with fewer than bottom-layer neighbors in , supplementEdges fills the missing slots using nearby objects sharing label (Lines 5–8 and 30–35). For missing edges, it uses search parameter and is applied only to the first labels. Supplemented neighbors are stored as object-ID references rather than vertices of ; hence, they do not change or its approximation bound, and locates their resident graphs when expanded.
Lem. 3.8 and Thm. 3.9 give the time and space bounds of Alg. 1.
Lemma 3.8. For an object , there are distinct nodes in the label trie such that and .
Algorithm 1: DYLAN index construction
Input: Object set with label set , HNSW parameters and Output: Root node of the DYLAN index
Create an empty trie with ; initialize and as empty
for do
,
TrieInsert
buildGraphfor to do
for do
for do
supplementEdges
return
procedure
TrieInsert:Initialize node
for to do
if then
Create new child , and set its parent
the child of corresponding to
assign to
procedure
buildGraph:if or then
for do
HNSWInsert
else
for do
buildGraph
procedure
supplementEdges:// only the bottom layer
if then
Theorem 3.9. Alg. 1 takes space and time to build the DYLAN index, where is the cost of inserting an object into the HNSW graph and is the cost of a query in DYLAN.
Query Processing
Query processing consists of three steps. First, given a filter , we identify a set of trie nodes whose corresponding trie regions form an exact disjoint cover of . Second, since the graph indices associated with these trie nodes may be disconnected, we augment them with graph indices from selected common ancestors, obtaining a graph set that improves cross-region connectivity. Finally, we jointly traverse the graphs in and apply to filter the visited objects. We describe these three steps below.
Algorithm 2: Disjoint cover set & graph index set retrieval
Input: Label trie 𝑇, inverted list 𝐼, query label filter Φ
1 𝒩 ← complexSearch(𝑇, 𝐼, Φ); 𝒢 ← ∅
2 for 𝑢 ∈ 𝒩 do
3 𝒢 ← 𝒢 ∪ {𝑢.index.𝐺}
4 for 𝑎 ∈ ancestors of 𝑢 do
5 if 𝑎 is a key ancestor of 𝒩 then
6 𝒢 ← 𝒢 ∪ {𝑎.index.𝐺}
7 return 𝒩, 𝒢
8 function contSearch(𝑇, 𝐼, 𝑓q):
9 𝒩 ← ∅; 𝑙 ← max{𝑓q}
10 for 𝑢 ∈ 𝐼𝑙 do
11 if 𝑓q ⊆ prefix(𝑢) then
12 𝒩 ← 𝒩 ∪ {𝑢}
13 return 𝒩
14 function overSearch(𝑇, 𝐼, 𝑓q):
15 𝒩 ← ∅
16 for 𝑙 ∈ 𝑓q do
17 for 𝑢 ∈ 𝐼𝑙 do
18 if prefix(𝑢) ∩ (𝑓q \ {𝑙}) = ∅ then
19 𝒩 ← 𝒩 ∪ {𝑢}
20 return 𝒩
21 function complexSearch(𝑇, 𝐼, Φ):
22 𝒩 ← ∅
23 if Φ is (Φ₀ ∧ Φ₁) or (Φ₀ ∨ Φ₁) then
24 𝒩₀ ← complexSearch(𝑇, 𝐼, Φ₀)
25 𝒩₁ ← complexSearch(𝑇, 𝐼, Φ₁)
26 for 𝑖 ∈ {0, 1} do
27 for 𝑢 ∈ 𝒩ᵢ do
28 𝐴𝑢 ← ancestors of 𝑢
29 if Φ = Φ₀ ∧ Φ₁ and ({𝑢} ∪ 𝐴𝑢) ∩ 𝒩₁−𝑖 ≠ ∅ then
30 𝒩 ← 𝒩 ∪ {𝑢}
31 if Φ = Φ₀ ∨ Φ₁ and 𝐴𝑢 ∩ 𝒩₁−𝑖 = ∅ then
32 𝒩 ← 𝒩 ∪ {𝑢}
33 return 𝒩
34 else
35 if Φ is cont(𝑓q) then return contSearch(𝑇, 𝐼, 𝑓q)
36 if Φ is over(𝑓q) then return overSearch(𝑇, 𝐼, 𝑓q)
Disjoint cover computation. Given a label filter , we first identify a set of trie nodes whose corresponding trie regions are pairwise disjoint and collectively cover all qualifying objects in .
Definition 3.10 (Disjoint Cover Set). A node set () is a disjoint cover set of a label filter if its corresponding trie regions form a partition of , i.e., and for all and .
The disjoint cover identifies the exact trie regions for . For each , DYLAN searches through , which remains a 2-approximate index for initially by Lem. 3.4, and a 4-approximate one after dynamic insertions by Thm. 3.15.
Alg. 2 computes (Lines 8–36). For containment, it scans for , the query label with the largest ID and hence the least frequent one under the build-time ordering, and retains iff (Lines 9–13). For overlap, it scans for each and retains iff , which removes nested duplicates and yields an exact disjoint cover (Lines 15–20). For a complex
Algorithm 3: Multi-Graph Search
Input: Label trie T, disjoint cover set N, graph index set G, query (q, Φ), HNSW parameters M and ef
1 entries ← ∅
2 for u ∈ N do
3 entries ← entries ∪ {HNSW_entry(u.index.G, q)}
4 Set C ← entries and mark all vertices in entries as visited
5 W ← up to the ef closest qualifying vertices in entries to q
6 Denote W_max as the current farthest vertex in W to q. If W = ∅, define δ(W_max, q) = +∞
7 while |C| > 0 do
8 v ← extract nearest vertex to q in C;
9 if |W| = ef and δ(v, q) > δ(W_max, q) then break
10 M_cnt ← 0
11 for i ← log_size(Root) downto 0 do
12 if belong_v,i ≠ NULL and belong_v,i ∈ G then
13 G ← belong_v,i[0] // only use the bottom layer
14 for w ∈ N_G(v) do
15 if w is not visited then
16 Mark w as visited
17 if f_w |= Φ then
18 M_cnt ← M_cnt + 1
19 if |W| < ef or δ(w, q) < δ(W_max, q) then
20 C ← C ∪ {w}, W ← W ∪ {w}
21 if |W| > ef then W ← W \ {W_max}
22 if M_cnt ≥ 2M then break
23 if M_cnt ≥ 2M then break
24 return W
predicate, the algorithm recursively computes the two covers. Since trie regions are either nested or disjoint, conjunction keeps the smaller region in each overlapping pair, whereas disjunction keeps the larger one (Lines 24–32). The recursion ends at containment or overlap predicates (Lines 35–36).
Key-ancestor graph selection. Once the disjoint cover set is computed, it is still challenging to process the query. For each node , the -approximate guarantee ensures that contains all objects in while introducing only a constant-factor amount of additional search space. Thus, the selected graph indices primarily serve to maintain search quality. However, these graphs may be disconnected. A naive approach is to perform a separate ANN search on each graph and subsequently merge the results, which is inefficient as the cost grows with the number of nodes in . Another approach is to perform a single HNSW search over all graphs with a shared priority queue initialized with the entry point of each graph. However, in the absence of connecting edges between different graphs, the search may become trapped in one graph and overlook closer candidates in other regions.
The composite structure of DYLAN provides a natural solution to this problem. In particular, if nodes in occur in the subtrees rooted at two or more distinct children of a trie node , the HNSW graph associated with may contain edges spanning these child subtrees. Such edges can connect otherwise isolated graph indices and guide the search across different coverage regions. We refer to selected common ancestors that provide such cross-region connectivity as key ancestor nodes, defined below.
Definition 3.11 (Key Ancestor Node). Given a disjoint cover , a trie node is a key ancestor if nodes in occur in the subtrees rooted at two or more distinct children of .
Algorithm 4: DYLAN-Query
Input: Label trie , inverted index , query , HNSW parameters , search parameters and
;
;
return the top- objects in
By Lem. 3.4, contains all objects in . It therefore includes objects from the distinct child subtrees containing these cover nodes and may contain edges that bridge their search spaces. Note that this constant-factor bound applies separately to the graph assigned to each selected trie region to ensure search quality, rather than to the union of all graphs in . Therefore, it does not bound the total number of vertices visited during multi-graph search.
Alg. 2 first computes the disjoint cover set and initializes the graph index set (Line 1). It then adds the graph assigned to each cover node (Lines 2–3) and the graphs assigned to key ancestors encountered during the upward traversals (Lines 4–6). The resulting graph index set , together with , is returned in Line 7 for the multi-graph search to be explained shortly. During the upward traversals, we record for each visited ancestor the child subtree from which it is first reached; the ancestor is marked as a key ancestor once it is reached from a second child subtree.
Theorem 3.12. Alg. 2 runs in time for a containment query, for an overlap query, and for a complex query, where is the query label with the largest ID, the set of labels appearing in , and the number of containment and overlap predicates in .
Example 3.13. Revisiting the example in Figure 2, suppose the predicate is overlap, with label set , meaning that the result objects must contain either label 4 or 5. Using inverted lists, we locate nodes , (both corresponding to label 4), (label 5). Since these nodes have disjoint subtrees of trie , they form a disjoint cover set . Then we identify and as key ancestor nodes for . We add and (since ) to the index set . Observe that graph indices of , , and in are isolated; meanwhile, the edge from to in and the edge from to in connect the three isolated indices, improving search effectiveness, explained next.
Multi-graph search. Given the disjoint cover and graph index set , we jointly search selected graphs with Alg. 3. We first use upper layers of for each to obtain entry points of layer 0 (Lines 1–3). The entry points initialize the candidate queue , while their qualifying subset initializes the result queue (Lines 4–6). As in standard HNSW search, we repeatedly expand the candidate closest to the query. Once contains vertices, the search ends when is farther than the current farthest vertex in (Lines 7–9).
For each expanded vertex , we traverse its graphs in , identified by belong, in descending order of logarithmic size (Lines 11–23).
For each unvisited neighbor , we first check if . Only qualifying neighbors trigger vector access and distance computation, and are inserted into and when appropriate (Lines 14–21). As also contains key-ancestor graphs, the traversal can follow bridge edges across different trie regions. To limit excessive expansion, we stop expanding once (Lines 22–23), where counts examined neighbors satisfying .
Example 3.14. In Figure 3, suppose that object ID is being expanded. The belong array identifies the selected graphs containing , including . When the neighbor ID is encountered in , we first test whether . If so, is used to retrieve its vector from the global vector array for distance computation.
Algorithm 5: DYLAN-Insert
Input: object , label set , HNSW construction parameters ,
TrieInsert(, )
for to do
if is newly created then initialize graph assignment of ;
if then
if then HNSWInsert(, , , );
if and then
if then
changeIndexNode()
if then
Rebuild(, )
if and then
DestroyGraph()
;
update belong
if and then
supplementEdges(, , , , , , )
if then
the child node of corresponding to ;
The complete query procedure (Alg. 4) first invokes Alg. 2 to obtain the disjoint cover set and graph set . It then runs Alg. 3 and returns the top- objects in the resulting queue.
Multi-threading extension. Although our current implementation is single-threaded, query processing extends naturally to parallel execution: different queries are independent and can be processed concurrently without modifying the index, and within a query, the entry-point searches over different cover nodes’ graph indices can also run in parallel. Parallelizing the joint multi-graph traversal would require synchronizing shared search states such as the candidate and result queues, which we leave as future work.
Index Update
Updating the DYLAN index requires keeping the graph index at each label trie node up-to-date.
For deletions, as in most ANNS indices such as HNSW described in § 2.2, we apply soft deletion and simply mark the corresponding vertices as invalid, which are skipped during search. We therefore focus on insertions, which trigger non-trivial index maintenance. The insertion of an object includes three main steps: (i) insert into the label trie , (ii) update the affected graph indices along the insertion path in , and (iii) adjust the graph index used by each node, and rebuild an index if it becomes insufficiently effective for its associated node.
The first two steps update the existing trie and graph structures locally. For (i), all operations are lightweight, using only time, where is the number of labels in . For step (ii), since an object belongs to at most graphs, the cost is bounded by , where is the number of objects in the dataset , is the cost for inserting an object into an HNSW index, and is the cost of a query in DYLAN.
The main challenge lies in the third step, where the size change of an affected subtree may alter its and hence its graph-sharing relationship. Adjusting this relationship may involve expensive index rebuilding. To avoid rebuilding an index immediately after every such change, we adopt a threshold-based maintenance strategy: we allow the effective index for each node to be a 4-approximate index (see Def. 3.3). By tolerating a slightly weaker index guarantee, we postpone expensive rebuilds until the accumulated changes exceed a threshold. The cost of rebuilding is then amortized over later updates, which bounds the amortized time complexity per insertion to .
Alg. 5 appends # and inserts into the trie (Lines 1–2), then traverses its root-to-leaf path (Lines 4–23). We omit the straightforward auxiliary routines: CopyGraph, Rebuild, and DestroyGraph copy, rebuild, and release a graph, while ChangeIndexNode redirects affected index pointers; belong is updated in Line 19.
New nodes follow the materialization rule (Line 5), and is inserted into each graph it materializes (Lines 6–7). If increases, its is copied to its heavy child and the affected pointers are redirected. Because the copy may contain objects outside , it is rebuilt on only when (Lines 8–15). If , instead shares its parent’s graph; we therefore destroy and update the pointers and belong entries (Lines 16–19). Finally, we supplement edges (Lines 20–21).
The following theorem shows the efficiency of Alg. 5 and the validity of the index structure.
Theorem 3.15. Alg. 5 inserts each new object in amortized time while ensuring that for each node , the associated index remains a 4-approximate index for .
Example 3.16. Consider again the index in Figure 2 and insert with label set . In Figure 4(b), enters the trie, the graph indices along its path (, , ) are updated, and the new node gets its graph assignment. This raises to 2, changing , so we adjust the assignments as in Figure 4(c): is copied to its heavy child , with and redirected to ; meanwhile now matches its parent in , so is removed, points to , and becomes the heavy child of . The copied may temporarily hold vertices outside ; these are retained until the logarithmic-size gap reaches the threshold.
Figure 4. An example of the object insertion in the DYLAN index from Figure 2.
New labels and frequency drift. A label unseen at build time does not restructure the trie: it is assigned the next available ID upon its first insertion, and since this ID is the largest so far, it is traversed last in , so the insertion path follows existing nodes over the previously seen labels and branches off only near the leaf. Existing IDs are never reassigned, and the terminal symbol # ranks after every ordinary label, so the ordering invariant of Def. 3.1 is preserved. However, the frequency order drifts from the true frequencies as updates accumulate, which affects efficiency only, not correctness: the label trie and the disjoint cover computation of § 3.2 are exact under any ordering, which serves solely to place frequent labels near the root, where larger trie regions admit more graph sharing. Drift has two effects: CONTSEARCH selects as the least frequent query label (Alg. 2, Line 9), so a frequent new label makes this choice suboptimal and widens the scan of ; and frequent labels placed deep in the trie make it bushier, increasing trie space. Both effects remain mild in our experiments (Figure 23–Figure 24). If desired, rebuilding whenever doubles refreshes the ordering and amortizes to the same order as Thm. 3.15.

Figure 23. Robustness: YFCC

Figure 24. Robustness: YTB-Audio
Experiments
We compare our DYLAN with state-of-the-art label-filtered ANNS methods. DYLAN is implemented in C++, and all optimizations are enabled for competitor code. All indices reside in memory, and all experiments are conducted single-threaded on a Linux machine with an Intel Xeon Gold 5320 CPU @ 2.20GHz and 1TB memory.
Datasets. The experiments involve six real datasets. Five of them, together with their query settings, are taken from the filtered-ANNS benchmark [33], which is widely tested in related research for filtered ANNS [5, 11, 28, 32]: (i) TripClick [30], a large-scale health information retrieval dataset comprising click logs from the Trip Database health web search engine; (ii) LAION1M [31], a publicly available dataset of CLIP-filtered [29] image-text pairs; (iii) YFCC [36], a 1M-vector subset of YFCC100M containing image/video embeddings and associated labels; and (iv) YTB-Audio and (v) YTB-Video [4], a benchmark of millions of videos annotated with thousands of machine-generated topical entities. We additionally build (vi) Yelp1M for RAG-style workloads: each review in the Yelp Open Dataset [3] is treated as one text chunk, embedded into a 384-dimensional vector using all-MiniLM-L6-v2 [39], and labeled with the multi-valued categories associated with the business. Table 3 reports the statistics of these 6 datasets. The last column reports , the absolute Pearson correlation between the label-set Jaccard similarity and the distance of 1M randomly sampled object pairs per dataset (using distance instead of similarity only flips the sign). A small thus indicates that objects with similar label sets are not systematically closer in the vector space.
| Dataset | Vector Type | Dim. | # Vector | # Query | Attribute Type | Med. | P90 | Max | Avg. Selectivity containment | Avg. Selectivity overlap | ||
| TripClick | text | 768 | 1,055,976 | 1000 | clinical area | 29 | 1 | 2 | 8 | 0.07 | 0.19 | 0.0055 |
| LAION1M | image | 512 | 1,000,448 | 1000 | entities, locations, etc | 30 | 2 | 2 | 3 | 0.09 | 0.19 | 0.0428 |
| YFCC | image | 192 | 1,000,000 | 1000 | classes | 181,931 | 6 | 16 | 1332 | 0.038 | 0.19 | 0.0217 |
| YTB-Audio | audio | 128 | 5,000,000 | 1000 | classes | 3862 | 3 | 5 | 23 | 0.09 | 0.19 | 0.0009 |
| YTB-Video | video | 1024 | 1,000,000 | 200 | classes | 3862 | 3 | 5 | 21 | 0.09 | 0.19 | 0.0206 |
| Yelp1M | text chunk | 384 | 1,000,000 | 1000 | business categories | 1,227 | 5 | 9 | 36 | 0.09 | 0.19 | 0.4791 |
Table 3. Summary of datasets in the experiments.
Experimental Settings
Evaluation metrics. Following prior work [5, 11, 19], we use queries per second (QPS) to measure throughput and recall (defined in § 2.1) to measure result quality, with in all experiments. We use selectivity to denote the proportion of objects satisfying the filter.
Query generation. We generate two types of queries for each dataset, with containment and overlap label constraints. We first randomly generate candidate query label sets according to label frequencies and compute their actual filter selectivities. We bucket the candidates into selectivity ranges defined by powers of two and sample queries across these buckets to obtain workloads with diverse selectivities while keeping the average selectivity around 0.09 for containment and 0.19 for overlap. Due to their skewed label distributions, the resulting averages on YFCC and TripClick may deviate from these targets.
Competitors. We include the following methods in our experimental evaluation: (i) ACORN-1 and ACORN- [28], (ii) NaviX [32], (iii) Filtered-DiskANN [19], (iv) RWalks [5], (v) UNG [11], (vi) UniFilter [41], (vii) Curator [23], (viii) Prefilter (described in § 1), (ix) our DYLAN.

Figure 6. QPS vs. recall on LAION1M.

Figure 9. QPS vs. recall on YTB-Video.
To ensure fair comparisons, we tune the build-time parameters of every method, DYLAN included, on every dataset, selecting the configuration with the best QPS at recall 0.9 across both query types. The tuning details are given in Appendix A.1. For each method, we then vary its query-time search parameter to obtain the recall-QPS tradeoff. Our code is available at [1].
Comparison Results
Query performance. Figure 5-Figure 10 plot the QPS-recall curves for the 6 datasets in our experiments. We report methods that achieve at least 0.9 recall for LAION1M and TripClick. For YFCC, YTB-Audio, YTB-Video, and Yelp1M, which are large datasets with many label categories and are therefore more challenging, most methods fail to achieve strong performance. Hence, we only report methods that achieve at least 0.8 recall. RWalks is excluded from the experiments on YFCC because its memory consumption exceeds 1 TB. Prefilter is exact and appears as a single point in the figures. The proposed DYLAN consistently yields the best overall performance across all datasets. On datasets with relatively few label categories and simple label sets, such as TripClick and LAION1M, DYLAN remains highly competitive. At 0.99 recall, it is faster than the best baseline on LAION1M and TripClick for containment queries.

Figure 5. QPS vs. recall on TripClick.

Figure 10. QPS vs. recall on Yelp1M.
On datasets with more label categories and complex label sets, DYLAN shows a substantial advantage over its competitors. YFCC contains a large number of labels with an uneven distribution. Other methods perform well only on either containment or overlap queries, but not both. example, UNG performs well on containment queries but fails to reach high recall on overlap queries. DYLAN handles both query types effectively. On YTB-Audio, DYLAN is consistently faster than the fastest baseline, with speedups of for containment and for overlap at recall at least 0.8; in the higher-recall region, the speedups are and at recall at least 0.95, respectively. On the YTB-Video dataset, Curator achieves high QPS at high recall, at a level comparable to DYLAN. This is because the YTB-Video dataset is inherently difficult to search; regardless of the index type, a large number of vectors must be accessed to achieve high recall. Curator is based on IVF, and compared to graph-based methods, it does not incur excessive random access when scanning many vectors, resulting in faster performance. Yet, on most other datasets, DYLAN outperforms Curator by one to two orders of magnitude; the exception is YFCC, where the speedup over Curator is about . On Yelp1M, a text/RAG-style workload, DYLAN also consistently outperforms the baselines for both containment and overlap queries, demonstrating its effectiveness on text chunks with real-world multi-valued category labels.

Figure 12. Impact of selectivity on the YTB-Audio.

Figure 13. Impact of selectivity on the YTB-Video.
Impact of query selectivity. Next, we evaluate the performance of overlap and containment queries under varying selectivity levels across all datasets. Note that the label distribution is discrete, so we cannot generate a large number of queries with a specific selectivity. For datasets except YTB-Audio and YTB-Video, we generate queries whose selectivity falls into five intervals: , , , , and . For YTB-Audio and YTB-Video, where label frequencies are generally lower, we create queries in the intervals to for containment queries. For each interval, we report the QPS achieved at 0.99 recall on TripClick and LAION1M. Most baselines struggle to reach high recall on challenging datasets YFCC, YTB-Audio, YTB-Video, and Yelp1M. Hence, we report QPS at 0.9 recall for these. Due to the label distributions in YFCC and TripClick, it is infeasible to generate containment queries spanning a continuous selectivity range. We therefore report only overlap queries on these two datasets, deferring the results to Appendix § 9.§ 2 for space.
Figure 11-Figure 14 present the evaluation results. On the x-axis, each tick value represents the interval . Observe that DYLAN maintains consistently high performance across all selectivity levels and datasets. On the LAION1M dataset, UNG and DYLAN achieve comparable performance when the selectivity is very low. This is because LAION1M has relatively few labels, and low-selectivity queries involve only a small number of highly similar label sets. UNG’s static LNG can capture these relationships in advance by pre-building cross edges, whereas DYLAN incurs overhead to dynamically construct edges across label sets. On the other hand, UNG performs poorly on datasets with more labels. DYLAN shows a clear advantage on datasets with a larger number of labels. On YTB-Audio, DYLAN is the only approach that maintains both high recall and high QPS across all selectivity levels and query types. The cost of Prefilter is mainly determined by , so its throughput improves as selectivity decreases, yet it remains an order of magnitude slower than DYLAN in most settings.

Figure 11. Impact of selectivity on the LAION1M.

Figure 14. Impact of selectivity on the Yelp1M.
Query performance of complex predicate. In this experiment, for each query, we randomly select two containment predicates and combine them via disjunction to construct a complex predicate. Figure 15 presents the results on the TripClick and LAION1M datasets. Owing to space constraints, the results on additional datasets are provided in Appendix § 9.§ 3. It is worth noting that only Curator and DYLAN are label-aware methods capable of handling complex predicates.
Figure 15. Complex predicate.
In comparison with other methods, our approach achieves a speedup of one to nearly two orders of magnitude on LAION1M and TripClick. This result demonstrates that our method retains high performance even in the presence of complex predicates.
Index cost. Figure 16-Figure 17 show the memory consumption and indexing time of all solutions. Note that the RAM usage of RWalks on YTB-Audio and YTB-Video is not included in the figure because it consumes 32GB on YTB-Audio and 147GB on YTB-Video, which would dominate the scale. Among methods specifically designed for label-filtered ANNS, index construction of DYLAN is faster than that of Filtered-DiskANN, but slower than UNG and RWalks, while still remaining within the same order of magnitude. This overhead arises since DYLAN spends additional time constructing the hierarchical trie-graph structure to capture label relationships. The higher index building cost of DYLAN is compensated by its superior query performance, as demonstrated in the results above.
Figure 16. Memory cost.
Figure 17. Indexing time.
For TripClick and LAION1M, the memory usage of DYLAN is comparable to that of other methods. The higher memory on other datasets is due to the larger number of label sets and more complex label relationships in these datasets, which require additional space to achieve high recall. Recall from Figure 7 that our method is the only one that achieves high performance on both query types on YFCC, outperforming other approaches by a factor of ; on YTB-Audio (Figure 8), the performance gap reaches two orders of magnitude.

Figure 7. QPS vs. recall on YFCC.

Figure 8. QPS vs. recall on YTB-Audio.
We measure the memory cost of DYLAN by component. Since each vector is stored only once in the global vector array, materializing an object in multiple graph indices adds only graph metadata, and the label trie and auxiliary structures do not dominate the memory cost. Appendix § 9.§ 4 reports the full breakdown.
Update cost. As discussed in § 1, among existing label-aware indices, only Filtered-DiskANN [19] and Curator [23] natively support both label and vector updates. UniFilter caps the size of its auxiliary label graph, so once that capacity is reached, an update performs only the HNSW (i.e., vector) part. Figure 18 compares the update time of DYLAN with that of other methods: for each dataset, we pre-build the index on 80% of the objects and then insert the remaining 20%, reporting the average insertion time. The results show that DYLAN is 3–5× faster than Filtered-DiskANN, which must perform a label-filtered ANNS during each insertion. UniFilter achieves faster update times, but this is because our datasets contain a large number of labels, and UniFilter only updates the HNSW graph. Since Curator is based on an IVF structure, it enables rapid updates, as no graph modifications are necessary—only the cluster assignments of points need to be updated. Both, however, pay for this in search performance, as our earlier experiments show. We also measure a mixed workload that interleaves the same 20% insertions with deletions of a randomly selected, disjoint 20% of the initial build set. Its update cost follows the same trends, and we defer the details to Appendix § 9.8.
Figure 18. Insertion time.
Impact of update. We evaluate two update workloads, comparing in each case an index built directly on the final object set against one that reaches the same set through updates. The insertion-only workload pre-builds on 80% of the objects and inserts the remaining 20%; the mixed workload additionally deletes a disjoint, randomly selected 20% of the initial build set. Figure 19 and Figure 20 report the two workloads on YTB-Video; the other datasets lead to the same conclusions and are deferred to Appendix § 9.8. Under both, the recall-QPS curves of the updated index stay close to those of the directly built one. This confirms the trade-off targeted by our threshold-based maintenance: keeping a static index consistent with the data would require a full rebuild per update, at about s each (Figure 17), whereas DYLAN absorbs an insertion in milliseconds (Figure 18) with essentially no loss in query accuracy. Insertions go through the maintenance scheme of § 3.3, which keeps each node’s index a 4-approximate one for its region (Thm. 3.15), while deletions are even cheaper, since they only mark vertices as invalid and leave the graph topology untouched. As in standard soft-deletion practice, invalid vertices accumulate under deletion-heavy workloads; a periodic compaction can be applied when needed.

(a)

(b)
Figure 19. Impact of insertion-only update on YTB-Video.

(a)

(b)
Figure 20. Impact of mixed update on YTB-Video.
Query cost breakdown. To attribute DYLAN’s speedup to its index design, we instrument graph-based search at recall 0.9 and record the numbers of visited points and distance computations, together with a query-time breakdown. The two counts differ because points rejected by the label filter incur no distance computation. On YTB-Audio, DYLAN visits 38.6× fewer points and performs 75.5× fewer distance computations than UNG, reducing distance-computation time by 37.3×. The remaining throughput gap mainly comes from UNG’s preprocessing for finding minimum supersets of the query label set, which is negligible in DYLAN. Figure 21-Figure 22 report the corresponding breakdowns on YFCC and YTB-Audio for both containment and overlap queries, excluding methods that cannot reach 0.9 recall. Across both datasets, the speedup is explained by the number of points the search needs to examine and the number of distance computations rather than by per-operation efficiency, indicating that it stems from the index design rather than from implementation-level optimizations.

(a)

(b)
Figure 21. Query-cost breakdown on YFCC.

(a)

(b)
Figure 22. Query-cost breakdown on YTB-Audio.
Robustness study: frequency drift and new labels. We test robustness under frequency shift and new label insertion with 50/50 dynamic workloads on YFCC and YTB-Audio (a 50/50 split rather than the 80/20 used elsewhere, for a more aggressive shift): half of the data builds the initial index and the other half is inserted, with label ordering determined only from the initial set. For frequency shift, each object is scored by the average of over its labels , and the 50% insertion suffix is sampled without replacement with probability biased toward high-score objects. This makes high-frequency-label objects appear disproportionately during insertion. For new label insertion, we maximize label diversity in the inserted half, introducing 169,496 new labels on YFCC and 3,612 on YTB-Audio (93% and 94% of their label universes). Figure 23–Figure 24 show that the performance remains close to the original, demonstrating the robustness of DYLAN to evolving label distributions.
Ablation study of optimizations. Figure 25 evaluates two optimizations of DYLAN on YTB-Audio. The corresponding results on YFCC are deferred to Appendix § 9.9 for space. First, we replace multi-graph search with independent search, which searches each graph separately and merges the results. The resulting drop in the QPS-recall tradeoff confirms that the key-ancestor graphs are important for bridging otherwise disconnected regions and avoiding local optima. Second, we disable supplementEdges. Its impact is dataset-dependent: it yields a clear improvement on YTB-Audio but little on YFCC, whose materialized graphs are already well connected.
Figure 25. Ablation study of optimizations: YTB-Audio.
Scalability study. We evaluate scalability in two dimensions: the number of vectors and the size of the label universe.
For the former, we use YFCC10M from the Big ANN Benchmarks [34], which shares the same data source as YFCC. We vary the dataset size from 2M to 10M vectors, using the same queries as on YFCC, and report QPS at a fixed recall of 0.90. Figure 26 shows that the QPS of DYLAN degrades only mildly as the dataset grows, and that DYLAN is the fastest method on both containment and overlap queries across the entire range, typically by an order of magnitude over most baselines. The only competitive baseline is Filtered-DiskANN on overlap queries, which performs well on overlap filters but has no straightforward support for containment; on containment queries it becomes the slowest method. Hence, no baseline is competitive on both predicate types, whereas DYLAN handles them within a single index.
Figure 26. Scalability study.
For the latter, we measure how the index size of each method grows with the size of the label universe across the five 1M-scale datasets, excluding the raw vector storage so that only the index structures are compared. The results, reported in Appendix § 9.§ 5, are empirically consistent with the Label Scalability column of Table 1: the index size of DYLAN and most baselines stays within a narrow range, while that of RWalks grows sharply.
Impact of label-vector correlation. DYLAN does not assume that objects with similar label sets are close in vector space. As shown in Table 3, the five widely adopted datasets all have absolute Pearson correlation , whereas the newly added Yelp1M reaches 0.48; bucketing object pairs by label-set size does not change this picture, as reported in Appendix § 9.7. We therefore use Yelp1M to isolate the effect of : keeping both the vectors and the multiset of label sets unchanged, we vary their assignment to construct six variants with from approximately 0 to 0.5 (higher values are hard to realize without synthesizing label sets). Figure 27 reports the QPS at recall 0.9, which is nearly unchanged across all correlation levels for both query types. This robustness follows from our design. Correlation mainly changes how the qualifying objects sit in the vector space relative to the trie regions, and either way the search covers them: when is high, the results concentrate within a region’s own graph; when is low, they are reached across regions via the key-ancestor graphs, so the effective search graph is the union of the graphs in rather than any single per-region graph.

Figure 27. Impact of correlation.
Impact of parameter . We also conduct experiments to evaluate the impact of on query performance and indexing cost. Interested readers are referred to Appendix § 9.10 for detailed results.
Related Work
Approximate nearest neighbor search. Existing ANNS solutions can be broadly categorized into three classes: LSH-based, PQ-based, and graph-based. Locality-sensitive hashing (LSH) and its variants, e.g., [6, 7, 14, 20, 40], provide rigorous theoretical error guarantees, but often incur considerable time and space overhead in practice. Product quantization (PQ) [21] partitions the high-dimensional vector space into multiple low-dimensional subspaces, and quantizes each subspace to compress the vectors. PQ-based methods, e.g. [8, 9, 10, 18, 24] trade result accuracy for significantly lower memory usage, achieving high scalability. Graph-based methods [15, 17, 25, 26, 35] build a proximity graph for the dataset, where vertices represent vectors and edges connect similar vectors.
ANNS with attribute filtering. There exist a plethora of research works [16, 19, 27, 38, 44, 46] on designing generic solutions for attribute-filtered ANNS. Such solutions are often less effective than specialized methods for particular filters [16, 46]. Beyond label filters, range-filtered ANNS has also been studied [22, 42, 43, 46], which is orthogonal to our work.
Conclusion
This paper presented DYLAN, a dynamic composite index for label-filtered ANNS that combines a frequency-ordered label trie, selective HNSW-style graph materialization, cross-region multi-graph search, and threshold-based index maintenance. Experiments on real datasets show that DYLAN achieves superior query efficiency at comparable recall, especially on label-rich datasets, while maintaining favorable indexing and update-cost trade-offs. Future work includes an efficient multi-threaded implementation, designing efficient index for external-memory settings, and considering more complex settings such as joint label and multi-attribute range filters.
Acknowledgments
This work is supported by the “1+1+1” CUHK-CUHK(SZ)-GDST Joint Collaboration Fund (No. 2025A0505000045) and a CUHK direct grant.
References
Additional experimental results
Parameter Tuning
Query parameters. All queries retrieve results and are executed single-threaded. For each approximate method, we vary its query-time search parameter to trace the recall–QPS tradeoff: for Filtered-DiskANN and UNG, efSearch for NaviX and ACORN, for RWalks and DYLAN, for UniFilter, and search_ef for Curator. Prefilter evaluates the label predicate exactly and performs an exact scan over the survivors, and therefore appears as a single point in the recall–QPS plots.
Construction parameters. We tune the build-time parameters of every method, DYLAN included, on every dataset under one common protocol. Each configuration is scored by its QPS at recall 0.9 — the operating point used throughout § 4 for most experiments — on containment and on overlap queries, and we select the configuration maximizing the geometric mean of the two; if only one query type reaches this recall, the configuration is scored on that type alone, and if neither does, configurations are ranked by the geometric mean of their highest attained recalls. The swept grids, with the remaining parameters fixed to the values recommended by the corresponding papers, are: with for Filtered-DiskANN; with , 6 cross-group edges and 16 query entry vectors for UNG; with beam size 4 for Curator; and with for NaviX, RWalks, ACORN-1 (, ), ACORN- (, ), UniFilter (), and DYLAN, ACORN-1 and ACORN- being swept independently. We further extend Filtered-DiskANN’s detect_common_filters to support both containment and overlap predicates. Table 6 reports the selected values. Each baseline is thus evaluated under its own best configuration rather than a default one, and DYLAN receives no larger construction budget: except on YTB-Video, its selected is 16, no larger than that of any baseline. RWalks is omitted on YFCC, as its memory consumption exceeds the available 1 TB.
| Dataset | Filtered-DiskANN | UNG | NaviX | ACORN-1 | ACORN- | Curator | RWalks | UniFilter | DYLAN |
| LAION1M | 48 | 48 | 48 | 48 | 16 | 16 | |||
| TripClick | 64 | 48 | 48 | 32 | 16 | 16 | |||
| YFCC | 48 | 48 | 48 | – | 32 | 16 | |||
| YTB-Audio | 48 | 64 | 64 | 48 | 48 | 16 | |||
| YTB-Video | 64 | 64 | 64 | 64 | 16 | 64 | |||
| Yelp1M | 48 | 64 | 64 | 48 | 64 | 16 |
Table 6. Selected construction parameters for each method and dataset. Here and denote the graph out-degree, and denote the construction candidate size, and nlist and denote Curator’s branching factor and maximum leaf size. ACORN-1 and ACORN- are tuned independently, and “–” indicates that the method is omitted due to out-of-memory.
Impact of Query Selectivity
Figure 28 shows the additional results of the impact of filter selectivity on query performance on TripClick and YFCC omitted in § 4. Recall that it is infeasible to generate containment queries spanning a continuous range of target selectivity due to the label distributions in YFCC and TripClick. We only report overlap queries on these two datasets. These results are consistent with the trends presented in § 4. It can be observed that our method generally outperforms the other approaches, except on YFCC under very low selectivity.
Figure 28. Impact of selectivity on different datasets.
Query Performance of Complex Predicate
Figure 32 shows the results on the remaining 4 datasets omitted in § 4. Our method achieves performance comparable to Curator on YFCC and YTB-Video, significantly outperforming other approaches. On the YTB-Audio dataset, our method outperforms all other methods, including Curator, by two orders of magnitude. This demonstrates that our method maintains superior performance across all datasets and under any query conditions.

Figure 32. Complex predicate.
Memory Breakdown of DYLAN Index
Table 4 reports the memory consumption of DYLAN by component. We separately account for the global vector array, object labels, the label trie, materialized graph indices, and other auxiliary structures. The “Other” category includes the belong arrays and the label inverted lists. Since each vector is stored only once in the global vector array, materializing an object in multiple graph indices only introduces graph metadata rather than additional vector copies. The breakdown also reflects the different characteristics of the datasets. For example, YFCC incurs a relatively large trie cost due to its large label universe and complex label sets, whereas the graph indices constitute the main additional cost on YTB-Audio. Overall, the trie and auxiliary structures remain moderate compared with the vector and graph storage, confirming that the additional structures introduced by DYLAN do not dominate its memory consumption.
| Dataset | Vector | Labels | Trie | Graph | Other | Total |
| TripClick | 3.02 | 0.06 | 0.01 | 0.41 | 0.06 | 3.56 |
| LAION1M | 1.91 | 0.05 | 0.01 | 0.48 | 0.06 | 2.52 |
| YFCC | 0.72 | 0.07 | 1.09 | 0.77 | 0.15 | 2.80 |
| YTB-Audio | 2.39 | 0.27 | 0.28 | 3.08 | 0.38 | 6.38 |
| YTB-Video | 3.82 | 0.05 | 0.09 | 2.12 | 0.08 | 6.15 |
| Yelp1M | 1.43 | 0.06 | 0.03 | 0.71 | 0.08 | 2.32 |
Table 4. DYLAN memory cost breakdown by component (GB)
Figure 31. Ablation study of optimizations: YFCC.
Label Scalability
Sec. 4 evaluates scalability along two dimensions, the number of vectors and the size of the label universe, and reports only the former; we report the latter here. Figure 29 plots the index size of each method against the number of distinct labels over the five 1M-scale datasets (all datasets except YTB-Audio), whose label universes span from 29 labels on TripClick to 181,931 on YFCC. Since all five datasets hold roughly the same number of vectors, the raw vector payload is essentially constant across them and would mask the differences of interest; we therefore exclude it for every method and report only the index structures built on top of it. The index size of DYLAN grows by only 4.4× across the entire span and follows a trend similar to most existing methods, indicating that neither the label trie nor the auxiliary structures grows substantially with the label universe. RWalks is the clear exception: it encodes labels into vector-like representations, so its index size increases sharply as labels accumulate, which is also why it exceeds the available 1 TB on YFCC. These results are consistent with the Label Scalability column of Table 1 and confirm that DYLAN scales effectively to large label universes.
Figure 29. Index size vs. .
Impact of Memory Layout
DYLAN stores vectors and adjacency lists separately, so reaching a neighbor’s vector requires an extra indirection through its object ID. To isolate the cost of this indirection, we compare two layouts of a standard HNSW graph on LAION1M in Figure 30. The first follows the original implementation of HNSWlib [2], where each vertex stores its vector contiguously with its adjacency list, avoiding an additional pointer dereference to locate the vector. The second is the separated layout used by DYLAN, where adjacency lists hold only object IDs and all vectors reside in a global array, so expanding a neighbor requires a second random access into that array. The two layouts achieve nearly identical query performance, differing by less than 1%: the indirection is amortized over the distance computation that follows it, and the vector array is accessed in the same order regardless of layout. In DYLAN the effect is even smaller, since many visited neighbors fail the label filter and are skipped without any vector access at all. Together with Figure 30, this confirms that the separated layout, which lets an object appear in multiple materialized graphs without duplicating its vector, does not trade memory for query latency.
Figure 30. Memory layout.

Figure 33. Impact of insertion-only update: containment queries.
Label-Vector Correlation by Label-Set Size
We analyze whether label-set similarity is correlated with vector proximity, and whether such correlation depends on how many labels the objects carry. For each dataset, we uniformly sample 1M distinct object pairs and compute the Pearson correlation between their label-set Jaccard similarity and their distance, reporting since negating the distance only flips the sign. A single overall correlation can be misleading here, as pairs with few labels and pairs with many labels differ in both their Jaccard values and their distance distributions: the overall coefficient absorbs these cross-bucket shifts under a global normalization. We therefore also group the sampled pairs by into four ranges—[1, 2], [3, 5], [6, 10], and —and report the within-bucket correlation for each.

Figure 34. Impact of insertion-only update: overlap queries.

Figure 35. Impact of mixed updates: containment queries.
Table 5 reports the results. On the five benchmark datasets, the overall correlations are consistently very small, the largest being on LAION1M, and the bucket-level correlations stay below 0.0617 in almost all cases. The only exception is the [1, 2] bucket of YFCC with , which draws on just 3,774 sampled pairs and therefore has limited support. Grouping by label-set size thus does not change the picture: on these datasets, objects with similar label sets are not systematically closer in the vector space, at any label-set size. Yelp1M is the exception by construction: its labels are business categories attached to review text, so an overall of 0.4791 together with consistently high bucket-level correlations makes it a complementary workload on which label similarity does carry information about vector proximity.
Table 5. Absolute Pearson correlation between label-set Jaccard similarity and distance. Object pairs are grouped by max().

Figure 36. Impact of mixed updates: overlap queries.
Impact of Update
Sec. 4.2 reports both update workloads on YTB-Video only. Here we give the results on the remaining datasets: Figs. 33 and 34 for the insertion-only workload, Figs. 35 and 36 for the mixed workload, in each case for containment and overlap queries respectively, and Fig. 37 for the update time under the mixed workload. The protocol follows Sec. 4.2: an index built directly on the final object set is compared against one that reaches the same set through updates. Across all datasets and both workloads, the two recall-QPS curves stay close, confirming that the threshold-based maintenance scheme preserves index quality under insertions, and that lazy deletions leave the graph topology untouched.
Ablation study of optimizations
Sec. 4.2 evaluates the two optimizations of DYLAN on YTB-Audio only; Fig. 31 reports the same ablation on YFCC. Replacing multi-graph search with independent search again degrades the QPS-recall tradeoff, most visibly on overlap queries, where a filter spans more trie regions and the key-ancestor graphs therefore matter most for cross-region connectivity. Disabling SUPPLEMENTEDGES, in contrast, has almost no effect on YFCC: its materialized graphs are already well connected, so the supplemented edges are rarely traversed. This confirms the dataset-dependence noted in Sec. 4.2—the multi-graph search is the essential component, while SUPPLEMENTEDGES helps only where per-region connectivity is insufficient.
Impact of Parameter on DYLAN
Fig. 38 shows the impact of . As we can observe, increasing leads to higher indexing time but strengthens the quality of the graph, resulting in better performance. This improvement in connectivity enhances query performance. Based on the experimental results, we set as the default parameter as it gains a nice trade-off between the query performance and indexing cost.

Figure 37. Mixed update time.
Figure 38. Impact of to query and indexing cost.
Proofs
Proof of Lemma 3.4. Let . By construction, is an ancestor of , so , and shares only when . Hence, for some ,
which implies . Therefore, is a 2-approximate index for by Definition 3.3.
Proof of Lemma 3.5. We prove by contradiction. Assume that node has two distinct children and such that and . Without loss of generality, let . Since is the set of all objects in the subtree of and , are disjoint subtrees, we have . Consequently, , which is a contradiction. Therefore, the assumption is false, and the lemma holds.
Proof of Lemma 3.8. For the object , it only belongs to the graph indexes of its ancestors in the Trie; hence there are at most such nodes. Moreover, because a node maintains its own index () only when , the number of distinct values along the root-to-leaf path is . Therefore, can belong to at most such indexes. Combining the two bounds yields the result.
Proof of Theorem 3.9. The space complexity of our index consists of the following components: the Trie structure, the inverted lists , the belong array, and all the HNSW graph indexes. Each object is inserted into the Trie by traversing (or creating) at most nodes. Hence the Trie and the associated inverted lists require space. The indicates whether object belongs to a graph of logarithmic size . Since can take at most distinct values, the total size of the belong array is . Through Lemma 3.8, the overall space occupied by all graph indexes is
Summing the three parts, the total space complexity is
For construction time, we first build the Trie and the inverted lists, which takes time. Initializing and updating the belong array costs . The dominant cost is the HNSW insertion: each object is inserted into at most graphs, and each insertion has complexity (the time to insert one point into a plain HNSW graph). For lines 5–8 of Algo. 1, each element is subject to the supplementEdges operation at most times, where the cost of each such operation is , which denotes the cost of performing one query on DYLAN. Hence the total construction time is
Proof of Theorem 3.12. For containment queries, we access ancestors of nodes in and examine the prefix of each node. For overlap queries, we access ancestors of nodes from the inverted list of every label in and also examine the prefix of each node. The number of ancestors of a node is , and each ancestor can be accessed in time. Now consider a complex query. For any node where , if is inspected during a merge step in ComplexSearch, the associated cost is . In the worst-case scenario, every merge operation in ComplexSearch includes . Since a complex predicate comprising containment or overlap queries entails merge operations, the overall complexity, when combined with the costs of ContainmentSearch and OverlapSearch, is given by
Therefore, the theorem holds.
Proof of Theorem 3.15. Operations on the Trie and updates to the inverted lists take time. Traversing the path from the root to the leaf also costs . For HNSW insertion and supplementEdge, an object belongs to at most graphs, so the total insertion cost is . Adjusting the index assigned to a node may involve copying or deleting an index; one such operation on node costs and is triggered only when a change in alters . After one such change, the next copy/delete on this index occurs after insertions into . Hence the amortized cost per insertion contributed by copying/deleting is . Since an insertion affects at most subtrees, the total amortized overhead from copying/deleting is .
Rebuilding the index for node costs . After a rebuild, contains at most nodes, and the next rebuild is triggered after further insertions. Therefore, the amortized cost per insertion from rebuilding is . Because an insertion touches at most graphs, the total amortized rebuilding overhead is . Summing all parts yields an amortized time complexity per update of . Moreover, the graph is allowed to contain at most vertices, so
assuring that the index remains a 4-approximate index for .
Received 17 April 2026; revised 19 August 2026; accepted 12 September 2026.
References
- [1]2026. Code and technical report. https://github.com/CUHK-DBGroup/DYLAN.
- [2]2026. Hnswlib. https://github.com/nmslib/hnswlib.
- [3]2026. Yelp Dataset. https://business.yelp.com/data-resources/open-dataset.
- [4]Sami Abu-El-Haija, Nisarg Kothari, Jooseong Lee, Paul Natsev, George Toderici, Balakrishnan Varadarajan, and Sudheendra Vijayanarasimhan. 2016. YouTube-8M: A Large-Scale Video Classification Benchmark. CoRR abs/1609.08675 (2016).
- [5]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), 212:1–212:26.DOI
- [6]Alexandr Andoni and Piotr Indyk. 2008. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 51, 1 (2008), 117–122.
- [7]Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, and Ludwig Schmidt. 2015. Practical and Optimal LSH for Angular Distance. In NeurIPS. 1225–1233.arxiv.org/abs/1509.02897
- [8]Fabien André, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. 2015. Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan. Proc. VLDB Endow. 9, 4 (2015), 288–299.
- [9]Artem Babenko and Victor S. Lempitsky. 2015. Tree quantization for large-scale similarity search and classification. In CVPR. 4240–4248.
- [10]Davis W. Balock and John V. Guttg. 2017. Bolt: Accelerated Data Mining with Fast Vector Compression. In SIGKDD. 727–735.
- [11]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), 246:1–246:27.DOI
- [12]Cheng Chen, Chenzhe Jin, Yunan Zhang, Sasha Podolsky, Chun Wu, Szu-Po Wang, Eric Hanson, Zhou Sun, Robert Walzer, and Jianguo Wang. 2024. SingleStore-V: An Integrated Vector Database System in SingleStore. Proc. VLDB Endow. 17, 12 (2024), 3772–3785.
- [13]Dechuang Chen, Bing Chen, Jianwei Lu, Zhiwei Wu, Zeyu Yang, Qiang Gu, Fangyuan Zhang, Sibo Wang, Zeyuan Yu, Caihua Yin, Wenchao Zhou, and Feifei Li. 2026. Nova: A Multi-Purpose Vector Engine for Low-Latency, Multi-Tenant, and Cross-Table Hybrid Retrieval. Proc. VLDB Endow. 19, 12 (2026), 4453–4465.DOI
- [14]Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. 2004. Locality-sensitive hashing scheme based on p-stable distributions. In PoCG. 253–262.DOI
- [15]Wei Dong, Moses Charikar, and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures. In WWW. 577–586.DOI
- [16]Joshua Engels, Benjamin Landrum, Shangdi Yu, Laxman Dhulipala, and Julian Shun. 2024. Approximate Nearest Neighbor Search with Window Filters. In ICML.arxiv.org/abs/2402.00943
- [17]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.arxiv.org/abs/1707.00143
- [18]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), 167.arxiv.org/abs/2405.12497
- [19]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. Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters. In WWW. 3406–3416.DOI
- [20]Piotr Indyk and Rajeev Motwani. 1998. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In STOC. 604–613.
- [21]Hervé 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.DOI
- [22]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), 148:1–148:26.DOI
- [23]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. CoRR abs/2601.01291 (2026).arxiv.org/abs/2601.01291
- [24]Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2021. Billion-Scale Similarity Search with GPUs. IEEE Trans. Big Data 7, 3 (2021), 535–547.
- [25]Yury Malkov, Alexander Ponamorenko, Andrey Logvinov, and Vladimir Krylov. 2014. Approximate nearest neighbor algorithm based on navigable small world graphs. Inf. Syst. 45 (2014), 61–68.DOI
- [26]Yury A. Malkov and Dmitry 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.
- [27]Yusuke Matsui, Ryota Hinami, and Shin’ichi Satoh. 2018. Reconfigurable Inverted Index. In MM. 1715–1723.arxiv.org/abs/1808.03969
- [28]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), 120.arxiv.org/abs/2403.04871
- [29]Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. 2021. Learning Transferable Visual Models From Natural Language Supervision. In ICML, Vol. 139. 8748–8763.arxiv.org/abs/2103.00020
- [30]Navid Rekabzaz, Oleg Lesota, Markus Schedl, Jon Brassey, and Carsten Eickhoff. 2021. TripClick: The Log Files of a Large Health Web Search Engine. In SIGIR. 2507–2513.
- [31]Christoph Schuhmann, Richard Vencu, Romain Beaumont, Robert Kaczmarczyk, Clayton Mullis, Aarush Katta, Theo Coombes, Jenia Jitsev, and Aran Komatsuzaki. 2021. LAION-400M: Open Dataset of CLIP-Filtered 400 Million Image-Text Pairs. CoRR abs/2111.02114 (2021).
- [32]Gaurav Sehgal and Semih Salihoglu. 2025. NaviX: A Native Vector Index Design for Graph DBMSs With Robust Predicate-Agnostic Search Performance. Proc. VLDB Endow. 18, 11 (2025), 4438–4451.
- [33]Jiayang Shi, Yuzheng Cai, and Weiguo Zheng. 2025. Filtered Approximate Nearest Neighbor Search: A Unified Benchmark and Systematic Experimental Study [Experiment, Analysis & Benchmark]. arXiv preprint arXiv:2509.07789 (2025).arxiv.org/abs/2509.07789
- [34]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 preprint arXiv:2409.17424 (2024).arxiv.org/abs/2409.17424
- [35]Suhas Jayaram Subramanya, Divya C. Vaidya, Harsha Vardhan Simhadri, Ravishankar Krishnaswamy, and Rohan Kadekodi. 2019. Rand-NSG: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In NeurIPS, 13748–13758.
- [36]Bart Thomee, David A Shamma, Gerald Friedland, Benjamin Elizalde, Karl Ni, Douglas Poland, Damian Borth, and Li-Jia Li. 2016. Fcc100m: The new data in multimedia research. Commun. ACM 59, 2 (2016), 64–73.DOI
- [37]Jiang Wang, Xin Wen, Ruicheng Liu, Xiaoyan Tang, Yongqing Xie, Pinghua Wang, Ji Sun, Yanfeng Zhang, Yong Li, Guoliang Li, Xiaoguang Ren, Wen Nie, and Chunbo Li. 2025. GaussDB-Vector: A Large-Scale Persistent Real-Time Vector Database for LLM Applications. Proc. VLDB Endow. 18, 12 (2025), 4951–4963.DOI
- [38]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 Qiu, Ruiyi Jiang, Yi Wei, and Charles Xie. 2021. Milvus: A Purpose-Built Vector Data Management System. In SIGMOD. 2614–2627.DOI
- [39]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. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.).
- [40]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.DOI
- [41]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), 1–26.DOI
- [42]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), 239:1–239:26.arxiv.org/abs/2409.02571
- [43]Fangyuan Zhang, Mengxu Jiang, Guanhao Hou, Jieming Shi, Hua Fan, Wenchao Zhou, Feifei Li, and Sibo Wang. 2025. Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 3, 3 (2025), 152:1–152:26.DOI
- [44]Qianxi Zhang, Shuotao Xu, Qi Chen, Guoxin Sui, Jiadong Xie, Zhizhen Cai, Yaoqi Chen, Yinxuan He, Yuqing Yang, Fan Yang, Mao Yang, and Longzhou. 2023. VBASE: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity. In OSDI. 377–395.
- [45]Justin Zobel and Alistair Moffat. 1998. Inverted files versus signature files for text indexing. TODS 23, 4 (1998), 453–490.DOI
- [46]Chaoji Zou, 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), 69:1–69:26.














