arXiv CSopen access

Efficient Graph Indexing for Interval-Aware Vector Search

Efficient Graph Indexing for Interval-Aware Vector Search Siyuan Liang

Beijing Institute of Technology Beijing, China [email protected]

arXiv:2606.11789v1 [cs.DB] 10 Jun 2026

Guoren Wang

Beijing Institute of Technology Beijing, China [email protected]

Ziqi Yin

Nanyang Technological University Singapore, Singapore [email protected]

Kaiwen Xue

Huawei Technologies Co., Ltd. Beijing, China [email protected]

Abstract Interval-aware Approximate Nearest Neighbor (ANN) search arises in applications where each object is associated with a numeric value or interval, and queries must satisfy both vector-similarity and interval constraints. Existing methods are typically tailored to a single query semantics, such as interval-filtered ANN search, and therefore require multiple specialized indexes to support diverse workloads, leading to substantial indexing and memory overhead. To address this limitation, we propose the Unified Interval-aware Relative Neighborhood Graph (URNG), a unified graph framework for interval-aware ANN search. URNG preserves the monotonic searchability of relative-neighborhood-graph based ANN indexes while additionally ensuring structural heredity over query-induced subgraphs, enabling a single index to support multiple intervalaware query semantics. Building on this framework, we develop UG, a practical graph index that efficiently approximates URNG through unified interval-aware pruning and iterative repair, together with a query algorithm for interval-aware ANN search. Extensive experiments on 5 datasets show that UG consistently achieves a strong accuracy-efficiency trade-off across diverse interval-aware workloads while maintaining competitive index construction cost and memory usage.

1

Introduction

Driven by advances in deep learning and large language models [7, 27, 44], vector search has become a core component in many real-world applications, including recommendation systems [9, 45], information retrieval [33], data mining [6, 13], and retrievalaugmented generation (RAG) [63]. However, due to the curse of dimensionality [4, 23, 53], exact nearest neighbor (NN) search in high-dimensional spaces is often too expensive to satisfy practical latency requirements. Approximate nearest neighbor (ANN) search addresses this challenge by substantially improving efficiency with only limited loss in accuracy. Over the past few decades, a wide range of ANN indexes have been proposed, including tree-based, hashing-based, quantizationbased, and graph-based methods [1, 5, 15–18, 48, 50, 58, 60]. Among them, graph-based methods consistently achieve a strong trade-off between query accuracy and efficiency [3, 51]. Their effectiveness Preprint, 2026.

Qi Zhang

University of Science and Technology Beijing Beijing, China [email protected]

Daiyin Wang

Huawei Technologies Co., Ltd. Beijing, China [email protected]

Ronghua Li

Beijing Institute of Technology Beijing, China [email protected]

Xubin Li

Huawei Technologies Co., Ltd. Beijing, China [email protected]

fundamentally relies on graph navigability: well-connected routing structures enable the search to approach high-quality neighbors while examining only a small fraction of the dataset. In particular, graph indexes that approximate the Relative Neighborhood Graph (RNG) are especially appealing, as they often examine fewer objects while maintaining high recall [46]. However, many real-world similarity search tasks are not purely vector-based. In addition to vector similarity, retrieved objects are often required to satisfy interval constraints associated with numeric attributes such as time, price, or validity ranges. A representative example arises in video surveillance and object tracking, where each detected object is associated not only with an embedding vector, but also with a temporal interval indicating when it appears in the camera’s field of view. Depending on the application, the system may need to support different interval-aware ANN query, as illustrated below. (1) Given a query vector 𝑣 and a time window 𝑞.𝐼 , one may want to retrieve visually similar objects whose visible durations are fully contained by the query range, which is referred to as Interval-Filtering ANN (IFANN) query [57]. (2) Conversely, given a query vector 𝑣 and a time interval 𝑞.𝐼 , one may want to retrieve visually similar objects whose visible durations cover the entire query interval, which is referred to as Interval-Stabbing ANN (ISANN) queries. When the query interval degenerates to a single timestamp 𝑡, ISANN reduces to Range-Stabbing ANN (RSANN) queries, also known as the timestamp ANN query [52], which retrieve nearest neighbors that remain active at the specific time 𝑡. A natural question is whether a single graph index can support these diverse interval-aware ANN queries efficiently. Unfortunately, this is non-trivial. The key challenge is structural: under interval constraints, search is effectively restricted to the query-valid objects, inducing a query-dependent subgraph of the original graph. Even if the original graph is highly navigable, the induced subgraph may lose critical routing nodes and edges, thereby severely degrading search quality. Moreover, different query semantics, such as interval containment and timestamp stabbing, can induce different subgraphs under the same range condition. As a result, a graph index that performs well for standard ANN search does not necessarily remain effective for interval-aware ANN retrieval. Partly due to this challenge, existing interval-aware ANN methods are typically specialized to a single query semantics rather

Preprint, 2026,

than designed as a unified index. For example, Hi-PNG [57] targets IFANN queries by building multiple graph indexes over different sub-ranges and selecting qualified sub-indexes for routing at query time. While effective for its target setting, such methods do not directly support a unified family of interval-aware queries. Consequently, supporting multiple query semantics often requires maintaining multiple specialized indexes, which leads to substantial indexing and memory overhead. In this paper, we propose the Unified interval-aware Relative Neighborhood Graph (URNG), a unified graph framework for intervalaware ANN search under numeric inclusion semantics. Unlike existing filtered graph designs, URNG explicitly accounts for both encompassing and subsumed relationships during graph construction. By carefully designing the pruning conditions, URNG preserves the search-friendly structure of RNG-style graphs under interval-aware filtering, while incurring only a modest constant-factor overhead in storage under a uniform interval model. These properties enable URNG to support a broad family of interval inclusion queries within a single graph index. Constructing an exact URNG on large-scale datasets, however, remains computationally prohibitive. To bridge theory and practice, we further develop the Unified Graph index (UG), a practical graph index that efficiently approximates URNG. The construction of UG consists of three phases: (1) generating an initial candidate set for each node by jointly considering spatial and interval proximity; (2) constructing a local UG for each node via iterative pruning; and (3) merging these local structures to approximate the global graph. Based on UG, we further design an efficient query processing algorithm for interval-aware ANN search. In summary, our main contributions are as follows: • Unified graph framework. We propose the URNG, a unified theoretical framework for interval-aware ANN search under various interval semantics queries. URNG preserves the monotonic searchability of RNG-style graphs while ensuring structural heredity over query-induced subgraphs, i.e., the subgraph induced by a valid query range remains a valid URNG. We further show that, under a uniform interval model, URNG incurs only a constant-factor overhead over the corresponding RNG in index size and search complexity. • Practical unified index. Building on URNG, we develop UG, a practical and efficient graph index that approximates the proposed framework. We design a fast interval-aware pruning technique to accelerate UG construction, and employ an iterative refinement procedure to empirically preserve monotonic searchability. In practice, the number of required iterations is small. The time complexity of each iteration is bounded by O (|𝐶 | · 𝑀𝑢𝑔 ), where |𝐶 | is a small constant in practice and 𝑀𝑢𝑔 denotes the number of edges of UG, which ensures good scalability on largescale datasets. We further show that UG satisfies key properties for robust performance under diverse query ranges. Based on UG, we also design an efficient query processing algorithm for graph navigation under interval-aware predicates. • Extensive Experiments. We conduct extensive experiments on five datasets to evaluate the effectiveness, robustness, and scalability of UG. The results show that, for IFANN queries, UG consistently achieves the best QPS–Recall trade-off across all

Liang et al.

datasets and substantially outperforms existing hierarchical baselines in the high-recall regime. UG also remains competitive in index construction time and memory consumption, indicating that its query gains do not come at the cost of excessive indexing overhead. In addition, UG is robust under diverse filtering workloads and continues to perform strongly even for highly selective queries. Beyond IFANN, UG also achieves strong performance on ISANN and remains competitive on RFANN and RSANN despite not being specialized for these query types. Finally, scalability experiments on datasets with up to 40M vectors show that UG scales smoothly with increasing data size.

2

Background and Motivation

In this section, we first introduce the interval-aware ANN queries studied in this paper, then review the main design strategies for such queries, and finally explain why existing methods remain insufficient for supporting diverse interval-aware workloads within a unified index.

2.1

Data Model and Query Types

Dataset. We consider a dataset 𝐷 of 𝑛 objects. Each object 𝑜 = (𝑣, 𝑎𝑠 , 𝑎𝑡 ) consists of a 𝑑-dimensional vector 𝑜.𝑣 and two numerical attributes 𝑜.𝑎𝑠 , 𝑜.𝑎𝑡 ∈ R with 𝑜.𝑎𝑠 ≤ 𝑜.𝑎𝑡 . The pair (𝑜.𝑎𝑠 , 𝑜.𝑎𝑡 ) specifies the interval associated with 𝑜. Unless otherwise stated, vector distance is measured by the Euclidean distance. Based on this model, we study interval-aware approximate nearest neighbor (ANN) search, where nearest neighbor retrieval is performed under query-dependent interval constraints. All queries are parameterized by a tuple 𝑞 = ⟨𝑣, 𝐼, 𝑘⟩, where 𝑞.𝑣 is a query vector, 𝑞.𝐼 = [𝑎𝑙 , 𝑎𝑟 ] is a query interval, and 𝑞.𝑘 is the number of desired results. The query semantics differ in how object intervals are matched against 𝑞.𝐼 . Interval-Filtered ANN (IFANN) Query [57]. An IFANN query returns the 𝑞.𝑘 objects in 𝐷 with the smallest Euclidean distances to 𝑞.𝑣 among those satisfying [𝑜.𝑎𝑠 , 𝑜.𝑎𝑡 ] ⊆ 𝑞.𝐼 . Interval-Stabbing ANN (ISANN) Query. An ISANN query returns the 𝑞.𝑘 objects in 𝐷 with the smallest Euclidean distances to 𝑞.𝑣 among those satisfying [𝑜.𝑎𝑠 , 𝑜.𝑎𝑡 ] ⊇ 𝑞.𝐼 . Two widely studied query types arise as special cases. Range-Filtered ANN (RFANN) Query [56, 64]. RFANN is a special case of IFANN in which each object is associated with a single scalar value 𝑜.𝑎, i.e., 𝑜.𝑎𝑠 = 𝑜.𝑎𝑡 = 𝑜.𝑎. The query returns the 𝑞.𝑘 nearest objects satisfying 𝑜.𝑎 ∈ 𝑞.𝐼 . Range-Stabbing ANN (RSANN) Query [52]. RSANN is a special case of ISANN in which the query interval degenerates to a single scalar value 𝑡, i.e., 𝑞.𝐼 = [𝑡, 𝑡]. The query returns the 𝑞.𝑘 nearest objects satisfying 𝑡 ∈ [𝑜.𝑎𝑠 , 𝑜.𝑎𝑡 ]. This query is referred to as Timestamp ANN (TANN) in prior work [52]. To unify the terminology across interval-aware ANN queries, we refer to it as RSANN in this paper, highlighting that it retrieves objects whose intervals are stabbed by the query timestamp. Although these queries differ in interval semantics, they can be cast into a common interval-aware ANN formulation.

Efficient Graph Indexing for Interval-Aware Vector Search

IFANN query RNG subgraph Q=[(25,75),G]

Preprint, 2026,

ISANN query RNG subgraph Q=[(25,75),G]

Figure 1: Interval constraints induce query-dependent searchable subgraphs. Starting from the same RNG, IFANN and ISANN retain different valid objects and edges, potentially invalidating critical routing structures.

2.2

Search Strategies and Graph Backbone

