betaFeedback

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.

MethodLabel AwareContainmentOverlapComplexVectorLabel setLabel Scalability
ACORN [28]×LowLowLow✓✓High
NaviX [32]×LowLowLow✓✓High
Filtered-DiskANN [19]✓LowMedium×✓✓High
RWalks [5]✓MediumMedium×××Low
UNG [11]✓MediumMedium×✓×High
UniFilter [41]✓Low××✓PartialHigh
Curator [23]✓MediumMediumMedium✓✓High
DYLAN (Ours)✓HighHighHigh✓✓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 TT capturing the relationships among label sets in the data: each non-root node u∈Tu \in T carries a label and a prefix formed by the labels on the root-to-uu 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 uu form the trie region of uu. The second phase selectively materializes multiple HNSW-style graph indices embedded in TT, 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 q\mathbf{q} with a label predicate Φ\Phi, the filtered search space often spans multiple trie regions. DYLAN first identifies a set N\mathcal{N} 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 N\mathcal{N}; 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 OO be a dataset containing nn objects, where each object is represented as a vector in Rd\mathbb{R}^{d}. Given two vectors p,q∈Rd\mathbf{p},\mathbf{q} \in\mathbb{R}^{d}, let δ(p,q)\delta(\mathbf{p},\mathbf{q}) represent their distance, e.g., Euclidean distance in Rd\mathbb{R}^{d}. We define nearest neighbor search as follows.

Definition 2.1 (Nearest Neighbor Search (NNS)). Given an object set OO consisting of nn objects, a query vector q∈Rd\mathbf{q} \in\mathbb{R}^{d}, and a positive integer k≤nk \le n, the nearest neighbor search returns a set of vectors R∗={o1∗,o2∗,…,ok∗}⊆OR^{*} = \{\mathbf{o}_{1}^{*}, \mathbf{o}_{2}^{*}, \ldots, \mathbf{o}_{k}^{*}\} \subseteq O with the top-kk smallest distances to q\mathbf{q}, such that ∀o∗∈R∗,∀o∈R∗\forall\mathbf{o}^{*} \in R^{*}, \forall\mathbf{o} \in R^{*}, we have δ(o∗,q)≤δ(o,q)\delta(\mathbf{o}^{*},\mathbf{q}) \le\delta(\mathbf{o},\mathbf{q}).

Next, we focus on the situation in which each object in OO is further associated with a label set. For instance, Figure 1 shows a set of objects O={o1,o2,…,o6}O = \{\mathbf{o}_{1}, \mathbf{o}_{2}, \ldots, \mathbf{o}_{6}\} where each object is associated with a set of integer-valued labels, e.g., o1\mathbf{o}_{1} has a label set {1,2}\{1, 2\}.

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 OO where each object o∈O\mathbf{o} \in O is associated with a label set fof_{\mathbf{o}}, a query is defined as Q=(q,Φ,k)Q = (\mathbf{q}, \Phi, k), where q∈Rd\mathbf{q} \in\mathbb{R}^{d} is a query vector and Φ\Phi is a label filtering predicate. The label-filtered NNS returns the min⁡(k,∣OΦ∣)\min(k, |O_{\Phi}|)-nearest neighbors to q\mathbf{q} within the subset OΦ={o∈O∣fo⊨Φ}O_{\Phi} = \{\mathbf{o} \in O \mid f_{\mathbf{o}} \models\Phi\}, i.e., the objects satisfying the label filter constraint Φ\Phi.

In the above definition, a common notion for the filter predicate Φ\Phi (e.g., [11]) is Φ::=cont⁡(F)∣over⁡(F)∣(Φ∧Φ)∣(Φ∨Φ)\Phi::= \operatorname{cont}(F) \mid\operatorname{over}(F) \mid(\Phi\land\Phi) \mid(\Phi\lor\Phi), which include (i) containment: given a query label set fqf_q, an object oo with label set fof_o satisfies fo⊨cont⁡(fq)f_o \models\operatorname{cont}(f_q) iff fq⊆fof_q \subseteq f_o, and (ii) overlap: fo⊨over⁡(fq)f_o \models\operatorname{over}(f_q) iff fq∩fo≠∅f_q \cap f_o \ne\emptyset. In addition, we can combine predicates using logical connectors to form complex filters: Conjunction: fo⊨(Φ1∧Φ2)f_o \models(\Phi_1 \land\Phi_2) iff fo⊨Φ1f_o \models\Phi_1 and fo⊨Φ2f_o \models\Phi_2; Disjunction: fo⊨(Φ1∨Φ2)f_o \models(\Phi_1 \lor\Phi_2) iff fo⊨Φ1f_o \models\Phi_1 or fo⊨Φ2f_o \models\Phi_2. Here Φ1\Phi_1 and Φ2\Phi_2 can themselves be complex label filters.

In the example of Figure 1, given a query vector q\mathbf{q} (represented by a cross) and k=2k = 2, an NNS on OO returns o1o_1 and o5o_5, which are closest to q\mathbf{q}. Meanwhile, given a query label set fq={1,3}f_q = \{1, 3\} and the predicate Φ=cont⁡(fq)\Phi= \operatorname{cont}(f_q), the label-filtered NNS returns o5o_5 and o6o_6, which are the closest objects to q\mathbf{q} whose label sets contain both query labels 1 and 3. Now consider two query label sets fq,1={3,6}f_{q,1} = \{3, 6\} and fq,2={1,2}f_{q,2} = \{1, 2\}, and let Φ=cont⁡(fq,1)∨cont⁡(fq,2)\Phi= \operatorname{cont}(f_{q,1}) \lor\operatorname{cont}(f_{q,2}). Then o6o_6 satisfies cont⁡(fq,1)\operatorname{cont}(f_{q,1}), while o1o_1, o2o_2, o5o_5, o6o_6 satisfy cont⁡(fq,2)\operatorname{cont}(f_{q,2}). Hence, the filtered object set is {o1,o2,o5,o6}\{o_1, o_2, o_5, o_6\}, and the label-filtered NNS returns the top-kk objects from this set, namely o1o_1 and o5o_5.

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 R∗R^* be the exact label-filtered NNS result and RR is the ANNS result for the same query. We define Recall⁡(R)=∣R∩R∗∣∣R∗∣\operatorname{Recall}(R) = \frac{|R \cap R^*|}{|R^*|}, which is ∣R∩R∗∣k\frac{|R \cap R^*|}{k} when ∣OΦ∣≥k|O_\Phi| \ge k.

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 OO of nn vectors in Rd\mathbb{R}^d, it builds a proximity graph GG, in which each vertex corresponds to a vector in OO and each directed edge connects a pair of vertices according to a pre-defined proximity rule under the distance metric δ\delta of § 2.1. In the particular case of HNSW, GG consists of LL layers, each of which contains a proximity graph known as a navigable small world (NSW); let H[i]H[i] be the graph at layer ii. The number of vertices decreases exponentially from the bottom layer H[0]H[0] to the top layer H[L−1]H[L - 1], and the maximum out-degree is 2M2M at H[0]H[0] and MM at all higher layers, where MM is a system parameter.