Existing solutions to interval-aware ANN search can be understood from two complementary perspectives: how interval constraints are enforced, and what ANN backbone is used for similarity search. These two perspectives are orthogonal: interval constraints may be handled in different ways, while the underlying ANN search can still be built on a graph-based backbone. From the perspective of constraint handling, existing methods typically fall into three categories. Pre-filtering first identifies all objects satisfying the interval predicate and then performs ANN search over the valid subset [49, 54]. Post-filtering first retrieves candidates according to vector similarity and then discards those violating the predicate [28]. Specialized indexing designs dedicated structures for particular query semantics to support more efficient constrained retrieval [56, 57]. From the perspective of ANN search, graph-based indexes have become one of the most effective backbones for modern vector retrieval. They organize objects into proximity graphs and answer queries through greedy graph traversal, achieving a strong balance between search accuracy and efficiency in high-dimensional spaces. This makes graph-based ANN a natural foundation for intervalaware retrieval.

2.3

Challenges under Interval Constraints

Despite this common design space, existing methods remain insufficient for supporting diverse interval-aware workloads within a unified graph index. In practice, many solutions are still tailored to individual query semantics rather than designed as a shared framework across IFANN, ISANN, RFANN, and RSANN. A natural baseline is to combine interval filtering with ANN search in a loosely coupled manner. Pre-filtering first materializes the valid subset and then performs ANN search on it, which is effective for low-selectivity queries [19, 21], but can be prohibitively expensive when the valid subset remains large. Post-filtering first retrieves candidates by vector similarity and then removes invalid ones — this approach suits high-selectivity queries [49, 54] — but often wastes substantial search effort and requires considerable oversampling before enough valid results are found. As a result,

loosely coupled strategies are generally inadequate for efficient interval-aware ANN search. More fundamentally, interval-aware constraints alter the effective search space in a query-dependent manner, posing a structural challenge to graph-based ANN search. The effectiveness of graph ANN indexes relies on good navigability in the searchable graph. Under interval-aware queries, however, search is effectively confined to the valid objects determined by the query interval, yielding a query-induced subgraph of the original graph. This subgraph may differ significantly from the full graph in both connectivity and routing structure: nodes or edges that are critical to greedy navigation in the original graph may no longer remain available after applying the interval constraint. Consequently, a graph that is highly navigable on the full dataset may become poorly connected, or even disconnected, under interval-aware queries. Figure 1 illustrates this effect using an RNG-style graph1 : under the same query interval, IFANN and ISANN induce different valid subgraphs, and routing structures available in the original graph may disappear after filtering. Some specialized graph indexes partially alleviate this issue for their target query semantics. For example, strong IFANN solutions often rely on partitioned or multi-structure designs, such as hierarchical interval partitioning [57], to achieve high query efficiency. However, these approaches incur additional indexing and memory overhead, complicate updates and maintenance, and do not naturally generalize to other interval-aware query types. More broadly, existing specialized methods remain tightly coupled to specific predicates and therefore do not generalize naturally across interval-aware query types. These observations suggest that the key challenge is not merely to optimize search for one particular interval predicate, but to design a unified graph framework whose search effectiveness is preserved under diverse query-dependent filtering conditions. This challenge motivates the framework developed in the next section.

3

Unified Interval-aware RNG

In this section, we establish the theoretical foundation of the Unified Interval-aware Relative Neighborhood Graph (URNG). We proceed to formally define the URNG structure and provide a rigorous analysis of its graph-theoretic properties, including monotonic searchability, structural heredity, and asymptotic complexity bounds. Definition 3.1 (URNG). Let 𝐷 be a dataset in a metric space with distance function 𝛿, where each object is associated with an interval attribute 𝐼 . The Unified Interval-aware Relative Neighborhood Graph (URNG) on 𝐷 is defined as a graph 𝐺 = (𝑉 , 𝐸, st), where each node in 𝑉 corresponds to an object in 𝐷, and each edge (𝑢, 𝑣) ∈ 𝐸
is associated with a semantic bitmask st(𝑢, 𝑣) = 𝑏 IF (𝑢, 𝑣), 𝑏 IS (𝑢, 𝑣) ∈ {0, 1}2 . For any two distinct nodes 𝑢, 𝑣 ∈ 𝑉 , the IF bit 𝑏 IF (𝑢, 𝑣) is set to 1 if and only if there does not exist a witness node 𝑤 ∈ 𝑉 \ {𝑢, 𝑣 } such that all of the following conditions hold2 : 𝛿 (𝑢, 𝑤) < 𝛿 (𝑢, 𝑣), 𝛿 (𝑣, 𝑤) < 𝛿 (𝑢, 𝑣), 𝐼 𝑤 ⊆ 𝐼𝑢 ∪ 𝐼 𝑣 , and 𝑏 IF (𝑢, 𝑤) = 1 1 [16] refers to the graph constructed based on the RNG’s pruning strategy as the

Monotonic Relative Neighborhood Graph (MRNG). For simplicity, we use the term RNG throughout this paper. 2 Here, the union symbol for two intervals, 𝐼 𝐴 ∪ 𝐼 𝐵 , denotes the interval min(𝐼𝐴 .𝑙, 𝐼𝐵 .𝑙 ), max(𝐼𝐴 .𝑟, 𝐼𝐵 .𝑟 ) . For convenience, throughout the subsequent description of the pruning conditions, ∪ is used with this meaning.

Preprint, 2026,

[30, 100]

[25, 75] C

E

F

[20, 80] A

B [30, 70]

G

[25, 75]

[0, 70]

H D

[30, 85]

[40, 60]

(a) Edge kept by URNG-IF [30, 100]

[25, 75] C

E

F

[20, 80] A

B [30, 70]

G

[25, 75]

[0, 70]

H D

[30, 85]

[40, 60]

(c) Edge kept by URNG

[30, 100]

[25, 75] C

E

F

[20, 80] A

[30, 100]

D

[25, 75] C

E

[25, 75]

[30, 85]

[40, 60]

(d) Edge pruned by URNG

Figure 2: Illustration of the URNG pruning strategy Similarly, the IS bit 𝑏 IS (𝑢, 𝑣) is set to 1 if and only if there does not exist a witness node 𝑤 ∈ 𝑉 \ {𝑢, 𝑣 } such that all of the following conditions hold: 𝛿 (𝑢, 𝑤) < 𝛿 (𝑢, 𝑣), 𝛿 (𝑣, 𝑤) < 𝛿 (𝑢, 𝑣), 𝐼𝑢 ∩ 𝐼 𝑣 ⊆ 𝐼 𝑤 , and 𝑏 IS (𝑢, 𝑤) = 1 Accordingly, an edge (𝑢, 𝑣) is active for IFANN queries when 𝑏 IF (𝑢, 𝑣) = 1, active for ISANN queries when 𝑏 IS (𝑢, 𝑣) = 1, and active for both query types when st(𝑢, 𝑣) = (1, 1). Example 1. Figure 2 presents four representative cases that illustrate how edges are retained or pruned in URNG under different interval semantics. (1) The edge (𝐵, 𝐶) is the longest edge in triangle (𝐵, 𝐶, 𝐹 ), and would therefore be pruned in a classical RNG. Under intervalaware semantics, however, only the IS constraint [30, 70] ⊆ [0, 70] is satisfied. As a result, the IS functionality of (𝐵, 𝐶) is pruned, while its IF functionality is preserved. (2) The edge (𝐵, 𝐷) is the longest edge in triangle (𝐵, 𝐷, 𝐻 ), and would also be removed in a classical RNG. Under interval-aware semantics, only the IF constraint [40, 60] ⊆ [30, 85] is satisfied. Hence, the IF functionality of (𝐵, 𝐷) is pruned, while its IS functionality remains active. (3) For the edge (𝐷, 𝐺), there exists no triangle in which it becomes the longest edge. Therefore, this edge cannot be pruned by any valid witness node and remains active under both semantics. (4) The edge (𝐴, 𝐵) is the longest edge in triangle (𝐴, 𝐵, 𝐶), and since [25, 75] ⊆ [20, 80], its IF functionality is pruned by edge (𝐴, 𝐶). The same edge (𝐴, 𝐵) is also the longest edge in triangle (𝐴, 𝐵, 𝐷), and since [30, 70] ⊆ [30, 85], its IS functionality is pruned by edge (𝐴, 𝐷). Since both semantic bits are removed, the edge is completely discarded from the graph. The above definition unifies the two interval semantics into a single theoretical graph. Compared with defining two independent proximity graphs, URNG offers two advantages: (1) reduced memory cost, as nodes and many edges are shared across the two graphs; and (2) efficient construction and query processing due to the bitmask-based representation, as detailed in Section 4. Difference from the classical RNG. There is no direct inclusion relationship between RNG and URNG. The reason is fundamental: in URNG, pruning depends not only on the geometric condition that an edge is the longest edge of a triangle, but also on whether the witness node remains valid under the corresponding interval

[30, 100]

[30, 85]

[40, 60]

C

[0, 70] F

[20, 80] A

B [30, 70]

(b) RNG Path (A->B) [20, 80] A

H D

[25, 75]

E

B [30, 70]

G

[25, 75]

(c) URNG-IS Path (A->D->B)

H D

[30, 85]

[40, 60]

(d) RNG Path (A->B)

Figure 3: Differences between RNG and URNG.

H D

B [30, 70]

G

[0, 70] B [30, 70]

G

[25, 75]

B [30, 70]

[20, 80] A

F

[20, 80] A

[0, 70] F

(a) URNG-IF Path (A->C->B)

[40, 60]

(b) Edge kept by URNG-IS [30, 100]

C

[20, 80] A

H

[30, 85]

[25, 75]

E

B [30, 70]

G

[25, 75]

Liang et al.

[0, 70]

semantics. Consequently, some edges that would be removed in a classical RNG may be retained in URNG due to the lack of a semantically valid witness. Conversely, such retained edges may later act as new semantic witnesses and prune other edges that would otherwise survive in the classical RNG, as illustrated in Figure 1 and 2. However, it is precisely URNG’s awareness of interval that allows it to maintain connectivity and high performance across different queries. As illustrated in Figure 3, navigation from 𝐴 to 𝐵 in URNG does not necessarily rely on the direct edge (𝐴, 𝐵). In the IF-induced subgraph, the path (𝐴, 𝐶), (𝐶, 𝐵) shown in Figure (a) can replace the direct edge. In the IS-induced subgraph, the path (𝐴, 𝐷), (𝐷, 𝐵) shown in Figure (b) plays an analogous role. This witness-mediated routing mechanism is precisely what prevents the filtered subgraph from becoming disconnected under interval constraints, and it forms the structural basis for the advantage of URNG in intervalaware search.

3.1

Theoretical Properties

In this subsection, we introduce two key properties of URNG that enable it to support various interval-aware ANN queries within a single graph structure. Definition 3.2 (Monotonic path). Given a graph 𝐺 = (𝑉 , 𝐸) and a distance metric 𝛿, a path = 𝑣 0 → 𝑣 1 → 𝑣 2 → · · · → 𝑣𝑘 = 𝑡 is called a monotonic path with respect to the target node 𝑡 if 𝛿 (𝑣𝑖+1, 𝑡) < 𝛿 (𝑣𝑖 , 𝑡), ∀ 0 ≤ 𝑖 < 𝑘. That is, the distance to the target strictly decreases at every step along the path. We now prove the existence of a monotonic path in each semantic projection of URNG. Theorem 3.3 (Monotonic Searchability). For any dataset 𝐷 and a URNG graph 𝐺 constructed over 𝐷, fix one semantic projection 𝐺 𝜎 , where 𝜎 ∈ {IF, IS}. For any two nodes 𝑠, 𝑡 ∈ 𝑉 , a monotonic path from 𝑠 to 𝑡 exists in 𝐺 𝜎 . Proof. Without loss of generality, consider the current node 𝑢 ≠ 𝑡. If (𝑢, 𝑡) ∈ 𝐸 𝜎 , the condition is satisfied directly. Otherwise, if (𝑢, 𝑡) ∉ 𝐸 𝜎 , then by Definition 3.1 under the fixed semantics 𝜎, there exists a witness node 𝑤 such that (𝑢, 𝑤) ∈ 𝐸 𝜎 and 𝛿 (𝑤, 𝑡) < 𝛿 (𝑢, 𝑡). The search can thus safely proceed from 𝑢 to 𝑤. Repeating the same argument, the distance to 𝑡 strictly decreases at every step. Since the dataset is finite, this process must terminate, and the only possible terminal node is 𝑡. Therefore, a monotonic path from 𝑠 to 𝑡 exists in 𝐺 𝜎 . □

Efficient Graph Indexing for Interval-Aware Vector Search

Preprint, 2026,

Example 2. As shown in Figure 3, under IF filtering, the path 𝐴 → 𝐶 → 𝐵 exists in Figure (a), while under IS filtering, the path 𝐴 → 𝐷 → 𝐵 exists in Figure (c). Figure (b) and (d) further illustrate the direct edge 𝐴 → 𝐵.These examples show that although URNG reorganizes the local graph structure according to interval semantics, it still preserves the core navigability property required for search. The monotonicity property provides the theoretical justification for applying graph traversal over any semantic projection of URNG. It is worth noting that classical RNG also belongs to the family of monotonic search networks and thus admits monotonic paths as well [16]. Corollary 3.4. Let 𝐺 𝜎 = (𝑉 , 𝐸 𝜎 ) be a fixed semantic projection of the URNG constructed on dataset 𝐷 under distance metric 𝛿,where 𝜎 ∈ {IF, IS}. For any target node 𝑡 ∈ 𝑉 , beam search using 𝑡 .𝑣 as the query vector can always reach 𝑡 regardless of the choice of the entry node. Proof. Without loss of generality, let 𝑠 be the entry node. By Theorem 3.3, there exists a monotonic path 𝑠 = 𝑣 0 → 𝑣 1 → · · · → 𝑣𝑚 = 𝑡 in 𝐺 𝜎 such that 𝛿 (𝑣𝑖+1, 𝑡) < 𝛿 (𝑣𝑖 , 𝑡) for all 0 ≤ 𝑖 < 𝑚. Since the query vector is exactly 𝑡 .𝑣, we have 𝛿 (𝑣𝑖+1, 𝑞.𝑣) < 𝛿 (𝑣𝑖 , 𝑞.𝑣) at every step along the same path. Therefore, the search process always has access to at least one candidate that is closer to the query target than the current node. Since beam search always keeps the closest candidates and the dataset is finite, the search process eventually reaches 𝑡. □ In addition to monotonic searchability, URNG satisfies another crucial property, namely structural heredity. This property states that filtering a globally constructed URNG and directly rebuilding URNG on the filtered node set produce equivalent graph structures. This is precisely the property that classical RNG lacks in interval-aware settings. In the following theorem, we fix one query semantics at a time. Accordingly, 𝑉𝐼 denotes the query-valid node set under the chosen semantics, and 𝐺 [𝐼 ] denotes the induced subgraph relevant to that semantics. We then have the following theorem. Theorem 3.5 (Structural Heredity). Let 𝐺 = (𝑉 , 𝐸) be the URNG constructed on dataset 𝐷 under distance metric 𝛿. For any query 𝑞 = ⟨𝑣, 𝐼 = [𝑎𝑙 , 𝑎𝑟 ], 𝑘⟩, let 𝐺 [𝐼 ] = (𝑉𝐼 , 𝐸𝐼 ) denote the induced subgraph of 𝐺, and let 𝐺 ′ = (𝑉 ′, 𝐸 ′ ) denote the URNG directly constructed on the node set 𝑉𝐼 . Then 𝐺 [𝐼 ] ≡ 𝐺 ′, that is, the two graphs are structurally equivalent. Proof. Since 𝑉𝐼 = 𝑉 ′ , it suffices to prove 𝐸𝐼 = 𝐸 ′ . We use induction on edge length. For the base case, let (𝑢, 𝑣) be the shortest candidate edge with both endpoints in 𝑉𝐼 . Suppose (𝑢, 𝑣) were pruned by some witness node 𝑤 ∈ 𝑉 . Then (𝑢, 𝑤) must be shorter than (𝑢, 𝑣). Moreover, the semantic condition forces 𝑤 ∈ 𝑉𝐼 : for IFANN, [𝑤 .𝑙, 𝑤 .𝑟 ] ⊆ 𝐼 ; for ISANN, 𝐼 ⊆ [𝑤 .𝑙, 𝑤 .𝑟 ]. Thus (𝑢, 𝑤) is a shorter edge inside 𝑉𝐼 , contradicting the choice of (𝑢, 𝑣). Hence (𝑢, 𝑣) cannot be pruned, and its semantic state is identical in 𝐸𝐼 and 𝐸 ′ . Now assume that all edges shorter than (𝑢, 𝑣) have the same semantic states in 𝐸𝐼 and 𝐸 ′ . If a semantic bit of (𝑢, 𝑣) remains active in 𝐸𝐼 , then no valid witness with the same semantic status

IFANN query URNG subgraph Q=[(25,75),G]

ISANN query URNG subgraph Q=[(25,75),G]

Figure 4: Illustration of the hereditary property of URNG. exists in 𝑉𝐼 ; since 𝐸 ′ is constructed on the same node set 𝑉𝐼 , no such witness can appear in 𝐸 ′ , so the bit also remains active there. Conversely, if a semantic bit of (𝑢, 𝑣) is inactive in 𝐸𝐼 , then there exists a witness edge (𝑢, 𝑤) satisfying the corresponding pruning condition. By the same argument as above, the semantic condition implies 𝑤 ∈ 𝑉𝐼 . Since dis(𝑢, 𝑤) < dis(𝑢, 𝑣), the induction hypothesis guarantees that (𝑢, 𝑤) has the same semantic state in 𝐸 ′ , and therefore (𝑢, 𝑣) is also pruned in 𝐸 ′ . Thus (𝑢, 𝑣) has the same semantic state in both graphs. By induction, all edges do, and hence 𝐸𝐼 = 𝐸 ′ . □ The heredity property guarantees that, for any interval-aware ANN query, it is unnecessary to explicitly reconstruct the graph structure from scratch on the filtered node set. Instead, one can directly search over the corresponding induced subgraph, and the result is equivalent to that of rebuilding URNG after filtering. This is exactly the structural advantage that URNG provides over the classical RNG in interval-aware search. Figure 4 illustrates the induced URNG subgraphs for the example shown in Figure 1. Under the interval filter [25, 75], both the IF-induced and IS-induced subgraphs remain well connected and navigable, thereby supporting the intended search process and returning the desired results.

3.2

Complexity Analysis

We next summarize the complexity of URNG under a uniform interval model, where interval endpoints are generated independently and uniformly. Detailed proofs are deferred to the appendix [32]. Theorem 3.6. Under the assumption that interval attributes are independently and uniformly distributed, the expected complexity of interval-aware beam search on URNG is 𝑂 (𝑛 1/𝑑 log 𝑛). Theorem 3.7. The index size of URNG is upper bounded by 𝑂 (𝐶 urng𝑆𝑟 ) = 𝑂 (𝑆𝑟 ), where 𝑆𝑟 denotes the index size of the corresponding RNG and 𝐶 urng is a constant independent of 𝑛. These results show that, under the uniform interval model, URNG preserves the navigability of monotonic search graphs while incurring only a constant-factor overhead over the corresponding RNG. Theorem 3.8. The time complexity of exact URNG construction is 𝑂 (𝑛 3 ).

Preprint, 2026,

Algorithm 1: UG Initial Candidate Generation Input: Dataset 𝑉 , spatial budget 𝑒 𝑓𝑠𝑝𝑎𝑡𝑖𝑎𝑙 , attribute budget 𝑒 𝑓𝑎𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒 Output: Initial candidate sets C for all nodes 1 Function GenerateCandidates(𝑉 , 𝑒 𝑓𝑠𝑝𝑎𝑡𝑖𝑎𝑙 , 𝑒 𝑓𝑎𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒 ) 2 C𝑠𝑝𝑎 ← NNDescent(𝑉 , 𝑒 𝑓𝑠𝑝𝑎𝑡𝑖𝑎𝑙 ); 3 foreach 𝑢 ∈ 𝑉 do 4 C𝑎𝑡𝑡𝑟 (𝑢) ← ∅; 5 6 7 8 9

10

𝐾𝑒𝑦𝑠 ← {𝑙, 𝑟, 𝑚𝑖𝑑, 𝑙𝑒𝑛}; foreach 𝑘 ∈ 𝐾𝑒𝑦𝑠 do 𝑉𝑘 ← sort 𝑉 in ascending order of attribute 𝑘; foreach 𝑢 ∈ 𝑉𝑘 do 𝑒𝑓 N𝑘 (𝑢) ← fetch 𝑎𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒 adjacent nodes from 8 both sides of 𝑢 in 𝑉𝑘 ; C𝑎𝑡𝑡𝑟 (𝑢) ← C𝑎𝑡𝑡𝑟 (𝑢) ∪ N𝑘 (𝑢);

13

foreach 𝑢 ∈ 𝑉 do C(𝑢) ← C𝑠𝑝𝑎 (𝑢) ∪ C𝑎𝑡𝑡𝑟 (𝑢); C(𝑢) ← Unique(C(𝑢)) \ {𝑢};

14

return C;

11 12

This 𝑂 (𝑛 3 ) exact-construction cost further motivates the practical UG index introduced in Section 4. Difference from the (RRNG) [64]. The proposed URNG is closely related to the Range-aware Relative Neighborhood Graph (RRNG) [64], which was originally developed for RFANN search, since both aim to preserve monotonic searchability and structural heredity under attribute-induced filtering. However, URNG substantially generalizes RRNG in both the data model and query semantics: while RRNG assumes scalar attributes and RFANN queries, URNG handles interval attributes and supports multiple interval-inclusion semantics, including ISANN, IFANN, RSANN and RFANN search. Indeed, RRNG can be viewed as a special case of URNG when each object interval degenerates to a point, i.e., 𝐼𝑜 = [𝑜.𝑎, 𝑜.𝑎], and only the IF projection is considered.

4

The Unified Interval-aware Graph-based Index

In Section 3, we introduced the unified theory of the Unified Intervalaware Relative Neighborhood Graph (URNG). However, constructing an exact URNG requires explicitly evaluating witness relationships on the complete graph, where results in an 𝑂 (𝑛 3 ) construction cost and prevents URNG from being applied in practice. To address this issue, we propose the Unified Interval-aware Graph-based index (UG), a practical graph index that approximates URNG effectively while preserving its structural advantages. In particular, UG is built in two stages. We first generate a highquality candidate set for each node, and then apply an iterative unified pruning strategy to derive the final graph. In addition, we design an interval-aware beam search algorithm over UG to support efficient navigation for both IFANN queries and ISANN queries.

Liang et al.

4.1

Candidate Generation

The computational bottleneck of exact URNG construction lies in the size of the candidate set. In principle, exact pruning would require considering all nodes as potential neighbors. However, the analysis in Section 3 suggests that the edges that ultimately survive pruning are highly selective: an edge is retained not merely because of geometric proximity, but rather due to the absence of any semantically valid witness that can eliminate it under the query semantics. This observation motivates us to replace the complete candidate set with a high-quality approximate candidate pool. Algorithm 1 constructs the initial candidate pool for each node by combining spatial proximity and interval proximity. It first applies NNDescent to the whole dataset with budget 𝑒 𝑓𝑠𝑝𝑎𝑡𝑖𝑎𝑙 , obtaining a spatial candidate set C𝑠𝑝𝑎 that captures the local neighborhood structure in the vector space (line 2). To further introduce intervalrelevant candidates, the algorithm initializes an empty attributeaware candidate set for each node (lines 3–4), and then examines four interval-derived keys, including the left endpoint 𝑙, the right endpoint 𝑟 , the midpoint mid, and the interval length len (line 5). For each key, all nodes are sorted according to the corresponding interval attribute (line 7). The algorithm then scans the sorted order and collects nearby nodes around each node 𝑢 as attribute-aware candidates (lines 8–10). In particular, it fetches up to ⌊𝑒 𝑓𝑎𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒 /8⌋ adjacent nodes from each side of 𝑢 under the current ordering, so that the overall number of interval-based candidates is controlled by 𝑒 𝑓𝑎𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒 across the four keys and two directions (line 9). These candidates are useful because nodes close in such interval-derived orders are more likely to survive the same interval constraint or serve as semantic witnesses in later pruning. Finally, UG merges the spatial and attribute-aware candidates, removes duplicates and the node itself, and returns the initial candidate sets for all nodes (lines 11–14). Candidate generation in UG is motivated by the observation in Section 3 that URNG edges are determined by both spatial proximity and semantically valid witnesses. Accordingly, UG constructs the candidate pool from two complementary sources: spatial neighbors, which provide the basic navigational backbone, and interval-aware neighbors, which increase the chance of covering useful IF/IS witnesses. Since exact URNG construction would require considering all nodes, this stage only provides a bounded candidate space rather than enforcing URNG properties by itself. The URNG-like structure is further approximated in the subsequent stages: unified pruning applies the interval-aware witness conditions within the candidate pool, while iterative repair compensates for missing continuation paths caused by the bounded candidate set. Empirically, this design provides sufficient candidate coverage for high-recall search, as shown in Section 5.