Search. To process an ANNS query q\mathbf{q}, HNSW starts from an entry vertex in the highest layer H[L−1]H[L - 1] and iteratively descends the layers, using the vertex closest to q\mathbf{q} at the current layer as the entry point for the next. At the bottom layer H[0]H[0], it performs a greedy search maintaining a candidate queue CC of discovered vertices to be expanded and a result queue WW of up to efef closest vertices to q\mathbf{q} seen so far. At each step, the vertex closest to q\mathbf{q} is extracted from CC; the search terminates once it is farther from q\mathbf{q} than the farthest vertex in WW, and otherwise its out-neighbors are examined and eligible vertices are inserted into both queues, with WW truncated to size efef. Finally, the top-kk closest vertices in WW 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 GG is built incrementally, by sequentially inserting vertices into an initially empty GG. To insert a vertex uu, the algorithm first determines its highest level LuL_u using a truncated geometric distribution, and then inserts uu from level H[Lu]H[L_u] down to H[0]H[0]. At each level, a greedy layer search with construction parameter efce_{fc} collects a bounded candidate set of vertices close to uu, which is then pruned to form the out-neighbor set N(u)N(u) within the out-degree limit: candidates are sorted by their distance to uu, and a candidate vv is discarded if it is dominated by an already selected ww, i.e., δ(u,w)<δ(u,v)\delta(u,w) < \delta(u,v) and δ(v,w)<δ(u,v)\delta(v,w) < \delta(u,v). Each selected neighbor vv adds uu to N(v)N(v), and N(v)N(v) is pruned in the same way if it exceeds the limit. Since LuL_u has a constant expected value, building an HNSW graph of nn vectors takes O(n⋅cupd)O(n \cdot c_{\mathrm{upd}}) time and O(nM)O(nM) space, where cupdc_{\mathrm{upd}} 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.

SymbolMeaning
O,nO, nGiven set of objects and its cardinality
fof_oLabel set of object oo
δ(u,v)\delta(u,v)Distance between uu and vv
Φ,q\Phi, qQuery label filter and the query vector
OΦO_{\Phi}Set of objects whose label sets satisfy Φ\Phi
MMMaximum out-degree of HNSW (except vertices in the bottom layer whose out-degree is 2M2M)
ef,efcef, ef_cSize of the candidate set during graph search and graph construction, respectively
TTLabel trie in DYLAN
OuO_uSet of objects falling into the subtree of u∈Tu \in T
NG(v)N_G(v)Out-neighbor set of vertex vv in graph index GG
log_size⁡(u)\operatorname{log\_size}(u)⌊log⁡2∣Ou∣⌋\lfloor\log_2 |O_u| \rfloor
u.p,u.chu.p, u.chParent and children of node u∈Tu \in T
u.indexu.indexTrie node whose materialized graph used by uu
u.chheavyu.ch_{\mathrm{heavy}}Child with the same log_size as node u∈Tu \in T
belongo,ibelong_{o,i}Materialized graph of log size ii that contains oo

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 TT to organize the labels of the given object set OO. 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, oio_i denotes the ID of the object represented by a vertex, whereas oi∈Rd\mathbf{o}_i \in\mathbb{R}^d 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 L=⋃o∈Ofo\mathcal{L} = \bigcup_{o\in O} f_o be the label universe, and let freq⁡(l)=∣{o∈O∣l∈fo}∣\operatorname{freq}(l) = \lvert\{o \in O \mid l \in f_o\}\rvert denote the frequency of label ll. We sort the labels in descending order of frequency and assign them integer IDs 1,2,…,∣L∣1, 2, \ldots, \lvert\mathcal{L}\rvert 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 fof_o 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 TT is defined as follows.

Definition 3.1 (Label trie). Given the label universe L\mathcal{L} of OO, the label trie TT is a rooted tree whose root is unlabeled and carries no ordinary label on its path, whose other internal nodes represent ordinary labels in L\mathcal{L}, and whose leaves represent the terminal label #; ordinary-label IDs strictly increase along every root-to-leaf path.

For a node u∈Tu \in T, let prefix⁡(u)⊆L\operatorname{prefix}(u) \subseteq\mathcal{L} denote the set of ordinary labels on the path from the root to uu, and let OuO_u denote the objects assigned to leaves in the subtree rooted at uu. Thus, each node uu represents a trie region OuO_u consisting of objects that share prefix⁡(u)\operatorname{prefix}(u); this region serves as the basic unit for graph materialization described next. We use u.pu.p to denote the parent of uu, and u.ch={(l,c)}u.ch = \{(l,c)\} to denote its children, where each pair (l,c)(l,c) indicates that child cc corresponds to label ll.