4.2

Pruning Strategy

After obtaining the candidate graph, UG constructs the final index by pruning redundant edges while preserving, as much as possible, the structural behavior of URNG. The goal of this stage is to approximate the unified pruning semantics of URNG within a bounded candidate pool, while keeping the graph sparse enough for efficient search. To support both IFANN queries and ISANN queries within a single graph, UG associates each retained edge with a semantic

Efficient Graph Indexing for Interval-Aware Vector Search

Algorithm 2: UG Iterative Construction Input: Dataset 𝑉 , initial candidates C (0) , semantic degree

budget 𝑀, iterations 𝑇 Output: Neighbor sets N (𝑇 ) with semantic bitmasks (0) , 𝑀,𝑇 ) 1 Function BuildUG(𝑉 , C 2 foreach 𝑢 ∈ 𝑉 do 3 W (0) (𝑢) ← ∅; 4 5 6 7 8 9 10 11 12

for 𝑡 ← 1 to 𝑇 do foreach 𝑢 ∈ 𝑉 do b(𝑡 ) (𝑢) ← Uniqe(C (𝑡 −1) (𝑢) ∪ W (𝑡 −1) (𝑢)); C W (𝑡 ) (𝑢) ← ∅; foreach 𝑢 ∈ 𝑉 do b(𝑡 ) (𝑢), 𝑀); N (𝑡 ) (𝑢), ΔW ← UnifiedPrune(𝑢, C (𝑡 ) (𝑡 ) C (𝑢) ← { 𝑣 | (𝑣, ·) ∈ N (𝑢) }; foreach (𝑤, 𝑣) ∈ ΔW do W (𝑡 ) (𝑤) ← W (𝑡 ) (𝑤) ∪ {𝑣 };

Preprint, 2026,

Algorithm 3: UG Unified Prune Input: Node 𝑢, candidate set C(𝑢), semantic degree budget 𝑀 Output: Pruned neighbors N (𝑢) and repair set ΔW 1 Function UnifiedPrune(𝑢, C(𝑢), 𝑀) 2 N (𝑢) ← ∅, ΔW ← ∅; 3 𝑐𝑛𝑡𝐼 𝐹 ← 0, 𝑐𝑛𝑡𝐼𝑆 ← 0; 4 sort C(𝑢) by increasing 𝛿 (𝑢, ·); 5 foreach 𝑣 ∈ C(𝑢) do 6 𝑠 𝑣 [𝐼 𝐹 ] ← 1, 𝑠 𝑣 [𝐼𝑆] ← 1; 7 if 𝐼𝑢 ∩ 𝐼 𝑣 = ∅ then 8 𝑠 𝑣 [𝐼𝑆] ← 0; 9 10 11 12 13

13

return N (𝑇 ) ;

14 15

bitmask indicating whether the edge is active under IF semantics, IS semantics, or both. Therefore, UG does not explicitly maintain two separate graphs. Instead, it stores a unified edge set, and later query processing dynamically selects the subgraph according to the query type. Algorithm 2 presents the iterative construction procedure of UG. The algorithm starts from the initial candidate sets C (0) and maintains a repair candidate set W (𝑡 ) for each iteration. Initially, the repair set of every node is empty (lines 2–3). At the beginning of the 𝑡-th iteration, UG forms a refined candidate pool for each node by merging the candidates retained from the previous round and the repair candidates generated in the previous round (lines 5–7). This design avoids accumulating all historical candidates, while still allowing potentially useful pruned endpoints to be reconsidered. After the refined candidate pool is obtained, UG applies UnifiedPrune to each node, producing a semantic neighbor set N (𝑡 ) (𝑢) and a set of repair pairs ΔW (lines 8–9). The retained neighbors are extracted as the base candidate set for the next iteration (line 10). For each repair pair (𝑤, 𝑣), the pruned endpoint 𝑣 is inserted into the repair set of the witness node 𝑤, so that the possible continuation path through 𝑤 can be explored in the next round (lines 11–12). After 𝑇 iterations, the algorithm returns the final neighbor sets N (𝑇 ) , where each retained edge is associated with its semantic bitmask (line 13). For compactness, we denote the interval of a node 𝑥 by 𝐼𝑥 = [𝑙𝑥 , 𝑟 𝑥 ]. For 𝜎 ∈ {𝐼 𝐹, 𝐼𝑆 }, let 𝑠 [𝜎] denote whether semantic 𝜎 is active in bitmask 𝑠. We define the semantic witness conditions as Φ𝐼 𝐹 (𝑢, 𝑣, 𝑤) : 𝐼 𝑤 ⊆ 𝐼𝑢 ∪ 𝐼 𝑣 and Φ𝐼𝑆 (𝑢, 𝑣, 𝑤) : 𝐼𝑢 ∩ 𝐼 𝑣 ⊆ 𝐼 𝑤 , where the IS condition is considered only when 𝐼𝑢 ∩ 𝐼 𝑣 ≠ ∅. Algorithm 3 presents the local unified pruning rule used in UG. The algorithm first initializes the neighbor set, the repair set, and the semantic degree counters, and then sorts all candidates by their distance to 𝑢 (lines 1–4). This ordering allows previously retained neighbors to serve as possible witnesses for later candidates. For each candidate 𝑣, UG initializes both semantic bits as active, and

16 17

18 19 20 21 22 23 24 25

foreach 𝑤 ∈ N (𝑢) do if 𝑠 𝑣 = 0 then break; if 𝛿 (𝑣, 𝑤) ≥ 𝛿 (𝑢, 𝑣) then continue; foreach 𝜎 ∈ {𝐼 𝐹, 𝐼𝑆 } do if 𝑠 𝑣 [𝜎] = 1 and 𝑤 .𝑠𝑡𝑎𝑡𝑢𝑠 [𝜎] = 1 and Φ𝜎 (𝑢, 𝑣, 𝑤) then 𝑠 𝑣 [𝜎] ← 0; ΔW ← ΔW ∪ {(𝑤, 𝑣)}; foreach 𝜎 ∈ {𝐼 𝐹, 𝐼𝑆 } do if 𝑠 𝑣 [𝜎] = 1 then if 𝑐𝑛𝑡𝜎 < 𝑀 then 𝑐𝑛𝑡𝜎 ← 𝑐𝑛𝑡𝜎 + 1; else 𝑠 𝑣 [𝜎] ← 0; if 𝑠 𝑣 ≠ 0 then 𝑣.𝑠𝑡𝑎𝑡𝑢𝑠 ← 𝑠 𝑣 ; N (𝑢) ← N (𝑢) ∪ {𝑣 }; return N (𝑢), ΔW;

immediately removes the IS bit if 𝐼𝑢 and 𝐼 𝑣 do not overlap, since no ISANN query can make both endpoints valid in this case (lines 5–8). The pruning step then scans the already retained neighbors of 𝑢 as candidate witnesses (lines 9–17). If both semantic bits of 𝑣 have been removed, the scan stops early (lines 10–11). Otherwise, a retained neighbor 𝑤 is considered only when it satisfies the geometric witness condition 𝛿 (𝑣, 𝑤) < 𝛿 (𝑢, 𝑣) (lines 12–13); the other RNG-style condition 𝛿 (𝑢, 𝑤) < 𝛿 (𝑢, 𝑣) is guaranteed by the sorted processing order. For each semantic 𝜎 ∈ {𝐼 𝐹, 𝐼𝑆 }, the bit 𝑠 𝑣 [𝜎] is cleared when 𝑤 is also active under 𝜎 and satisfies the corresponding semantic condition Φ𝜎 (𝑢, 𝑣, 𝑤) (lines 14–16). Whenever a semantic bit is removed, the pair (𝑤, 𝑣) is recorded in ΔW as a repair candidate for the next iteration (line 17). After witness pruning, UG enforces the semantic degree budget separately for IF and IS, so that each semantic projection remains sparse (lines 18–21). Finally, if at least one semantic bit of 𝑣 remains active, 𝑣 is retained as a neighbor of 𝑢 together with its remaining bitmask (lines 22–24). The algorithm returns the pruned neighbor set and the repair set (line 25). The iterative repair mechanism is introduced to compensate for the bounded candidate pool. In the exact URNG, an edge can be

Preprint, 2026,

Liang et al.

Algorithm 4: UG Interval-Aware Beam Search Input : Graph 𝐺, query 𝑄 = (𝑞 𝑣 , 𝑞𝐼 , 𝑘, 𝑡𝑦𝑝𝑒), beam size 𝑒 𝑓𝑠𝑒𝑎𝑟𝑐ℎ Output : Top-𝑘 nearest neighbors 1 Function ContextAwareSearch(𝐺, 𝑄, 𝑒 𝑓𝑠𝑒𝑎𝑟𝑐ℎ ) 2 𝑠𝑡𝑎𝑟𝑡 ← GetEntryNode(𝑄.𝑞𝐼 , 𝑄.𝑡𝑦𝑝𝑒); 3 if 𝑠𝑡𝑎𝑟𝑡 = NULL then return ∅; 4 𝐶 ← {𝑠𝑡𝑎𝑟𝑡 }, 𝑅 ← {𝑠𝑡𝑎𝑟𝑡 }, 𝑉 𝑖𝑠𝑖𝑡𝑒𝑑 ← {𝑠𝑡𝑎𝑟𝑡 }; 5 while 𝐶 ≠ ∅ do 6 𝑢 ← ExtractMin(𝐶); 7 if |𝑅| ≥ 𝑒 𝑓𝑠𝑒𝑎𝑟𝑐ℎ and 𝛿 (𝑢, 𝑞 𝑣 ) > max𝑥 ∈𝑅 𝛿 (𝑥, 𝑞 𝑣 ) then 8 break; 9 10 11 12

13 14 15 16 17

18 19 20

21

foreach 𝑣 ∈ 𝑁 (𝑢) \ 𝑉 𝑖𝑠𝑖𝑡𝑒𝑑 do 𝑉 𝑖𝑠𝑖𝑡𝑒𝑑 ← 𝑉 𝑖𝑠𝑖𝑡𝑒𝑑 ∪ {𝑣 }; if 𝑄.𝑡𝑦𝑝𝑒 = IF then if (𝑣.𝑠𝑡𝑎𝑡𝑢𝑠 & FLAG𝐼 𝐹 ) ≠ 0 and [𝑙 𝑣 , 𝑟 𝑣 ] ⊆ 𝑄.𝑞𝐼 then 𝐶 ← 𝐶 ∪ {𝑣 }; 𝑅 ← 𝑅 ∪ {𝑣 }; if |𝑅| > 𝑒 𝑓𝑠𝑒𝑎𝑟𝑐ℎ then RemoveMax(𝑅); else if 𝑄.𝑡𝑦𝑝𝑒 = IS then if (𝑣.𝑠𝑡𝑎𝑡𝑢𝑠 & FLAG𝐼𝑆 ) ≠ 0 and 𝑄.𝑞𝐼 ⊆ [𝑙 𝑣 , 𝑟 𝑣 ] then 𝐶 ← 𝐶 ∪ {𝑣 }; 𝑅 ← 𝑅 ∪ {𝑣 }; if |𝑅| > 𝑒 𝑓𝑠𝑒𝑎𝑟𝑐ℎ then RemoveMax(𝑅); return Top-𝑘 nodes from 𝑅;

safely pruned because there exists a witness edge together with a monotone continuation path. In practice, however, such a continuation path may not yet be present in the current local candidate pool. UG therefore records the pruned endpoint as a repair candidate of the witness node and reintroduces it in the next round. This makes the iterative construction process a heuristic approximation of monotone-path repair under bounded candidate pools. Theorem 4.1. When 𝑀 = ∞, pruning on the whole candidate graph is equivalent to pruning directly on the candidate graph induced by the query-valid nodes. In other words, the candidate-based pruning procedure preserves heredity asymptotically. Proof. When 𝑀 = ∞, the candidate set is not truncated, so all possible witness nodes are available. Let 𝐺 [𝐼 ] be the graph obtained by pruning the whole candidate graph and then restricting it to the query-valid nodes, and let 𝐺 ′ be the graph obtained by directly pruning the candidate graph induced by the same valid node set. Since both procedures operate on the same valid node set, they have the same candidate edges before pruning. We compare edges in ascending order of distance. The shortest edge cannot be pruned. For any edge (𝑢, 𝑣), a semantic bit is pruned iff there exists a shorter valid witness node 𝑤 satisfying the corresponding pruning condition. Such a witness is preserved

Algorithm 5: Entry Node Acquisition Input : Query interval 𝑞𝐼 = [𝑞𝑙 , 𝑞𝑟 ], query type 𝑡𝑦𝑝𝑒, sorted arrays 𝐴𝑟𝑟 Output : Entry node ID or NULL 1 Function GetEntryNode(𝑞 𝐼 , 𝑡𝑦𝑝𝑒) 2 if 𝑡𝑦𝑝𝑒 = IF then 3 𝑖 ← BinarySearchFirst(𝐴𝑟𝑟 .𝐿, ≥, 𝑞𝑙 ); 4 if 𝑖 is valid and 𝐴𝑟𝑟 .𝑆𝑢 𝑓 𝑓 𝑀𝑖𝑛𝑅 [𝑖].𝑣𝑎𝑙 ≤ 𝑞𝑟 then 5 return 𝐴𝑟𝑟 .𝑆𝑢 𝑓 𝑓 𝑀𝑖𝑛𝑅 [𝑖].𝑛𝑜𝑑𝑒_𝑖𝑑;

9

else if 𝑡𝑦𝑝𝑒 = IS then 𝑖 ← BinarySearchLast(𝐴𝑟𝑟 .𝐿, ≤, 𝑞𝑙 ); if 𝑖 is valid and 𝐴𝑟𝑟 .𝑃𝑟𝑒 𝑓 𝑀𝑎𝑥𝑅 [𝑖].𝑣𝑎𝑙 ≥ 𝑞𝑟 then return 𝐴𝑟𝑟 .𝑃𝑟𝑒 𝑓 𝑀𝑎𝑥𝑅 [𝑖].𝑛𝑜𝑑𝑒_𝑖𝑑;

10

return NULL;

6 7 8

Query Idx 0 1 Idx 1 Idx 2 Idx 3 Idx 4

2

10 Min R: 7 (Pos: 2)

8

1

Min R: 7 (Pos: 2)

3

4.5

11

Min R: 9 (Pos: 3)

6

8

Max R: 11 (Pos: 1)

11

Max R: 11 (Pos: 1)

7

5

Max R: 8 (Pos: 0)

3

Min R: 7 (Pos: 2)

4

9.5

4

9

Min R: 12 (Pos: 4)

7

5 12

Max R: 11 (Pos: 1)

6

9

Max R: 12 (Pos: 4)

12

1 2 3 4 5 6 7 8 9 10 11 12

1 2 3 4 5 6 7 8 9 10 11 12

(a) IFANN Entry Node

(b) ISANN Entry Node

Figure 5: Entry Node Acquisition after restricting to valid nodes: under IF semantics, the pruning condition implies [𝑤 .𝑙, 𝑤 .𝑟 ] ⊆ [min(𝑢.𝑙, 𝑣.𝑙), max(𝑢.𝑟, 𝑣.𝑟 )] ⊆ 𝐼, so 𝑤 is query-valid; under IS semantics, it implies 𝐼 ⊆ [max(𝑢.𝑙, 𝑣.𝑙), min(𝑢.𝑟, 𝑣.𝑟 )] ⊆ [𝑤 .𝑙, 𝑤 .𝑟 ], so 𝑤 is also query-valid. Therefore, every witness used in the whole graph also appears in the induced graph, and vice versa. Hence each edge has the same IF/IS semantic state in 𝐺 [𝐼 ] and 𝐺 ′ , implying 𝐺 [𝐼 ] = 𝐺 ′ . Therefore, when 𝑀 = ∞, candidate-based pruning preserves structural heredity. □ Theorem 4.2. The construction complexity of UG is 𝑂 (𝑇𝐶𝑀𝑢𝑔 ), where 𝑇 is the number of pruning iterations, 𝐶 = 𝑒 𝑓𝑠𝑝𝑎𝑡𝑖𝑎𝑙 +𝑒 𝑓𝑎𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒 is the candidate set size, and 𝑀𝑢𝑔 denotes the number of effective edge examinations in UG. Proof. In each iteration, UG examines candidate edges and may generate additional repair candidates from pruned edges. Under a small number of iterations, the candidate pool remains stable up to a constant factor after deduplication. Therefore, the total cost scales linearly with the number of iterations, the candidate size, and the number of effective edge examinations, yielding 𝑂 (𝑇𝐶𝑀𝑢𝑔 ). □

Efficient Graph Indexing for Interval-Aware Vector Search

Preprint, 2026,

Table 1: Dataset Statistics

4.3

Query Processing

We propose an efficient search algorithm that supports ANN search over the UG. Based on Theorem 4.1, UG can be searched directly under the query predicate without explicitly materializing the queryinduced subgraph, which would otherwise incur substantial perquery overhead. To initialize search within the valid subgraph, UG first locates an entry node that already satisfies the query predicate. This is achieved by sorting all nodes by their left endpoints and maintaining two auxiliary arrays: the suffix minimum of right endpoints and the prefix maximum of right endpoints. As shown in Algorithm 5, this allows a valid entry node, if one exists, to be found in logarithmic time. Given the acquired entry node, Algorithm 4 performs an intervalaware beam search on the unified physical graph. Instead of constructing different graph structures for IFANN and ISANN queries, UG dynamically filters neighbors using the semantic bitmask stored on each edge together with the corresponding interval predicate. In this way, the same physical graph is searched as the logical IFANN-induced or ISANN-induced subgraph, depending on the query type. Lemma 4.3 (Entry-node acqisition). Algorithm 5 is correct for both IFANN and ISANN queries. In particular: (1) if the algorithm returns a node 𝑢 ≠ NULL, then 𝑢 satisfies the corresponding query predicate; (2) if the algorithm returns NULL, then no valid node exists in the dataset for that query; (3) the time complexity of a single invocation is 𝑂 (log 𝑛). Proof. For an IFANN query, the algorithm first finds the smallest index 𝑖 such that 𝑙𝑢 ≥ 𝑞𝑙 . Any valid node must therefore lie in the suffix starting from 𝑖. If the minimum right endpoint in this suffix is at most 𝑞𝑟 , then the returned node satisfies 𝑙𝑢 ≥ 𝑞𝑙 and 𝑟𝑢 ≤ 𝑞𝑟 , and is thus valid. Otherwise, no node in the suffix can satisfy the IFANN predicate, which means no valid IFANN node exists. For an ISANN query, the algorithm finds the largest index 𝑖 such that 𝑙𝑢 ≤ 𝑞𝑙 . Any valid node must then lie in the prefix ending at 𝑖. If the maximum right endpoint in this prefix is at least 𝑞𝑟 , then the returned node satisfies 𝑙𝑢 ≤ 𝑞𝑙 and 𝑟𝑢 ≥ 𝑞𝑟 , and is therefore valid. Otherwise, no node in the prefix can satisfy the ISANN predicate, so no valid ISANN node exists. In both cases, the algorithm consists of one binary search followed by a constant number of array accesses and comparisons, yielding a total complexity of 𝑂 (log 𝑛). □ Example. Figure 5 illustrates the entry-node acquisition procedure for both query types. In Figure (a), for the IFANN query interval [2, 10], the binary search first identifies the suffix of nodes with left endpoints no smaller than 2, and the entry node is then selected by the suffix-minimum right endpoint, yielding the valid interval [4, 7]. In Figure (b), for the ISANN query interval [4.5, 9.5], the binary search identifies the prefix of nodes with left endpoints no greater than 4.5, and the entry node is obtained by the prefix-maximum right endpoint, yielding the valid interval [3, 11]. This example shows that the entry-node acquisition procedure is not only efficient, but also directly aligned with the two interval predicates.

Datasets

|𝐷 |

|𝑄 |

𝑑

Vector Type

DB-OpenAI GIST1M S&P 500 SIFT1M DEEP1M

990,000 1,000,000 1,445,794 1,000,000 990,000

10,000 1,000 14,603 10,000 10,000

1,536 960 384 128 96

text image financial image image

5 Experiments 5.1 Experimental Setup Datasets. We evaluate our methods on five public datasets, including one real-world dataset (S&P 500) and four widely used benchmark datasets (DB-OpenAI, GIST1M, SIFT1M, and DEEP1M) [2, 57]. The dataset statistics are summarized in Table 1. Following prior work [29, 52, 57], the interval attributes and query ranges are synthetically generated for all datasets except S&P 500, since such attributes are rarely available due to privacy concerns. For S&P 500, the attributes are derived from real financial data. Baselines. First, for Interval-Filtering ANN (IFANN) queries, we compare against representative methods proposed in [57], including HNSW [35], Vamana [24], NSG [16], HCNNG [47], Hi-PNG-HNSW (denoted as H-HNSW), Hi-PNG-Vamana (denoted as H-Vamana), Hi-PNG-NSG (denoted as H-NSG), and Hi-PNG-HCNNG (denoted as H-HCNNG). HNSW, Vamana, NSG, and HCNNG adopt a postfiltering strategy, i.e., retrieving top-𝑘 ′ candidates first and then applying interval filtering, while the Hi-PNG variants partition the interval space hierarchically and build graph indexes on the corresponding partitions. Second, for Range-Stabbing ANN (RSANN) queries, we compare against Timestamp [52] and HNSW. In particular, HNSW also adopts a post-filtering strategy, while TG constructs timestamp-aware graph indexes and compresses them into a single structure for efficient querying. Third, for Range-Filtered ANN (RFANN) queries, we compare against RFANN-specific methods including SeRF [65], DSG [41], ACORN [40], iRangeGraph [56], UNIFY [31], Faiss-HNSW [11], SuperPostfiltering [12]. Finally, for Interval-Stabbing ANN (ISANN) queries, we compare against HNSWhnswlib [35] as the only available baseline. Unless otherwise specified, we follow the benchmark implementation and parameter settings in the existing experimental evaluation [29, 52, 57]. Query Workloads. For the IFANN queries, we adopt the realworld interval query data for the S&P 500 dataset and the uniform workload for the other four datasets. To further analyze robustness under different filtering conditions, we additionally construct three non-uniform workloads on GIST1M, namely short, long, and mixed. Specifically, short queries have selectivity below 5%, long queries have selectivity above 20%, and mixed queries contain an equal proportion of short and long intervals. For the experiments on other query types (ISANN, RFANN, and RSANN), we report results on GIST1M and SIFT1M under the uniform workload by default. Parameter Settings. First, for IFANN queries, the H-PNG builds upon four representative graph-based ANN backbones, including HNSW, Vamana, NSG, and HCNNG. Following previous studies [57], during the indexing phase, for HNSW, Vamana, and NSG, we set the maximum degree 𝑀 = 32 and the construction candidate size 𝑒 𝑓construction = 128. For Vamana, we set 𝛼 = 1.2. For HCNNG, we set the number of randomized clustering trees 𝑇 = 10 to ensure global connectivity, the leaf size threshold 𝐿𝑠 = 1000 to terminate recursive partitioning, and the local MST degree upper bound 𝑠 = 5

Preprint, 2026,

UG 10

10³

10³

HNSW

VAMANA

NSG 10

HCNNG

H-HNSW

10

QPS

10

H-VAMANA 10

H-NSG

Liang et al.

H-HCNNG 10

10

10

10³

10³

10³ 10²

10²

10¹ 0.80

0.85

0.90

0.95

Recall@10

1.00

10²

10¹ 0.80

0.85

0.90

0.95

Recall@10

(a) DB-OpenAI

1.00

10¹ 0.80

(b) GIST1M

0.85

0.90

0.95

Recall@10

1.00

10² 0.80

(c) S&P 500

0.85

0.90

0.95

Recall@10

10² 0.80

1.00

(d) SIFT1M

0.85

0.90

0.95

Recall@10

1.00

(e) DEEP1M

Figure 6: The accuracy–efficiency trade-off for IFANN queries under the uniform workload. UG

HNSW

Timestamp

ACORN

DSG

SeRF

SuperPostfiltering

UNIFY

iRangeGraph

QPS

10 10³

10³ 10

10³

10² 0.80

10³

10

0.85

0.90

0.95

Recall@10 (a) GIST1M (ISANN)

10³ 1.00 0.80

0.85

0.90

0.95

Recall@10 (b) SIFT1M (ISANN)

10² 1.00 0.80

0.85

0.90

0.95

1.00

Recall@10 (c) GIST1M (RFANN)

0.80

0.85

0.90

0.95

1.00

Recall@10 (d) SIFT1M (RFANN)

10² 0.80

0.85

0.90

0.95

1.00

Recall@10 (e) GIST1M (RSANN)

0.80

0.85

0.90

0.95

Recall@10 (f) SIFT1M (RSANN)

1.00

Figure 7: Query performance under diverse query types to maintain graph sparsity. For the Hi-PNG-specific construction, have the following observations: (1) Across all five datasets, UG the leaf size threshold is set to 𝑙𝑠 = 10000, which determines when consistently outperforms other methods. Specifically, on the recursive interval partitioning stops. Second, for RSANN queries, real-world S&P dataset, when recall@10 = 95%, UG reaches about we follow the settings used in the original papers for Timestamp 62,029 QPS, whereas the strongest baseline, H-HCNNG, achieves and HNSW [52]. Third, for RFANN queries, we use the settings only about 587 QPS, yielding a 105× speedup. (2) UG exhibits an even larger advantage in the high-recall regime. In particureported in existing experimental evaluation [29] and follow its lar, on the S&P dataset, at recall@10 = 98%, UG achieves approxiconfigurations for SeRF, DSG, ACORN, iRangeGraph, UNIFY, Faissmately 40,000 QPS, whereas the strongest baseline, H-NSG, reaches HNSW, and SuperPostfiltering. In particular, we use the same global only 136 QPS, corresponding to a 294× speedup. (3) H-HNSW, graph configuration 𝑀 = 40 and 𝑒 𝑓construction = 1000 unless otherH-HCNNG, H-NSG, and H-VAMANA exhibit comparable perwise specified. For ACORN, we set 𝛾 = 25. For SeRF, we set 𝑀 = 8 formance across the five datasets, while significantly outperand 𝑒 𝑓max = 𝑒 𝑓construction = 1000. DSG follows the same settings forming their respective counterparts. This validates that the as SeRF. For 𝛽-WST, we set split_factor = 2 and shift_factor = 0.5. Hi-PNG algorithm is the key contributor, whereas existing graphFor iRangeGraph, we use the same global graph configuration. For based methods fail to effectively handle such interval-aware ANN UNIFY, we set 𝐵 = 8, with low_threshold = 5% and high_threshold = queries. 50%, and enable the combined filtering strategy. Fourth, for ISANN Exp-2: Query performance under diverse query types. The queries, we use the HNSW-hnswlib as the baseline , with 𝑀 = 16 query performance of our proposed UG and the ISANN, RFANN, and 𝑒 𝑓construction = 200. For our proposed UG, unless otherwise and RSANN baselines is shown in Figure 7. The experimental respecified, we use the default setting 𝑒 𝑓spatial = 128, 𝑒 𝑓attribute = 300, sults demonstrate that our proposed UG consistently delivers max_edges𝐼 𝐹 = 256, max_edges𝐼𝑆 = 256, and 5 refinement iterations. state-of-the-art query performance. In particular, for ISANN, In the scalability experiment, we set 𝑒 𝑓spatial = 32 for nndescent. UG consistently outperforms the baseline. Under the uniform workEvaluation Metrics. Following previous studies [57, 64], we adopt load, when recall@10 = 95%, UG achieves about 2127.66 QPS on two standard metrics to evaluate querying performance. Accuracy GIST1M and 33333 QPS on SIFT1M, whereas HNSW achieves only is measured by recall@𝑘 = | R∩𝑘 R̃ | , where R denotes the result set about 245 and 3676 QPS, corresponding to speedups of about 8.7× returned by the evaluated method and R̃ represents the groundand 9.1×, respectively. For RSANN and RFANN, UG also achieves truth set obtained via brute-force search. Consistent with recent performance comparable to that of query-specific optimized basestudies [57, 64], we report recall@10, while also presenting results lines. It is worth noting that we investigate the scenario in which for varying 𝑘 values (Exp-6). Efficiency is measured using queries queries of different types are issued in the same query workload, |𝑄 | per second (QPS), computed as QPS = 𝑡 , where |𝑄 | queries are which suggests that UG provides the best overall solution for hanprocessed within time 𝑡. dling diverse query types in diverse query workloads. Implementation. All experiments are conducted on a Linux server Exp-3: Query performance under diverse filtering workloads. equipped with a single AMD Ryzen Threadripper 3990X 64-Core To further assess the benefits of the proposed UG across different Processor (2.2GHz) and 224 GB of memory. All algorithms are query workloads, we evaluate the IFANN query performance of implemented in C++ and compiled with GCC 14.3.0 using the all methods on the Long, Mixed, Short, and Uniform workloads of Ofast optimization flag. the GIST1M dataset. The querying performance is presented in Figure 10. The results confirm that our proposed UG consistently maintains its advantage across different workloads. In partic5.2 Experimental Results ular, when recall@10 = 95%, UG achieves about 1,999, 2,975, 2,014, Exp-1: Interval-Filtering ANN querying performance. The and 2,761 QPS under the Long, Mixed, Short, and Uniform workquery performance of our proposed UG and the compared IFANN loads, respectively. In comparison, the fastest baselines only achieve baselines under the uniform workload is shown in Figure 6. We

Efficient Graph Indexing for Interval-Aware Vector Search UG HNSW VAMANA 10 10

NSG 10³

Build Time (s)

10²

10³

10²

10³

(a) DB-OpenAI

10²

HCNNG

H-VAMANA 10³

H-NSG

H-HCNNG 10³

10²

10¹

(b) GIST1M

H-HNSW

(c) S&P 500

10¹

Preprint, 2026,

10²

10¹

(d) SIFT1M

(e) DEEP1M

Figure 8: The indexing time of all IFANN baselines across the five datasets. UG 10³

Index Size (MB)

10³

HNSW

VAMANA

NSG 10³

HCNNG

H-HNSW

H-VAMANA 10³

H-NSG

H-HCNNG 10³

10² 10²

10²

10²

10²

10¹ 10

(a) DB-OpenAI

10¹

(b) GIST1M

10¹

(c) S&P 500

10¹

(d) SIFT1M

10¹

(e) DEEP1M

Figure 9: The memory cost of all IFANN baselines across the five datasets.

QPS

10

UG HNSW VAMANA NSG H-HNSW H-VAMANA H-NSG

10

10³

10³

10²

10²

HCNNG H-HCNNG

10¹0.80 0.85 0.90 0.95 1.00 10¹0.80 0.85 0.90 0.95 1.00

QPS

10

Recall@10 (a) Long

10

10³

10³

10²

10²

Recall@10 (b) Short

10¹0.80 0.85 0.90 0.95 1.00 10¹0.80 0.85 0.90 0.95 1.00

Recall@10 (c) Mixed

Recall@10 (d) Uniform

Figure 10: The accuracy–efficiency trade-off for IFANN queries under diverse filtering workloads on GIST1M. about 1,056, 684, 482, and 445 QPS under these four workloads, respectively, leading to speedups of about 1.9×, 4.4×, 4.2×, and 6.2×. This indicates that UG can sustain substantially higher throughput even when the filtering condition becomes more selective. Exp-4: Indexing Cost. Figures 8 and 9 report the indexing time and index size of different IFANN methods on the five datasets, while similar patterns are observed on other query types. In terms of indexing time, UG is comparable to competitive baselines and even outperforms them on several datasets. For example, on GIST1M, UG takes about 678.9 s to build the index, whereas the best baseline, H-NSG, requires about 947.5 s, yielding a 1.4× speedup. This shows that UG not only delivers superior query performance but also offers a clear advantage in index construction time. For memory consumption, UG maintains a moderate index size compared with competitive baselines. For instance, on GIST1M, UG uses about 218.7 MB, substantially less than H-HCNNG and H-HNSW, which require 272.4 MB and 262.0 MB. Equivalently, the indexes of H-HCNNG and H-HNSW are about 1.25× and 1.20× larger than that of UG, respectively. These results indicate that

UG does not achieve its query advantage at the cost of excessive memory consumption. Overall, UG provides a favorable trade-off between indexing overhead and query efficiency. Exp-5: Querying performance with different 𝑘. We further analyze the effect of different 𝑘 values on query performance on the GIST1M dataset, as shown in Figure 12. Overall, QPS gradually decreases as k increases steadily.This is expected: a larger 𝑘 requires the system to return more results, which expands the search scope and increases the cost of candidate exploration. These results demonstrate that our proposed UG adapts well to varying retrieval requirements. Exp-6: Sensitivity study. We conduct a parameter sensitivity study for UG on IFANN queries using the GIST1M dataset and the results are shown in Figure 11. This proves that UG is not highly sensitive to parameter variations. In particular, for 𝑒 𝑓𝑎𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒 and 𝑒 𝑓𝑠𝑝𝑎𝑡𝑖𝑎𝑙 , increasing the parameter generally improves the highrecall region, although the gain gradually saturates. Meanwhile, larger values also lead to longer index construction time and higher memory consumption, so overly aggressive settings are unnecessary. The effect of iteration is more direct, and most of the gain is obtained within the first few iterations. As the iteration count increases from 1 to 3, the QPS-Recall curve improves substantially. However, the additional gain becomes small when it further increases to 4 and 5. This shows that only a small number of iterations is needed to obtain most of the benefit. In contrast, small values of 𝑚𝑎𝑥𝑒𝑑𝑔𝑒𝑠 noticeably limit the final performance, while medium values already capture most of the gain. However, the gain also gradually saturates as the parameter becomes larger. At the same time, larger 𝑚𝑎𝑥𝑒𝑑𝑔𝑒𝑠 values also imply higher construction and memory overhead. In practice, moderate parameter values are already sufficient to achieve a favorable balance between query performance and indexing overhead. Exp-7: Scalability Study. To evaluate the scalability of UG, we conduct IFANN experiments with increasing dataset size from SIFT100M, namely 10M, 20M, 30M, and 40M. Figure 13 reports the query latency at recall@10 = 90% and the index build time under different dataset sizes. Overall, as the dataset size increases, both query latency and build time grow steadily, while the overall trend remains smooth, demonstrating good scalability of UG on larger datasets.

10³

Liang et al.

10 10³

ef_attribute 100 1000 250 1500 500

Latency (ms)

QPS

10

ef_spatial 50 200 100 250 150

10² 0.80 0.85 0.90 0.95 1.00 10² 0.80 0.85 0.90 0.95 1.00

Recall@10 (a) ef_attribute

QPS

10³

iteration 1 4 2 5 3

max_edges 75 350 150 450 250

QPS

10³

10³ 10²0.80

Recall@10 (d) max_edges

Figure 11: Parameter sensitivity 10

10

k=10 k=20 k=40

k=70 k=100

0.85

0.90

0.95

Recall@k (a) IFANN

1.00 10²0.80

k=10 k=20 k=40

k=70 k=100

0.85

0.90

0.95

Recall@k (b) RSANN

1.00

Figure 12: Querying performance with different 𝑘.

6

1150 750 20M

30M

40M

10M

20M

30M

Dataset size (b) Build time

350 40M

Figure 13: Scalability with increasing dataset size.

10² 0.80 0.85 0.90 0.95 1.00 10² 0.80 0.85 0.90 0.95 1.00

Recall@10 (c) iteration

1550

Dataset size (a) Latency at recall@10 = 90%

10

10 10³

Recall@10 (b) ef_spatial

3.0 2.5 2.0 1.5 1.0 10M

Build time (s)

Preprint, 2026,

Related Work

Approximate Nearest Neighbor Search. Existing ANN indexes can be broadly categorized into four categories: graph-based [3, 16, 22, 34, 35, 51], quantization-based [17, 18, 20, 25, 36], hashingbased [42, 48, 50], and tree-based [5, 43]. A more overview is provided in recent surveys [37, 38]. Extensive empirical evaluations [2, 3, 30, 50] have consistently shown that graph-based methods achieve state-of-the-art performance. This superiority stems from the graph’s ability to encode proximity relationships, allowing query processing to converge rapidly by evaluating only a small fraction of the dataset [10]. Most graph-based indexes [51] are built upon four fundamental graph types: the Delaunay Graph (DG) [14], Relative Neighborhood Graph (RNG) [46], K-Nearest Neighbor Graph (KNNG) [39], and Minimum Spanning Tree (MST) [26]. Among these, RNG-based indexes achieve particularly strong performance due to their effective pruning strategy [51]. Building on RNG, we propose a novel ANN index to support efficient Interval-aware ANN search. Attribute-filtered ANN Search. Existing attribute-filtered ANN queries typically involve two types of attributes: keyword and numerical. Keyword attributes are unordered, whereas numerical attributes are inherently ordered. Consequently, different methods have been proposed to handle different types of attributes [40, 59, 65]. For numerical attributes, several specialized queries have been proposed [57, 65], including RFANN and IFANN queries, as described in Section 2. To support these queries, various indexes have been introduced [49, 56, 57]. Early studies [11, 49, 61] follow a two-stage paradigm, constructing separate indexes for vector and attribute retrieval before merging the results. For example, ADBV [54] employs a B-Tree and a PQ index independently, selecting a retrieval strategy via a cost model. A key limitation of

such approaches is that they do not co-optimize the index structure, resulting in sub-optimal performance compared with hybrid indexes [8, 12, 29, 31, 56, 65]. Recently, many hybrid indexes have been proposed, such as iRangeGraph [56], which integrates graph and attribute indexes more directly by constructing a graph for each segment of a partitioned attribute range. While this design achieves high performance, it incurs substantial indexing overhead and exhibits limited adaptability to different query types. For keyword attributes, similar techniques and strategies have been proposed, such as Faiss [11], Milvus [49], VBASE [62], ACORN [40], Filtered-DiskANN [19] (microsoft). However, they also suffer from either low query performance or high indexing time and limited adaptability to different query types. Recently, several efforts have aimed to design a unified index to support different query types. For example, [55] supports both conventional ANN queries and ANN queries with keyword predicates within a single index. However, designing one index to support for diverse numerical-attribute queries remains underexplored.

7

Conclusion and Future Work

In this paper, we propose an efficient graph index, UG, to handle various interval-aware ANN queries within a single index. We first introduce the Unified Interval-aware Relative Neighborhood Graph (URNG), which establishes the theoretical foundation for intervalaware ANN search. We then present UG, an efficient and practical approximation of URNG. Experimental results show that, for various interval-aware ANN queries, UG significantly outperforms the baselines in search efficiency, while incurring no additional index construction time or storage overhead. One direction for future work is to extend our theoretical graph and index beyond numerical attributes to support more diverse filtered search scenarios, such as keyword filtering. Building upon this, we aim to investigate and develop a unified theoretical framework capable of seamlessly accommodating arbitrary predicate filtering conditions, ultimately providing a generalized index for complex hybrid queries.

References [1] Akhil Arora, Sakshi Sinha, Piyush Kumar, and Arnab Bhattacharya. 2018. Hdindex: Pushing the scalability-accuracy boundary for approximate knn search in high-dimensional spaces. arXiv preprint arXiv:1804.06829 (2018). [2] Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. 2020. ANNBenchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems 87 (2020), 101374. [3] Ilias Azizi, Karima Echihabi, and Themis Palpanas. 2025. Graph-based vector search: An experimental evaluation of the state-of-the-art. Proceedings of the ACM on Management of Data 3, 1 (2025), 1–31. [4] Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, and Uri Shaft. 1999. When is “nearest neighbor” meaningful?. In International Conference on Database Theory. Springer, 217–235. [5] Alina Beygelzimer, Sham Kakade, and John Langford. 2006. Cover trees for nearest neighbor. In Proceedings of the 23rd International Conference on Machine

Efficient Graph Indexing for Interval-Aware Vector Search

Learning. 97–104. [6] Markus M Breunig, Hans-Peter Kriegel, Raymond T Ng, and Jörg Sander. 2000. LOF: identifying density-based local outliers. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. 93–104. [7] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020. Language models are few-shot learners. Advances in Neural Information Processing Systems 33 (2020), 1877–1901. [8] Yannis Chronis, Helena Caminal, Yannis Papakonstantinou, Fatma Özcan, and Anastasia Ailamaki. 2025. Filtered vector search: State-of-the-art and research opportunities. Proceedings of the VLDB Endowment 18, 12 (2025), 5488–5492. [9] Thomas Cover and Peter Hart. 1967. Nearest neighbor pattern classification. IEEE Transactions on Information Theory 13, 1 (1967), 21–27. [10] Magdalen Dobson, Zheqi Shen, Guy E Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. 2023. Scaling graph-based anns algorithms to billion-size datasets: A comparative analysis. arXiv preprint arXiv:2305.04359 (2023). [11] Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2025. The faiss library. IEEE Transactions on Big Data (2025). [12] Joshua Engels, Benjamin Landrum, Shangdi Yu, Laxman Dhulipala, and Julian Shun. 2024. Approximate nearest neighbor search with window filters. arXiv preprint arXiv:2402.00943 (2024). [13] Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu, et al. 1996. A densitybased algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), Vol. 96. 226–231. [14] Steven Fortune. 2017. Voronoi diagrams and Delaunay triangulations. In Handbook of Discrete and Computational Geometry. Chapman and Hall/CRC, 705–721. [15] Cong Fu, Changxu Wang, and Deng Cai. 2021. High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility. IEEE Transactions on Pattern Analysis and Machine Intelligence 44, 8 (2021), 4139–4150. [16] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2017. Fast approximate nearest neighbor search with the navigating spreading-out graph. arXiv preprint arXiv:1707.00143 (2017). [17] Jianyang Gao and Cheng Long. 2024. Rabitq: Quantizing high-dimensional vectors with a theoretical error bound for approximate nearest neighbor search. Proceedings of the ACM on Management of Data 2, 3 (2024), 1–27. [18] Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized product quantization. IEEE Transactions on Pattern Analysis and Machine Intelligence 36, 4 (2013), 744–755. [19] Siddharth Gollapudi, Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy, Nikit Begwani, Swapnil Raz, Yiyong Lin, Yin Zhang, Neelam Mahapatro, Premkumar Srinivasan, et al. 2023. Filtered-diskann: Graph algorithms for approximate nearest neighbor search with filters. In Proceedings of the ACM Web Conference 2023. 3406–3416. [20] Yunchao Gong, Svetlana Lazebnik, Albert Gordo, and Florent Perronnin. 2012. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence 35, 12 (2012), 2916–2929. [21] Gaurav Gupta, Jonah Yi, Benjamin Coleman, Chen Luo, Vihan Lakshman, and Anshumali Shrivastava. 2023. Caps: A practical partition index for filtered similarity search. arXiv preprint arXiv:2308.15014 (2023). [22] Ben Harwood and Tom Drummond. 2016. Fanng: Fast approximate nearest neighbour graphs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 5713–5722. [23] Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. 604–613. [24] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32. Curran Associates, Inc. [25] Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence 33, 1 (2010), 117–128. [26] Joseph B Kruskal. 1956. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc. 7, 1 (1956), 48–50. [27] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. 2015. Deep learning. Nature 521, 7553 (2015), 436–444. [28] Jie Li, Haifeng Liu, Chuanghua Gui, Jianyu Chen, Zhenyuan Ni, Ning Wang, and Yuan Chen. 2018. The design and implementation of a real time visual search system on JD E-commerce platform. In Proceedings of the 19th International Middleware Conference Industry. 9–16. [29] Mocheng Li, Xiao Yan, Baotong Lu, Yue Zhang, James Cheng, and Chenhao Ma. 2025. Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth

Preprint, 2026,

Experimental Study. Proceedings of the ACM on Management of Data 3, 6 (2025), 1–26. [30] Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. 2019. Approximate nearest neighbor search on high dimensional data—experiments, analyses, and improvement. IEEE Transactions on Knowledge and Data Engineering 32, 8 (2019), 1475–1488. [31] Anqi Liang, Pengcheng Zhang, Bin Yao, Zhongpu Chen, Yitong Song, and Guangxu Cheng. 2024. Unify: Unified index for range filtered approximate nearest neighbors search. arXiv preprint arXiv:2412.02448 (2024). [32] Siyuan Liang, Ziqi Yin, Qi Zhang, Rong hua Li, Guoren Wang, Kaiwen Xue, Daiyin Wang, and Xubin Li. 2026. One Index is All You Need: A Unified Graph Index for Interval-Aware Approximate Nearest Neighbor Search: Full Version. https://github.com/bbtsrr/UG-submit. Full version. [33] Ying Liu, Dengsheng Zhang, Guojun Lu, and Wei-Ying Ma. 2007. A survey of content-based image retrieval with high-level semantics. Pattern Recognition 40, 1 (2007), 262–282. [34] Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. 2014. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems 45 (2014), 61–68. [35] Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 42, 4 (2018), 824–836. [36] Yusuke Matsui, Yusuke Uchida, Hervé Jégou, and Shin’ichi Satoh. 2018. A survey of product quantization. ITE Transactions on Media Technology and Applications 6, 1 (2018), 2–10. [37] James Jie Pan, Jianguo Wang, and Guoliang Li. 2023. Survey of vector database management systems. arXiv preprint arXiv:2310.14021 (2023). [38] James Jie Pan, Jianguo Wang, and Guoliang Li. 2024. Vector database management techniques and systems. In Companion of the 2024 International Conference on Management of Data. 597–604. [39] Rodrigo Paredes and Edgar Chávez. 2005. Using the k-nearest neighbor graph for proximity searching in metric spaces. In International Symposium on String Processing and Information Retrieval. Springer, 127–138. [40] Liana Patel, Peter Kraft, Carlos Guestrin, and Matei Zaharia. 2024. Acorn: Performant and predicate-agnostic search over vector embeddings and structured data. Proceedings of the ACM on Management of Data 2, 3 (2024), 1–27. [41] Zhencan Peng, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. 2025. Dynamic Range-Filtering Approximate Nearest Neighbor Search. Proceedings of the VLDB Endowment 18, 10 (2025). [42] Ninh Pham and Tao Liu. 2022. Falconn++: A locality-sensitive filtering approach for approximate nearest neighbor search. Advances in Neural Information Processing Systems 35 (2022), 31186–31198. [43] Parikshit Ram and Kaushik Sinha. 2019. Revisiting kd-tree for nearest neighbor search. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 1378–1388. [44] Nils Reimers and Iryna Gurevych. 2019. Sentence-bert: Sentence embeddings using siamese bert-networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 3982–3992. [45] Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. 2001. Item-based collaborative filtering recommendation algorithms. In Proceedings of the 10th International Conference on World Wide Web. 285–295. [46] Godfried T Toussaint. 1980. The relative neighbourhood graph of a finite planar set. Pattern Recognition 12, 4 (1980), 261–268. [47] Javier Vargas Muñoz, Marcos A. Gonçalves, Zanoni Dias, and Ricardo da S. Torres. 2019. Hierarchical Clustering-Based Graphs for Large Scale Approximate Nearest Neighbor Search. Pattern Recognition 96 (2019), 106970. doi:10.1016/j.patcog. 2019.106970 [48] Jingdong Wang, Heng Tao Shen, Jingkuan Song, and Jianqiu Ji. 2014. Hashing for similarity search: A survey. arXiv preprint arXiv:1408.2927 (2014). [49] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, et al. 2021. Milvus: A purpose-built vector data management system. In Proceedings of the 2021 International Conference on Management of Data. 2614–2627. [50] Jingdong Wang, Ting Zhang, Nicu Sebe, Heng Tao Shen, et al. 2017. A survey on learning to hash. IEEE Transactions on Pattern Analysis and Machine Intelligence 40, 4 (2017), 769–790. [51] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. arXiv preprint arXiv:2101.12631 (2021). [52] Yuxiang Wang, Ziyuan He, Yongxin Tong, Zimu Zhou, and Yiman Zhong. 2025. Timestamp Approximate Nearest Neighbor Search over High-Dimensional Vector Data. In 2025 IEEE 41st International Conference on Data Engineering (ICDE). IEEE, 3043–3055. [53] Roger Weber, Hans-Jörg Schek, Stephen Blott, et al. 1998. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In VLDB ’98: Proceedings of the 24th International Conference on Very Large Data Bases, Vol. 98. 194–205.