Example 3.2. Consider again the object set OO 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 TT in the DYLAN index. Node u2u_2, for instance, corresponds to label 2 and prefix⁡(u2)={1,2}\operatorname{prefix}(u_2) = \{1,2\}, following the path root-u1u_1-u2u_2. Its parent is u2.p=u1u_2.p = u_1, and its two children u2.chu_2.ch are u4u_4 (with label 3) and u10u_{10} (with terminal label #). Accordingly, Ou2={o1,o2,o5,o6}O_{u_2} = \{o_1,o_2,o_5,o_6\}, since the ordered label sequences of all four objects begin with labels 1 and 2.

In particular, o1o_1 and o2o_2 terminate at u10u_{10}, while o5o_5 and o6o_6 are assigned to u8u_8 and u9u_9, respectively.

Figure 2. The DYLAN index for object set OO in Figure 1.

Graph indices integrated in TT. As will be clarified later in § 3.2, given a query label filter Φ\Phi, we decompose the filtered object set OΦO_{\Phi} into the union of subsets, each corresponding to a subtree rooted at a node in TT. Formally, we can find a node set N\mathcal{N} in TT, where ⋃u∈NOu=OΦ\bigcup_{u\in\mathcal{N}} O_u = O_{\Phi}. We then aim to assign each node u∈Nu \in\mathcal{N} a graph index through which all objects in OuO_u 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 α\alpha-approximate index.

Definition 3.3 (α-Approximate Index). Given a graph index GG built on an object set OGO_G and a target object set OO, we say GG is an α\alpha-approximate index for OO iff. O⊆OGO \subseteq O_G and ∣OG∣/∣O∣≤α|O_G|/|O| \leq\alpha.

Here, α\alpha bounds the size of the indexed object set relative to the target object set. Specifically, if GG is an α\alpha-approximate index for OuO_u, then GG contains all objects in OuO_u and at most α∣Ou∣\alpha|O_u| vertices in total, including at at most (α−1)∣Ou∣(\alpha- 1)|O_u| vertices outside OuO_u. 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 uu and materialized graph GG, let log_size⁡(u)=⌊log⁡2∣Ou∣⌋\operatorname{log\_size}(u) = \lfloor\log_2 |O_u| \rfloor and log_size⁡(G)=⌊log⁡2∣OG∣⌋\operatorname{log\_size}(G) = \lfloor\log_2 |O_G| \rfloor, respectively. If uu is the root or log_size⁡(u)<log_size⁡(u.p)\operatorname{log\_size}(u) < \operatorname{log\_size}(u.p), we materialize an HNSW index u.Gu.G on OuO_u and set u.index=uu.index = u. Otherwise, we set u.index=u.p.indexu.index = u.p.index, so that uu shares the graph index assigned to its parent. Here, u.indexu.index points to the trie node whose materialized graph is assigned to uu; hence, u.index.Gu.index.G denotes the graph index used to search OuO_u. This design yields the following guarantee2.

Lemma 3.4. For any node uu in TT, the initial graph index u.index.Gu.index.G built by Alg. 1 is a 2-approximate index for OuO_u.

By Lem. 3.4 and Def. 3.3, the initially constructed index u.index.Gu.index.G contains all objects in OuO_u and at most 2∣Ou∣2|O_u| vertices in total, i.e., at most ∣Ou∣|O_u| additional vertices outside OuO_u. After dynamic insertions, this local bound is relaxed to 4∣Ou∣4|O_u|, as will be established in Thm. 3.15. To record graph sharing in the trie, if a child cc of node uu satisfies log_size⁡(c)=log_size⁡(u)\operatorname{log\_size}(c) = \operatorname{log\_size}(u), then c.index=u.indexc.index = u.index, and we set u.chheavy=cu.ch_{\mathrm{heavy}} = c. Such a child is unique, as stated below.

Lemma 3.5. For any node uu in the trie TT, there exists at most one child cc of uu such that log_size⁡(c)=log_size⁡(u)\operatorname{log\_size}(c) = \operatorname{log\_size}(u).

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 ∣Ou1∣=6|O_{u_1}| = 6 and ∣Ou3∣=2|O_{u_3}| = 2, giving log⁡_size(u1)=2\log\_size(u_1) = 2 and log⁡_size(u3)=1\log\_size(u_3) = 1. Since u1=u3.pu_1 = u_3.p and their logarithmic sizes differ, we materialize u3.Gu_3.G on Ou3O_{u_3}. In contrast, u11u_{11} has the same logarithmic size as its parent u3u_3 and therefore shares u3.Gu_3.G, i.e., u11.index=u3.index=u3u_{11}.index = u_3.index = u_3 and u3.cheavy=u11u_3.c_{heavy} = u_{11}. As illustrated in Figure 3, although o6o_6 appears in multiple materialized graphs, its vector o6o_6 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 oo, an array belongo,ibelong_{o,i} points to the materialized graph u.Gu.G with log⁡_size(u)=i\log\_size(u) = i that contains oo as a vertex, or is NULL if no such graph exists.

We also maintain an inverted list IlI_l for each label ll: if the edge from a node uu to its child cc is labeled ll, then cc is inserted into IlI_l. During query processing, belongbelong locates the graphs containing a given object and IlI_l locates the trie nodes reachable by label ll (§ 3.2).

Example 3.7. Continuing Figure 2 and Figure 3, one can check that I4={u3,u5}I_4 = \{u_3, u_5\} and I5={u6}I_5 = \{u_6\}, while belongbelong records the materialized graphs containing o5o_5: u5.Gu_5.G, u4.Gu_4.G, and Root.GRoot.G.

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 log⁡_size\log\_size, updating belongbelong 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 oo with fewer than 2M2M bottom-layer neighbors in u.index.Gu.index.G, supplementEdges fills the missing slots using nearby objects sharing label ll (Lines 5–8 and 30–35). For k′k' missing edges, it uses search parameter ⌊efck′/(2M)⌋\left\lfloor e^{f_ck'/(2M)} \right\rfloor and is applied only to the first lth=O(log⁡n)l_{th} = O(\log n) labels. Supplemented neighbors are stored as object-ID references rather than vertices of u.index.Gu.index.G; hence, they do not change OGO_G or its approximation bound, and belongbelong 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 oo, there are O(min⁡{∣fo∣,log⁡n})O(\min\{|f_o|, \log n\}) distinct nodes uu in the label trie TT such that u.index=uou.index = u_o and o∈Ouo \in O_u.

Algorithm 1: DYLAN index construction

Input: Object set OO with label set L\mathcal{L}, HNSW parameters MM and efce_{fc} Output: Root node of the DYLAN index

  1. Create an empty trie TT with RootRoot; initialize II and belongbelong as empty

  2. for o∈Oo \in O do

    1. fo←fo∪{#}f_o \leftarrow f_o \cup\{\#\}, TrieInsert(Root,o)(Root,o)

  3. buildGraph(Root,O,M,efc)(Root,O,M,e_{fc})

  4. for l←1l \leftarrow1 to lthl_{th} do

    1. for u∈Ilu \in I_l do

      1. for o∈Ouo \in O_u do

        1. supplementEdges(T,I,l,o,u,M,efc)(T,I,l,o,u,M,e_{fc})

  5. return RootRoot

  6. procedure TrieInsert(Root,o)(Root,o):

    1. Initialize node u←Rootu \leftarrow Root

    2. for idx←1idx \leftarrow1 to ∣fo∣\lvert f_o\rvert do

      1. if ∄(l,c)∈u.ch,l=fo[idx]\nexists(l,c) \in u.ch, l=f_o[idx] then

        1. Create new child cc, and set its parent c.p←uc.p \leftarrow u

        2. Ifo[idx]←Ifo[idx]∪{c}I_{f_o[idx]} \leftarrow I_{f_o[idx]} \cup\{c\}

        3. u.ch←u.ch∪{(fo[idx],c)}u.ch \leftarrow u.ch \cup\{(f_o[idx],c)\}

      2. u←u \leftarrow the child of uu corresponding to fo[idx]f_o[idx]

    3. assign oo to uu

  7. procedure buildGraph(u,Ou,M,efc)(u,O_u,M,e_{fc}):

    1. if u=Rootu=Root or log⁡_size(u)<log⁡_size(u.p)\log\_size(u)<\log\_size(u.p) then

      1. for o∈Ouo \in O_u do

        1. HNSWInsert(u.G,o,M,efc)(u.G,o,M,e_{fc})

        2. belongo,log⁡_size(u)←u.Gbelong_{o,\log\_size(u)} \leftarrow u.G

      2. u.index←uu.index \leftarrow u

    2. else

      1. u.index←u.p.indexu.index \leftarrow u.p.index

      2. u.p.chheavy←uu.p.ch_{heavy} \leftarrow u

    3. for (l,c)∈u.ch(l,c) \in u.ch do

      1. buildGraph(c,Oc,M,efc)(c,O_c,M,e_{fc})

  8. procedure supplementEdges(T,I,l,o,u,M,efc)(T,I,l,o,u,M,e_{fc}):

    1. k′←2M−∣Nu.index.G(o)∣k' \leftarrow2M-\lvert N_{u.index.G}(o)\rvert // only the bottom layer

    2. if k′>0k'>0 then

      1. C←Alg. 4(T,I,(o,cont⁡({l})),M,⌊efc∗k′2M⌋,⌊efc∗k′2M⌋)C \leftarrow\text{Alg. 4}(T,I,(o,\operatorname{cont}(\{l\})),M,\lfloor\frac{e_{fc} \ast k'}{2M}\rfloor,\lfloor\frac{e_{fc} \ast k'}{2M}\rfloor)

      2. N′←Prune(o,k′,C∖(Nu.index.G(o)∪{o}))N' \leftarrow\text{Prune}(o,k',C\setminus(N_{u.index.G}(o)\cup\{o\}))

      3. Nu.index.G(o)←Nu.index.G(o)∪N′N_{u.index.G}(o)\leftarrow N_{u.index.G}(o)\cup N'