Preprint, 2026,

[54] Chuangxian Wei, Bin Wu, Sheng Wang, Renjie Lou, Chaoqun Zhan, Feifei Li, and Yuanzhe Cai. 2020. AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data. Proceedings of the VLDB Endowment 13, 12 (2020), 3152–3165. [55] Jiadong Xie, Jeffrey Xu Yu, Siyi Teng, and Yingfan Liu. 2025. Beyond Vector Search: Querying With and Without Predicates. Proceedings of the ACM on Management of Data 3, 6 (2025), 1–26. [56] Yuexuan Xu, Jianyang Gao, Yutong Gou, Cheng Long, and Christian S Jensen. 2024. irangegraph: Improvising range-dedicated graphs for range-filtering nearest neighbor search. Proceedings of the ACM on Management of Data 2, 6 (2024), 1–26. [57] Ming Yang, Yuzheng Cai, and Weiguo Zheng. 2025. Hi-PNG: Efficient IntervalFiltering ANNS via Hierarchical Interval Partition Navigating Graph. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 2. 3518–3529. [58] Ziqi Yin, Gao Cong, Kai Zeng, Jinwei Zhu, and Bin Cui. 2026. BBC: Improving Large-k Approximate Nearest Neighbor Search with a Bucket-based Result Collector. arXiv:2604.01960 [cs.DB] https://arxiv.org/abs/2604.01960 [59] Ziqi Yin, Shanshan Feng, Shang Liu, Gao Cong, Yew Soon Ong, and Bin Cui. 2024. LIST: Learning to Index Spatio-Textual Data for Embedding based Spatial Keyword Queries. arXiv:2403.07331 [cs.IR] https://arxiv.org/abs/2403.07331 [60] Ziqi Yin, Jianyang Gao, Pasquale Balsebre, Gao Cong, and Cheng Long. 2025. DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph. Proc. ACM Manag. Data 3, 1, Article 29 (Feb. 2025), 28 pages. doi:10.1145/3709679 [61] 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. Proceedings of the ACM on Management of Data 3, 3 (2025), 1–26. [62] Qianxi Zhang, Shuotao Xu, Qi Chen, Guoxin Sui, Jiadong Xie, Zhizhen Cai, Yaoqi Chen, Yinxuan He, Yuqing Yang, Fan Yang, Mao Yang, and Lidong Zhou. 2023. VBASE: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity. In 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23). USENIX Association, Boston, MA, 377–395. [63] Penghao Zhao, Hailin Zhang, Qinhan Yu, Zhengren Wang, Yunteng Geng, Fangcheng Fu, Ling Yang, Wentao Zhang, Jie Jiang, and Bin Cui. 2026. Retrievalaugmented generation for ai-generated content: A survey. Data Science and Engineering (2026), 1–29. [64] Zhiqiu Zou, Ziqi Yin, Rong-Hua Li, Hongchao Qin, Qiangqiang Dai, and Guoren Wang. 2026. RNSG: A Range-Aware Graph Index for Efficient Range-Filtered Approximate Nearest Neighbor Search. arXiv:2603.12913 [cs.DB] https://arxiv. org/abs/2603.12913 [65] Chaoji Zuo, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. 2024. Serf: Segment graph for range-filtering approximate nearest neighbor search. Proceedings of the ACM on Management of Data 2, 1 (2024), 1–26.

A

Proofs for the Complexity Analysis

Lemma A.1 (Expected length of a monotonic path). For any starting node 𝑥 ∈ 𝑉 and the interval-aware nearest neighbor 𝑦 ∈ 𝑉 of a query 𝑞, the expected number of steps of a greedy monotonic walk from 𝑥 to 𝑦 on 𝐺 is 𝑂 (𝑛 1/𝑑 log 𝑛/Δ𝑟 ), where 𝑛 := |𝑉 | and Δ𝑟 denotes the minimum gap between edge lengths among all nonisosceles triangles in the metric space. Proof. Since URNG satisfies monotonic searchability, it belongs to the class of monotonic search networks (MSNETs) in the NSG literature. Therefore, the expected greedy path length on URNG is upper bounded by the corresponding MSNET bound, namely 𝑂 (𝑛 1/𝑑 log(𝑛 1/𝑑 )/Δ𝑟 ), which is 𝑂 (𝑛 1/𝑑 log 𝑛/Δ𝑟 ). □ Lemma A.2 (Average degree bound). Let 𝐷𝑟 denote the average degree of RNG. Then the average degree of URNG is bounded by 𝑂 (𝐶 urng 𝐷𝑟 ). Under the uniform interval model, 𝐶 urng is a constant 31 independent of 𝑛 and may take 𝐶 urng = 6 + 13 3 = 3 . Proof. Fix a node 𝑢 ∈ 𝑉 , and partition the unit sphere centered at 𝑢 into 𝑁𝑑 cones of half-angle 30◦ . For a fixed cone, order the candidate points by distance to 𝑢, let 𝑌𝑡 indicate whether the 𝑡-th Í Í point is retained, and let 𝐾 = 𝑡 𝑌𝑡 . Then E[𝐾] = 𝑡 Pr(𝑌𝑡 = 1).