Theorem 3.9. Alg. 1 takes O(nlog⁡n+∑o∈O(M⋅min⁡{∣fo∣,log⁡n}+∣fo∣))O(n\log n+\sum_{o\in O}(M\cdot\min\{\lvert f_o\rvert,\log n\}+\lvert f_o\rvert)) space and O(nlog⁡n+∑o∈O∣fo∣+∑o∈Omin⁡{∣fo∣,log⁡n}(cupd+cq))O(n\log n+\sum_{o\in O}\lvert f_o\rvert+\sum_{o\in O}\min\{\lvert f_o\rvert,\log n\}(c_{upd}+c_q)) time to build the DYLAN index, where cupdc_{upd} is the cost of inserting an object into the HNSW graph and cqc_q is the cost of a query in DYLAN.

Query Processing

Query processing consists of three steps. First, given a filter Φ\Phi, we identify a set N\mathcal{N} of trie nodes whose corresponding trie regions OuO_u form an exact disjoint cover of OΦO_\Phi. 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 G\mathcal{G} that improves cross-region connectivity. Finally, we jointly traverse the graphs in G\mathcal{G} and apply Φ\Phi 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 Φ\Phi, we first identify a set N\mathcal{N} of trie nodes whose corresponding trie regions are pairwise disjoint and collectively cover all qualifying objects in OΦO_{\Phi}.

Definition 3.10 (Disjoint Cover Set). A node set N\mathcal{N} (N⊆T\mathcal{N} \subseteq T) is a disjoint cover set of a label filter Φ\Phi if its corresponding trie regions form a partition of OΦO_{\Phi}, i.e., ⋃u∈NOu=OΦ\bigcup_{u \in\mathcal{N}} O_u = O_{\Phi} and Oui∩Ouj=∅O_{u_i} \cap O_{u_j} = \varnothing for all i≠ji \ne j and ui,uj∈Nu_i, u_j \in\mathcal{N}.

The disjoint cover N\mathcal{N} identifies the exact trie regions for Φ\Phi. For each u∈Nu \in\mathcal{N}, DYLAN searches OuO_u through u.index.Gu.\mathit{index}.G, which remains a 2-approximate index for OuO_u initially by Lem. 3.4, and a 4-approximate one after dynamic insertions by Thm. 3.15.

Alg. 2 computes N\mathcal{N} (Lines 8–36). For containment, it scans IlI_l for l=max⁡fql = \max f_q, the query label with the largest ID and hence the least frequent one under the build-time ordering, and retains uu iff fq⊆prefix⁡(u)f_q \subseteq\operatorname{prefix}(u) (Lines 9–13). For overlap, it scans IlI_l for each l∈fql \in f_q and retains uu iff prefix⁡(u)∩(fq∖{l})=∅\operatorname{prefix}(u) \cap(f_q \setminus\{l\}) = \varnothing, 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 NN is computed, it is still challenging to process the query. For each node u∈Nu \in N, the α\alpha-approximate guarantee ensures that u.index.Gu.\mathit{index}.G contains all objects in OuO_u 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 NN. 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 NN occur in the subtrees rooted at two or more distinct children of a trie node aa, the HNSW graph associated with aa 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 NN, a trie node aa is a key ancestor if nodes in NN occur in the subtrees rooted at two or more distinct children of aa.

Algorithm 4: DYLAN-Query

Input: Label trie TT, inverted index II, query (q,Φ)(q, \Phi), HNSW parameters MM, search parameters efef and kk

  1. N,G←Algorithm⁡2(T,I,Φ)\mathcal{N}, \mathcal{G} \leftarrow\operatorname{Algorithm} 2(T, I, \Phi);

  2. results←Algorithm⁡3(T,N,G,(q,Φ),M,ef)results \leftarrow\operatorname{Algorithm} 3(T, \mathcal{N}, \mathcal{G}, (q, \Phi), M, ef);

  3. return the top-kk objects in resultsresults

By Lem. 3.4, a.index⁡.Ga.\operatorname{index}.G contains all objects in OaO_a. 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 G\mathcal{G}. Therefore, it does not bound the total number of vertices visited during multi-graph search.