Liang et al.

For IF semantics, let 𝐽𝑡 = 𝐼𝑢 ∪ 𝐼𝑡 and let 𝐷 = |𝐽𝑡 |. Conditioned on 𝐷 = 𝑝, a random interval is fully contained in 𝐽𝑡 with probability 𝑝 2 , so Pr(𝑌𝑡 = 1 | 𝐷 = 𝑝) = (1 − 𝑝 2 )𝑡 −1 . Since 𝐷 is the range of four i.i.d. uniform variables, its density is 𝑓𝐷 (𝑝) = 12𝑝 2 (1 − 𝑝) on (0, 1). ∫1 ∫ 1 1− (1−𝑝 2 )𝑚 Hence E[𝐾] = 0 12𝑝 2 (1 − 𝑝) 𝑑𝑝 = 12 0 (1 − 𝑝) (1 − (1 − 𝑝2

𝑝 2 )𝑚 ) 𝑑𝑝, which converges to 6 as 𝑚 → ∞. For IS semantics, let 𝐽𝑡 = 𝐼𝑢 ∩ 𝐼𝑡 = [𝐿, 𝑅], which may be empty. Conditioned on 𝐽𝑡 = [𝐿, 𝑅] ≠ ∅, a random interval covers it with probability 2𝐿(1−𝑅), so Pr(𝑌𝑡 = 1 | 𝐽𝑡 = [𝐿, 𝑅]) = (1−2𝐿(1−𝑅))𝑡 −1 . Moreover, Pr(𝐽𝑡 = ∅) = 1/3, and when 𝐽𝑡 ≠ ∅, its density is on 0 < 𝐿 < 𝑅 < 1. Therefore, E[𝐾] = 31 + ∫𝑓 𝐽 (𝐿, 𝑅) = 16𝐿(1 − 𝑅) Í𝑚 16𝐿(1 − 𝑅) 𝑡 =1 (1 − 2𝐿(1 − 𝑅))𝑡 −1 𝑑𝐿 𝑑𝑅, which simplifies 0<𝐿<𝑅<1∫ 1 to 3 + 8 0<𝐿<𝑅<1 (1 − (1 − 2𝐿(1 − 𝑅))𝑚 ) 𝑑𝐿 𝑑𝑅, and converges to 13 3 as 𝑚 → ∞. Thus the expected number of retained neighbors per cone is bounded by 𝐶 urng = 6 + 13 3 . Summing over all cones shows that the average degree of URNG is bounded by a constant factor times that of RNG, namely 𝑂 (𝐶 urng 𝐷𝑟 ). □

Proof of Theorem 3.6. By Lemma A.1, the expected number of expansion steps is 𝑂 (𝑛 1/𝑑 log 𝑛/Δ𝑟 ). By Lemma A.2, each expansion examines 𝑂 (𝐶 urng 𝐷𝑟 ) neighbors in expectation. Therefore, the total expected search complexity is 𝑂 (𝐶 urng 𝐷𝑟 𝑛 1/𝑑 log 𝑛/Δ𝑟 ). Since 𝐶 urng is constant and 𝐷𝑟 is bounded independently of 𝑛, this reduces to 𝑂 (𝑛 1/𝑑 log 𝑛/Δ𝑟 ). Under the spacing assumption Δ𝑟 ≈ 𝑂 (𝑛 −𝜖/𝑑 ) with 0 < 𝜖 < 𝑑, the bound becomes 𝑂 (𝑛 (1+𝜖 )/𝑑 log 𝑛), which is well approximated by 𝑂 (𝑛 1/𝑑 log 𝑛) when 𝜖 ≪ 𝑑. □ Proof of Theorem 3.7. The total index size consists of the storage for nodes and edges. The number of nodes is 𝑂 (𝑛). By Lemma A.2, the expected degree upper bound of URNG is 𝑂 (𝐶 urng 𝐷𝑟 ), where 𝐷𝑟 is the average bound of RNG. Since the total number of edges in RNG is 𝑆𝑟 = 𝑛𝐷𝑟 , the expected total number of edges in URNG is 𝑂 (𝐶 urng𝑛𝐷𝑟 ) = 𝑂 (𝐶 urng𝑆𝑟 ). Because 𝐶 urng is independent of 𝑛, the result follows. □ Proof of Theorem 3.8. In the exact construction procedure, one enumerates each node 𝑥, sorts the remaining nodes by their distances to 𝑥, and then checks all candidate witness nodes to determine whether each edge can be pruned. The sorting stage costs 𝑂 (𝑛 2𝑑), while the witness enumeration stage costs 𝑂 (𝑛 3 ). Since typically 𝑛 ≫ 𝑑, the overall complexity is 𝑂 (𝑛 3 ). □

Related documents

• String Diagrams for Process Mining#978502
• ZigZag Trie: A Novel Index for Contextual Queries#978503
• A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval#978504
• Efficiently Linking Unstructured Data for Multi-step Reasoning#978505