Alg. 2 first computes the disjoint cover set N\mathcal{N} and initializes the graph index set G\mathcal{G} (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 G\mathcal{G}, together with N\mathcal{N}, 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 O(∑u∈Ilmax⁡∣prefix⁡(u)∣)O\left(\sum_{u \in I_{l_{\max}}} \lvert\operatorname{prefix}(u)\rvert\right) time for a containment query, O(∑l∈fq∑u∈Il∣prefix⁡(u)∣)O\left(\sum_{l \in f_q}\sum_{u \in I_l} \lvert\operatorname{prefix}(u)\rvert\right) for an overlap query, and O(∑l∈LΦ∑u∈Il∣prefix⁡(u)∣⋅∣Φ∣)O\left(\sum_{l \in L_{\Phi}}\sum_{u \in I_l} \lvert\operatorname{prefix}(u)\rvert\cdot\lvert\Phi\rvert\right) for a complex query, where lmax⁡l_{\max} is the query label with the largest ID, LΦL_{\Phi} the set of labels appearing in Φ\Phi, and ∣Φ∣\lvert\Phi\rvert the number of containment and overlap predicates in Φ\Phi.

Example 3.13. Revisiting the example in Figure 2, suppose the predicate Φ\Phi is overlap, with label set fq={4,5}f_q = \{4, 5\}, meaning that the result objects must contain either label 4 or 5. Using inverted lists, we locate nodes u3u_3, u5u_5 (both corresponding to label 4), u6u_6 (label 5). Since these nodes have disjoint subtrees of trie TT, they form a disjoint cover set N={u3,u5,u6}\mathcal{N} = \{u_3, u_5, u_6\}. Then we identify u4u_4 and u1u_1 as key ancestor nodes for N={u3,u5,u6}\mathcal{N} = \{u_3, u_5, u_6\}. We add u4.Gu_4.G and Root⁡.G\operatorname{Root}.G (since u1.index⁡=Root⁡u_1.\operatorname{index} = \operatorname{Root}) to the index set G\mathcal{G}. Observe that graph indices of u5u_5, u6u_6, and u3u_3 in N\mathcal{N} are isolated; meanwhile, the edge from o5o_5 to o3o_3 in Root⁡.G\operatorname{Root}.G and the edge from o5o_5 to o6o_6 in u4.Gu_4.G connect the three isolated indices, improving search effectiveness, explained next.

Multi-graph search. Given the disjoint cover N\mathcal{N} and graph index set G\mathcal{G}, we jointly search selected graphs with Alg. 3. We first use upper layers of u.index⁡.Gu.\operatorname{index}.G for each u∈Nu \in\mathcal{N} to obtain entry points of layer 0 (Lines 1–3). The entry points initialize the candidate queue CC, while their qualifying subset initializes the result queue WW (Lines 4–6). As in standard HNSW search, we repeatedly expand the candidate vv closest to the query. Once WW contains ε\varepsilon vertices, the search ends when vv is farther than the current farthest vertex Wmax⁡W_{\max} in WW (Lines 7–9).

For each expanded vertex vv, we traverse its graphs in G\mathcal{G}, identified by belong, in descending order of logarithmic size (Lines 11–23).

For each unvisited neighbor ww, we first check if w⊨Φw \models\Phi. Only qualifying neighbors trigger vector access and distance computation, and are inserted into CC and WW when appropriate (Lines 14–21). As G\mathcal{G} also contains key-ancestor graphs, the traversal can follow bridge edges across different trie regions. To limit excessive expansion, we stop expanding vv once Mcnt≥2MM_{\mathrm{cnt}} \ge2M (Lines 22–23), where McntM_{\mathrm{cnt}} counts examined neighbors satisfying Φ\Phi.

Example 3.14. In Figure 3, suppose that object ID o5o_5 is being expanded. The belong array identifies the selected graphs containing o5o_5, including Root⁡.G\operatorname{Root}.G. When the neighbor ID o6o_6 is encountered in Root⁡.G\operatorname{Root}.G, we first test whether fo6⊨Φf_{o_6} \models\Phi. If so, o6o_6 is used to retrieve its vector o⃗6\vec{o}_6 from the global vector array for distance computation.

Algorithm 5: DYLAN-Insert

Input: object oo, label set fof_o, HNSW construction parameters MM, efce_{fc}

  1. fo←fo∪{#}f_o \leftarrow f_o \cup\{\#\}

  2. TrieInsert(RootRoot, oo)

  3. u←Rootu \leftarrow Root

  4. for idx←1idx \leftarrow1 to ∣fo∣+1\lvert f_o \rvert+ 1 do

  5. &nbsp;&nbsp;&nbsp;&nbsp;if uu is newly created then initialize graph assignment of uu;

  6. &nbsp;&nbsp;&nbsp;&nbsp;if u.index=uu.index = u then

  7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if o∉u.Go \notin u.G then HNSWInsert(u.Gu.G, oo, MM, efce_{fc});

  8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if ∣Ou∣>1\lvert O_u \rvert> 1 and log_size⁡(u)≠⌊log⁡2(∣Ou∣−1)⌋\operatorname{log\_size}(u) \ne\left\lfloor\log_2\left(\lvert O_u\rvert- 1\right)\right\rfloor then

  9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if u.chheavy≠NULLu.ch_{\mathrm{heavy}} \ne NULL then

  10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u.chheavy.G←CopyGraph⁡(u.G)u.ch_{\mathrm{heavy}}.G \leftarrow\operatorname{CopyGraph}(u.G)

  11. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c←u.chheavyc \leftarrow u.ch_{\mathrm{heavy}}

  12. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;changeIndexNode(cc)

  13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if log_size⁡(c.G)>log_size⁡(c)+1\operatorname{log\_size}(c.G) > \operatorname{log\_size}(c) + 1 then

  14. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rebuild(c.Gc.G, OcO_c)

  15. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u.chheavy←NULLu.ch_{\mathrm{heavy}} \leftarrow NULL

  16. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if u≠Rootu \ne Root and log_size⁡(u)=log_size⁡(u.p)\operatorname{log\_size}(u) = \operatorname{log\_size}(u.p) then

  17. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;DestroyGraph(u.Gu.G)

  18. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u.p.chheavy←uu.p.ch_{\mathrm{heavy}} \leftarrow u; u.index←u.p.indexu.index \leftarrow u.p.index

  19. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;update belong

  20. &nbsp;&nbsp;&nbsp;&nbsp;if idx>1idx > 1 and fo[idx−1]≤lthf_o[idx - 1] \le l_{th} then

  21. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;supplementEdges(TT, II, fo[idx−1]f_o[idx - 1], oo, uu, MM, efce_{fc})

  22. &nbsp;&nbsp;&nbsp;&nbsp;if idx≤∣fo∣idx \le\lvert f_o \rvert then

  23. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u←u \leftarrow the child node of uu corresponding to fo[idx]f_o[idx];

The complete query procedure (Alg. 4) first invokes Alg. 2 to obtain the disjoint cover set N\mathcal{N} and graph set G\mathcal{G}. It then runs Alg. 3 and returns the top-kk 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 oo includes three main steps: (i) insert oo into the label trie TT, (ii) update the affected graph indices along the insertion path in TT, 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 O(∣fo∣)O(|f_o|) time, where ∣fo∣|f_o| is the number of labels in oo. For step (ii), since an object belongs to at most O(min⁡{∣fo∣,log⁡n})O(\min\{|f_o|,\log n\}) graphs, the cost is bounded by O(min⁡{∣fo∣,log⁡n}⋅(cupd+cq))O(\min\{|f_o|,\log n\}\cdot(c_{\mathrm{upd}}+c_q)), where nn is the number of objects in the dataset OO, cupdc_{\mathrm{upd}} is the cost for inserting an object into an HNSW index, and cqc_q 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 log_size⁡\operatorname{log\_size} 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 O(∣fo∣M+min⁡{∣fo∣,log⁡n}⋅(cupd+cq))O(|f_o|M+\min\{|f_o|,\log n\}\cdot(c_{\mathrm{upd}}+c_q)).

Alg. 5 appends # and inserts oo 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 oo is inserted into each graph it materializes (Lines 6–7). If log_size⁡(u)\operatorname{log\_size}(u) increases, its u.Gu.G is copied to its heavy child cc and the affected pointers are redirected. Because the copy may contain objects outside OcO_c, it is rebuilt on OcO_c only when log_size⁡(c.G)>log_size⁡(c)+1\operatorname{log\_size}(c.G)>\operatorname{log\_size}(c)+1 (Lines 8–15). If log_size⁡(u)=log_size⁡(u.p)\operatorname{log\_size}(u)=\operatorname{log\_size}(u.p), uu instead shares its parent’s graph; we therefore destroy u.Gu.G 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 O(∣fo∣M+min⁡{∣fo∣,log⁡n}(cupd+cq))O(|f_o|M+\min\{|f_o|,\log n\}(c_{\mathrm{upd}}+c_q)) time while ensuring that for each node uu, the associated index remains a 4-approximate index for OuO_u.

Example 3.16. Consider again the index in Figure 2 and insert o7o_7 with label set {1,2,3,5}\{1,2,3,5\}. In Figure 4(b), o7o_7 enters the trie, the graph indices along its path (Root.G\mathit{Root}.G, u4.Gu_4.G, u6.Gu_6.G) are updated, and the new node u12u_{12} gets its graph assignment. This raises ∣Ou6∣|O_{u_6}| to 2, changing log_size⁡(u6)\operatorname{log\_size}(u_6), so we adjust the assignments as in Figure 4(c): u6.Gu_6.G is copied to its heavy child u7u_7, with u7.indexu_7.\mathit{index} and u9.indexu_9.\mathit{index} redirected to u7u_7; meanwhile u6u_6 now matches its parent u4u_4 in log_size⁡\operatorname{log\_size}, so u6.Gu_6.G is removed, u6.indexu_6.\mathit{index} points to u4u_4, and u6u_6 becomes the heavy child of u4u_4. The copied u7.Gu_7.G may temporarily hold vertices outside Ou7O_{u_7}; 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 fof_o, 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 max⁡{fq}\max\{f_q\} as the least frequent query label (Alg. 2, Line 9), so a frequent new label makes this choice suboptimal and widens the scan of IlI_l; 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 nn doubles refreshes the ordering and amortizes to the same order as Thm. 3.15.

Robustness plots for YFCC: containment and overlap

Figure 23. Robustness: YFCC

Robustness plots for YTB-Audio: containment and overlap

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 ∣r∣|r|, the absolute Pearson correlation between the label-set Jaccard similarity and the L2L_2 distance of 1M randomly sampled object pairs per dataset (using distance instead of similarity only flips the sign). A small ∣r∣|r| thus indicates that objects with similar label sets are not systematically closer in the vector space.

DatasetVector TypeDim.# Vector# QueryAttribute Type∣L∣|L|∣fo∣|f_o| Med.∣fo∣|f_o| P90∣fo∣|f_o| MaxAvg. Selectivity containmentAvg. Selectivity overlap∣r∣|r|
TripClicktext7681,055,9761000clinical area291280.070.190.0055
LAION1Mimage5121,000,4481000entities, locations, etc302230.090.190.0428
YFCCimage1921,000,0001000classes181,93161613320.0380.190.0217
YTB-Audioaudio1285,000,0001000classes386235230.090.190.0009
YTB-Videovideo10241,000,000200classes386235210.090.190.0206
Yelp1Mtext chunk3841,000,0001000business categories1,22759360.090.190.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 k=10k = 10 in all experiments. We use selectivity (O,Φ)=∣OΦ∣/∣O∣(O, \Phi) = |O_{\Phi}|/|O| 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-yy [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.

QPS versus recall on LAION1M; panels (a) Containment and (b) Overlap

Figure 6. QPS vs. recall on LAION1M.

QPS versus recall on YTB-Video; panels (a) Containment and (b) Overlap

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 5×5 \times faster than the best baseline on LAION1M and TripClick for containment queries.

QPS versus recall on TripClick; methods DYLAN, ACORN-1, ACORN-γ, NaviX, UNG, Filtered-DiskANN, Curator, UniFilter, RWalks, and Prefilter; panels (a) Containment and (b) Overlap

Figure 5. QPS vs. recall on TripClick.

QPS versus recall on Yelp1M; panels (a) Containment and (b) Overlap

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 5.7×5.7 \times for containment and 2.3×2.3 \times for overlap at recall at least 0.8; in the higher-recall region, the speedups are 43.5×43.5 \times and 8.7×8.7 \times 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 5×5 \times. 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.

Impact of selectivity on the YTB-Audio

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

Impact of selectivity on the YTB-Video

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: [2−2,2−1)[2^{-2}, 2^{-1}), [2−3,2−2)[2^{-3}, 2^{-2}), [2−4,2−3)[2^{-4}, 2^{-3}), [2−5,2−4)[2^{-5}, 2^{-4}), and [2−6,2−5)[2^{-6}, 2^{-5}). For YTB-Audio and YTB-Video, where label frequencies are generally lower, we create queries in the intervals [2−3,2−2)[2^{-3}, 2^{-2}) to [2−7,2−6)[2^{-7}, 2^{-6}) 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 ii represents the interval [2−(i+1),2−i)[2^{-(i+1)}, 2^{-i}). 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 ∣OΦ∣|O_{\Phi}|, so its throughput improves as selectivity decreases, yet it remains an order of magnitude slower than DYLAN in most settings.

Impact of selectivity on the LAION1M

Figure 11. Impact of selectivity on the LAION1M.

Impact of selectivity on the Yelp1M

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 3–5×3\text{--}5\times; on YTB-Audio (Figure 8), the performance gap reaches two orders of magnitude.

QPS versus recall on YFCC; panels (a) Containment and (b) Overlap

Figure 7. QPS vs. recall on YFCC.

QPS versus recall on YTB-Audio; panels (a) Containment and (b) Overlap

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 2×1042 \times10^{4} 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.

QPS versus Recall for containment queries on YTB-Video

(a)

QPS versus Recall for overlap queries on YTB-Video

(b)

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

QPS versus Recall for containment queries on YTB-Video

(a)

QPS versus Recall for overlap queries on YTB-Video

(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.

Query-cost breakdown for containment queries on YFCC

(a)

Query-cost breakdown for overlap queries on YFCC

(b)

Figure 21. Query-cost breakdown on YFCC.

Query-cost breakdown for containment queries on YTB-Audio

(a)

Query-cost breakdown for overlap queries on YTB-Audio

(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 log⁡(1+freq⁡(l))\log(1 + \operatorname{freq}(l)) over its labels ll, 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 ∣r∣≤0.0428|r| \le0.0428, 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 ∣r∣|r|: keeping both the vectors and the multiset of label sets unchanged, we vary their assignment to construct six variants with ∣r∣|r| 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 ∣r∣|r| is high, the results concentrate within a region’s own graph; when ∣r∣|r| is low, they are reached across regions via the key-ancestor graphs, so the effective search graph is the union of the graphs in G\mathcal{G} rather than any single per-region graph.

Impact of correlation, showing QPS versus $|\mathrm{Pearson}|$ for containment and overlap

Figure 27. Impact of correlation.

Impact of parameter efce_{f_c}. We also conduct experiments to evaluate the impact of efce_{f_c} 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 k=10k = 10 results and are executed single-threaded. For each approximate method, we vary its query-time search parameter to trace the recall–QPS tradeoff: LsearchL_{\mathrm{search}} for Filtered-DiskANN and UNG, efSearch for NaviX and ACORN, efef for RWalks and DYLAN, LL for UniFilter, and search_ef for Curator. Prefilter evaluates the label predicate exactly and performs an exact L2L_{2} 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: (Lbuild,R)∈{(96,64),(144,96),(192,128),(240,160)}(L_{\mathrm{build}}, R) \in\{(96, 64), (144, 96), (192, 128), (240, 160)\} with α=1.2\alpha= 1.2 for Filtered-DiskANN; (R,L)∈{(16,100),(32,100),(32,200),(48,200)}(R, L) \in\{(16, 100), (32, 100), (32, 200), (48, 200)\} with α=1.2\alpha= 1.2, 6 cross-group edges and 16 query entry vectors for UNG; (nlist,Bmax)∈{(16,64),(32,128),(64,256),(64,512)}(n_{\mathrm{list}}, B_{\mathrm{max}}) \in\{(16, 64), (32, 128), (64, 256), (64, 512)\} with beam size 4 for Curator; and M∈{16,32,48,64}M \in\{16, 32, 48, 64\} with efc=400ef_{c} = 400 for NaviX, RWalks, ACORN-1 (γ=1\gamma= 1, Mβ=2MM_{\beta} = 2M), ACORN-γ\gamma (γ=100\gamma= 100, Mβ=64M_{\beta} = 64), UniFilter (Mp=nM_{p} = n), and DYLAN, ACORN-1 and ACORN-γ\gamma 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 MM is 16, no larger than that of any baseline. RWalks is omitted on YFCC, as its memory consumption exceeds the available 1 TB.

DatasetFiltered-DiskANNUNGNaviXACORN-1ACORN-γ\gammaCuratorRWalksUniFilterDYLAN
LAION1M(144,96)(144, 96)(48,200)(48, 200)484848(64,512)(64, 512)481616
TripClick(192,128)(192, 128)(32,200)(32, 200)644848(64,512)(64, 512)321616
YFCC(240,160)(240, 160)(16,100)(16, 100)484848(64,512)(64, 512)–3216
YTB-Audio(240,160)(240, 160)(48,200)(48, 200)486464(64,512)(64, 512)484816
YTB-Video(240,160)(240, 160)(48,200)(48, 200)646464(64,512)(64, 512)641664
Yelp1M(240,160)(240, 160)(16,100)(16, 100)486464(64,512)(64, 512)486416

Table 6. Selected construction parameters for each method and dataset. Here RR and MM denote the graph out-degree, LbuildL_{\mathrm{build}} and LL denote the construction candidate size, and nlist and Bmax⁡B_{\max} denote Curator’s branching factor and maximum leaf size. ACORN-1 and ACORN-γ\gamma 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.

Complex predicate query performance plots for YFCC, YTB-Audio, YTB-Video, and Yelp1M

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.

DatasetVectorLabelsTrieGraphOtherTotal
TripClick3.020.060.010.410.063.56
LAION1M1.910.050.010.480.062.52
YFCC0.720.071.090.770.152.80
YTB-Audio2.390.270.283.080.386.38
YTB-Video3.820.050.092.120.086.15
Yelp1M1.430.060.030.710.082.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. ∣L∣|\mathcal{L}|.

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.

Impact of insertion-only update plots for containment queries on LAION1M, TripClick, YFCC, YTB-Audio, and Yelp1M

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 rr between their label-set Jaccard similarity and their L2L_2 distance, reporting ∣r∣\lvert r\rvert 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 max⁡(∣fi∣,∣fj∣)\max(\lvert f_i\rvert, \lvert f_j\rvert) into four ranges—[1, 2], [3, 5], [6, 10], and >10> 10—and report the within-bucket correlation for each.

QPS versus recall for overlap queries across LAION1M, TripClick, YFCC, YTB-Audio, and Yelp1M

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

QPS versus recall for containment queries across LAION1M, TripClick, YFCC, YTB-Audio, and Yelp1M

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 ∣r∣=0.0428\lvert r\rvert= 0.0428 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 ∣r∣=0.1891\lvert r\rvert= 0.1891, 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 ∣r∣|r| 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.

Dataset[1, 2][3, 5][6, 10]> 10Overall
TripClick0.00550.00780.0528–0.0055
LAION1M0.04080.0617––0.0428
YFCC0.18910.00280.00730.00120.0217
YTB-Audio0.00180.00110.00280.00310.0009
YTB-Video0.02160.02090.02170.00470.0206
Yelp1M0.57420.50890.47110.44580.4791

Table 5. Absolute Pearson correlation ∣r∣|r| between label-set Jaccard similarity and L2L_2 distance. Object pairs are grouped by max(∣fi∣,∣fj∣|f_i|, |f_j|).

Impact of mixed updates: overlap queries

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 efce_f c on DYLAN

Fig. 38 shows the impact of efce_f c. As we can observe, increasing efce_f c 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 efc=400e_{fc} = 400 as the default parameter as it gains a nice trade-off between the query performance and indexing cost.

Mixed update time bar chart with methods DYLAN, ACORN-1, ACORN-$\gamma$, NaviX, UNG, Filtered-DiskANN, Curator, UniFilter, and RWalks across TripClick, LAION1M, YFCC, YTB-Audio, YTB-Video, and Yelp1M

Figure 37. Mixed update time.

Figure 38. Impact of efce_{fc} to query and indexing cost.

Proofs

Proof of Lemma 3.4. Let v=u.indexv = u.\mathrm{index}. By construction, vv is an ancestor of uu, so Ou⊆OvO_u \subseteq O_v, and uu shares v.Gv.G only when log⁡_size(u)=log⁡_size(v)\log\_\mathrm{size}(u) = \log\_\mathrm{size}(v). Hence, for some kk,

2k≤∣Ou∣≤∣Ov∣<2k+12^k \le|O_u| \le|O_v| < 2^{k+1}

which implies ∣Ov∣<2∣Ou∣|O_v| < 2|O_u|. Therefore, v.Gv.G is a 2-approximate index for OuO_u by Definition 3.3.

Proof of Lemma 3.5. We prove by contradiction. Assume that node uu has two distinct children c1c_1 and c2c_2 such that log⁡2(∣Oc1∣)=log⁡2(∣Ou∣)\log_2(|O_{c_1}|) = \log_2(|O_u|) and log⁡2(∣Oc2∣)=log⁡2(∣Ou∣)\log_2(|O_{c_2}|) = \log_2(|O_u|). Without loss of generality, let ∣Oc1∣≤∣Oc2∣|O_{c_1}| \le|O_{c_2}|. Since OuO_u is the set of all objects in the subtree of uu and c1c_1, c2c_2 are disjoint subtrees, we have ∣Ou∣≥∣Oc1∣+∣Oc2∣≥2∣Oc1∣|O_u| \ge|O_{c_1}| + |O_{c_2}| \ge2|O_{c_1}|. Consequently, log⁡2(∣Ou∣)≥log⁡2(2∣Oc1∣)=log⁡2(∣Oc1∣)+1=log⁡2(∣Ou∣)+1\log_2(|O_u|) \ge\log_2(2|O_{c_1}|) = \log_2(|O_{c_1}|) + 1 = \log_2(|O_u|) + 1, which is a contradiction. Therefore, the assumption is false, and the lemma holds.

Proof of Lemma 3.8. For the object oo, it only belongs to the graph indexes of its ancestors in the Trie; hence there are at most O(∣fo∣)O(|f_o|) such nodes. Moreover, because a node uu maintains its own index (u.index=uu.\mathrm{index} = u) only when log⁡_size(u)≠log⁡_size(u.p)\log\_\mathrm{size}(u) \ne\log\_\mathrm{size}(u.p), the number of distinct log⁡_size\log\_\mathrm{size} values along the root-to-leaf path is O(log⁡n)O(\log n). Therefore, oo can belong to at most O(log⁡n)O(\log n) 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 II, the belong array, and all the HNSW graph indexes. Each object oo is inserted into the Trie by traversing (or creating) at most ∣fo∣|f_o| nodes. Hence the Trie and the associated inverted lists require O(∑o∈O∣fo∣)O(\sum_{o \in O}|f_o|) space. The belongo,i\mathrm{belong}_{o,i} indicates whether object oo belongs to a graph of logarithmic size ii. Since ii can take at most O(log⁡n)O(\log n) distinct values, the total size of the belong array is O(nlog⁡n)O(n\log n). Through Lemma 3.8, the overall space occupied by all graph indexes is

O(∑o∈Omin⁡{∣fo∣,log⁡n}M).O\left(\sum_{o\in O}\min\{|f_o|,\log n\}M\right).

Summing the three parts, the total space complexity is

O(nlog⁡n+∑o∈O∣fo∣+∑o∈Omin⁡{∣fo∣,log⁡n}M).O\left(n\log n+\sum_{o\in O}|f_o|+\sum_{o\in O}\min\{|f_o|,\log n\}M\right).

For construction time, we first build the Trie and the inverted lists, which takes O(∑o∈O∣fo∣)O\left(\sum_{o\in O}|f_o|\right) time. Initializing and updating the belong array costs O(nlog⁡n)O(n\log n). The dominant cost is the HNSW insertion: each object oo is inserted into at most min⁡{∣fo∣,log⁡n}\min\{|f_o|,\log n\} graphs, and each insertion has complexity cupdc_{\mathrm{upd}} (the time to insert one point into a plain HNSW graph). For lines 5–8 of Algo. 1, each element oo is subject to the supplementEdges operation at most min⁡{lth,∣fo∣}\min\{l_{\mathrm{th}},|f_o|\} times, where the cost of each such operation is cqc_q, which denotes the cost of performing one query on DYLAN. Hence the total construction time is

O(nlog⁡n+∑o∈O∣fo∣+∑o∈Omin⁡{∣fo∣,log⁡n}(cupd+cq)).O\left(n\log n+\sum_{o\in O}|f_o|+\sum_{o\in O}\min\{|f_o|,\log n\}(c_{\mathrm{upd}}+c_q)\right).

Proof of Theorem 3.12. For containment queries, we access ancestors of nodes in Imax⁡I_{\max} and examine the prefix of each node. For overlap queries, we access ancestors of nodes from the inverted list of every label in fqf_q and also examine the prefix of each node. The number of ancestors of a node uu is ∣prefix⁡(u)∣|\operatorname{prefix}(u)|, and each ancestor can be accessed in O(1)O(1) time. Now consider a complex query. For any node u∈Ilu\in I_l where l∈LΦl\in\mathcal{L}_{\Phi}, if uu is inspected during a merge step in ComplexSearch, the associated cost is prefix⁡(u)\operatorname{prefix}(u). In the worst-case scenario, every merge operation in ComplexSearch includes uu. Since a complex predicate comprising ∣Φ∣|\Phi| containment or overlap queries entails ∣Φ∣|\Phi| merge operations, the overall complexity, when combined with the costs of ContainmentSearch and OverlapSearch, is given by

O(∑l∈LΦ∑u∈Il∣prefix⁡(u)∣⋅∣Φ∣).O\left(\sum_{l\in\mathcal{L}_{\Phi}}\sum_{u\in I_l}|\operatorname{prefix}(u)|\cdot|\Phi|\right).

Therefore, the theorem holds.

Proof of Theorem 3.15. Operations on the Trie and updates to the inverted lists take O(∣fo∣)O(|f_o|) time. Traversing the path from the root to the leaf also costs O(∣fo∣)O(|f_o|). For HNSW insertion and supplementEdge, an object belongs to at most O(min⁡{∣fo∣,log⁡n})O(\min\{|f_o|,\log n\}) graphs, so the total insertion cost is O(min⁡{∣fo∣,log⁡n}⋅(cupd+cq))O(\min\{|f_o|,\log n\}\cdot(c_{\mathrm{upd}}+c_q)). Adjusting the index assigned to a node may involve copying or deleting an index; one such operation on node uu costs O(∣Ou∣M)O(|O_u|M) and is triggered only when a change in ∣Ou∣|O_u| alters log⁡_size(u)\log\_size(u). After one such change, the next copy/delete on this index occurs after Ω(∣Ou∣)\Omega(|O_u|) insertions into OuO_u. Hence the amortized cost per insertion contributed by copying/deleting is O(M)O(M). Since an insertion affects at most ∣fo∣|f_o| subtrees, the total amortized overhead from copying/deleting is O(∣fo∣M)O(|f_o|M).

Rebuilding the index for node uu costs O(∣Ou∣cupd)O(|O_u|c_{\mathrm{upd}}). After a rebuild, u.Gu.G contains at most 2log⁡_size(u)+1−12^{\log\_size(u)+1}-1 nodes, and the next rebuild is triggered after Ω(∣Ou∣)\Omega(|O_u|) further insertions. Therefore, the amortized cost per insertion from rebuilding is O(cupd)O(c_{\mathrm{upd}}). Because an insertion touches at most min⁡{∣fo∣,log⁡n}\min\{|f_o|,\log n\} graphs, the total amortized rebuilding overhead is O(min⁡{∣fo∣,log⁡n}⋅cupd)O(\min\{|f_o|,\log n\}\cdot c_{\mathrm{upd}}). Summing all parts yields an amortized time complexity per update of O(∣fo∣M+min⁡{∣fo∣,log⁡n}(cupd+cq)M)O(|f_o|M+\min\{|f_o|,\log n\}(c_{\mathrm{upd}}+c_q)M). Moreover, the graph u.index.Gu.\mathrm{index}.G is allowed to contain at most 2log⁡_size(u)+2−12^{\log\_size(u)+2}-1 vertices, so

∣Ou.index.G∣∣Ou∣≤2log⁡_size(u)+2−12log⁡_size(u)<4,\frac{|O_u.\mathrm{index}.G|}{|O_u|}\leq\frac{2^{\log\_size(u)+2}-1}{2^{\log\_size(u)}}<4,

assuring that the index remains a 4-approximate index for OuO_u.

Received 17 April 2026; revised 19 August 2026; accepted 12 September 2026.

References

  1. [1]2026. Code and technical report. https://github.com/CUHK-DBGroup/DYLAN.
  2. [2]2026. Hnswlib. https://github.com/nmslib/hnswlib.
  3. [3]2026. Yelp Dataset. https://business.yelp.com/data-resources/open-dataset.
  4. [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. [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. [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. [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. [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. [9]Artem Babenko and Victor S. Lempitsky. 2015. Tree quantization for large-scale similarity search and classification. In CVPR. 4240–4248.
  10. [10]Davis W. Balock and John V. Guttg. 2017. Bolt: Accelerated Data Mining with Fast Vector Compression. In SIGKDD. 727–735.
  11. [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. [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. [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. [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. [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. [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. [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. [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. [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. [20]Piotr Indyk and Rajeev Motwani. 1998. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In STOC. 604–613.
  21. [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. [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. [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. [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. [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. [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. [27]Yusuke Matsui, Ryota Hinami, and Shin’ichi Satoh. 2018. Reconfigurable Inverted Index. In MM. 1715–1723.arxiv.org/abs/1808.03969
  28. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [45]Justin Zobel and Alistair Moffat. 1998. Inverted files versus signature files for text indexing. TODS 23, 4 (1998), 453–490.DOI
  46. [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.

Paper details

vlnc:W_g3ex7rfx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents