arXiv CSopen access

CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data

CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data Mingyu Yang

Wentao Li

Wei Wang

HKUST (GZ) & HKUST China [email protected]

University of Leicester United Kingdom [email protected]

HKUST (GZ) & HKUST China [email protected]

Abstract

1

Hybrid queries combining high-dimensional vector similarity search with spatio-temporal filters are increasingly critical for modern retrieval-augmented generation (RAG) systems. Existing systems typically handle these workloads by nesting vector indices within low-dimensional spatial structures, such as R-trees. However, this decoupled architecture fragments the vector space, forcing the query engine to invoke multiple disjoint sub-indices per query. This fragmentation destroys graph routing connectivity, incurs severe traversal overhead, and struggles to optimize for complex spatial boundaries. In this paper, we propose CubeGraph, a novel indexing framework designed to natively integrate vector search with arbitrary spatial constraints. CubeGraph partitions the spatial domain using a hierarchical grid, maintaining modular vector graphs within each cell. During query execution, CubeGraph dynamically stitches together adjacent cube-level indices on the fly whenever their spatial cells intersect with the query filter. This dynamic graph integration restores global connectivity, enabling a unified, single-pass nearest-neighbor traversal that eliminates the overhead of fragmented sub-index invocations. Extensive evaluations on real-world datasets demonstrate that CubeGraph significantly outperforms state-of-the-art baselines, offering superior query execution performance, scalability, and flexibility for complex hybrid workloads.

Modern unstructured data, such as text, code, images, user profiles, and videos, is intrinsically linked with spatial and temporal metadata, such as geolocations, timestamps, and trajectories [2]. High-dimensional vector embeddings have become the standard foundation for retrieval augmented generation over such data, mapping each object into a latent space where semantic or visual relevance is measured via inner product or Euclidean distance. Beyond pure similarity search, emerging applications increasingly demand hybrid queries that jointly evaluate vector similarity alongside complex spatial and temporal predicates. In practice, these predicates extend far beyond simple bounding boxes; they require retrieval engines to satisfy constraints over irregular geographic polygons, spatial intersections, temporal windows, and dynamically changing spatio-temporal conditions. While supporting such hybrid queries enables richer information retrieval, it introduces severe challenges for efficient query processing. We illustrate this need through the following motivating examples.

CCS Concepts • Information systems → Data structures; Data management systems; Spatial-temporal systems.

Keywords Nearest Neighbor Search, Spatial Data Management, Filter Search, Retrieval-Augmented Generation ACM Reference Format: Mingyu Yang, Wentao Li, and Wei Wang. 2018. CubeGraph: Efficient RetrievalAugmented Generation for Spatial and Temporal Data. In Proceedings of (Conference acronym ’XX). ACM, New York, NY, USA, 16 pages. https: //doi.org/XXXXXXX.XXXXXXX

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

Introduction

Motivating Example 1: Urban event retrieval. A city management platform stores geo-tagged reports, images, and videos, each represented by a vector embedding and associated with a timestamp and location (Fig. 1). Given a query such as flooded streets, an analyst may search for semantically similar records within a specified time window, but strictly limited to objects located inside an irregular flood-impact region. This query necessitates the seamless integration of vector similarity search with complex spatial and temporal filters. Motivating Example 2: Regional multimedia retrieval. A multimedia database manages geo-tagged images and videos alongside their vector embeddings and timestamps (Fig. 1(2)). Given a query image, a user may search for the most similar objects captured during a specific time interval, constrained within a complex polygonal region and excluding restricted subregions. This requires jointly processing vector similarity with non-rectangular spatial filtering and temporal constraints. Existing database solutions typically model this as a filtered approximate 𝑘-nearest neighbor (AKNN) search problem. Since the exact result is hard to obtain in the high-dimensional space due to the curse of dimensionality [15]. Among various vector index [3, 5, 11–13, 19, 48], graph-based vector indices (e.g., HNSW) offer superior naive AKNN query efficiency [4, 9, 10, 16, 19–21, 24, 26, 27, 29, 30, 36–38, 46, 50], most existing methods attempt to adapt the graph structure or traversal process to accommodate metadata filters [7, 8, 14, 17, 28, 29, 34, 40–44, 47, 49, 52, 54, 55]. A standard graph index navigates the high-dimensional space by routing through proximity-based neighbor connections until converging

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY Query Text

Trovato et al.

Query Image

Query Filters

flooded streets

Time Interval : [T1,T2] Location: Inside Polygon A But Outside Circle B

Time Window April 1st-4th,2026 April 2026

Map & Results

April 1st-4th,2026 April

Spatial Region

Area A

k-Most Similar Embeddings

Table 1: Comparison of CubeGraph with existing filtered vector search paradigms. Performance measures overall accuracy and query efficiency under complex spatial constraints. Compact indicates whether the method avoids the index size explosion when handling multi-dimensional spatial filters. Connectivity captures the ability to maintain a unified, well-connected graph during search, avoiding fragmentation. Flexibility assesses support for arbitrary spatio-temporal filter shapes (e.g., polygons, irregular regions). Feature

Flood Impact Zone

Time Match

Area B (Exclusion Zone)

CubeGraph (Our)

PostFiltering

ACORN

Tree-Graph

★★★ ✓ ✓ ✓

★ ✓ ✓ ✓

★ ✓ ✓ ×

★★ × × ×

Time Match in [T1,T2] T1

T2

Figure 1: Motivating examples for hybrid vector similarity search with spatio-temporal filters. Each data object is represented by a high-dimensional vector embedding x𝑖 and associated with spatiotemporal metadata s𝑖 (e.g., geolocation and timestamp). (1) Urban event retrieval: a city management platform stores geo-tagged reports, images, and videos. Given a query vector q (e.g., flooded streets) and a spatio-temporal filter 𝜙, the task is to retrieve the top-𝑘 most similar objects satisfying 𝜙 (s𝑖 ) = 1. (2) Regional multimedia retrieval: a multimedia database stores geo-tagged images and videos. Given a query image q and a complex polygonal filter 𝜙, the system must return the top-𝑘 nearest neighbors within the specified spatiotemporal constraints.

on the 𝑘-nearest neighbors of query. Early execution paradigms, namely PreFiltering and PostFiltering, leave the underlying graph topology unchanged but modify the traversal logic. PreFiltering prunes nodes failing the predicate during traversal, which severely degrades graph connectivity and search accuracy under low filter selectivity. Conversely, PostFiltering traverses the graph ignoring the filter and verifies predicates post-hoc, leading to massive redundant distance computations and degraded efficiency. Challenge. To overcome the limitations of single-graph paradigms, state-of-the-art methods adopt a decoupled architecture, nesting multiple vector graphs within a low-dimensional spatial index. For instance, to handle 1D metadata (e.g., a time window), methods like WindowFilter [8], iRange [44], ESG [47], and WoW [40] build segment-tree-like structures where each tree node maintains a separate graph index. Consequently, answering a range filter query introduces an 𝑂 (log 𝑁 ) multiplicative overhead to the query execution time, alongside an 𝑂 (𝑁 log 𝑁 ) space complexity burden. In spatio-temporal scenarios, metadata dimensionality inherently exceeds 1D (e.g., 2D geolocation plus a 1D timestamp). Furthermore, spatial filters are rarely regular rectangles; they are often complex polygons or circles. To handle multi-dimensional metadata, a straightforward extension is to organize graph indices using multi-dimensional trees, such as R-trees or KD-trees [33, 51]. During query execution, the engine traverses the tree and invokes the graph indices attached to the overlapping tree nodes, subsequently merging the results [33]. √ However, even with only 2D metadata, a KD-tree requires 𝑂 ( 𝑁 ) tree nodes to reconstruct a given 2D rectangular filter. This architectural decoupling forces the query engine to invoke a massive number of disjoint graph subqueries. This subquery explosion destroys the global routing connectivity of the vector space, severely limiting the search performance, flexibility, and scalability of existing tree-graph methods.

Performance Compact Connectivity Flexibility

Our Idea. In this paper, we propose CubeGraph, a novel index structure and search paradigm designed to efficiently process hybrid queries with arbitrary spatio-temporal filters. Our fundamental insight is that the graph navigation property can be preserved across multi-dimensional boundaries if the underlying index bounds the number of search domains and supports dynamic connectivity. To this end, CubeGraph constructs a hierarchical grid over the spatiotemporal metadata space, mapping data points into localized, modular cube indices. By leveraging multiple levels of spatial granularity, the hierarchical grid guarantees that the number of involved graph indices is tightly controlled, effectively eliminating the exponential subquery explosion inherent to KD-tree or R-tree-based methods. Crucially, rather than treating these cubes as isolated search domains, CubeGraph introduces a lightweight, on-the-fly graph stitching mechanism. During query execution, as the search algorithm identifies the bounded set of cubes intersecting the query filter, it dynamically links the nodes to adjacent cubes, achieving a merged graph index. This creates a unified, query-specific routing graph in real-time. This dynamic integration avoids the massive redundant distance computations of PostFiltering, the graph disconnection issues of PreFiltering, and the traversal overhead of decoupled tree-graph architectures. Contributions. We summarize our main contributions as follows: Problem Analysis. We conduct an in-depth analysis of vector similarity search under complex spatio-temporal constraints. We identify that the multi-dimensionality of metadata and the geometric complexity of query filters lead to a subquery explosion in existing decoupled architectures, acting as the primary bottleneck for scalability and flexibility. The CubeGraph Framework. Based on the insight that dynamically stitched sub-graphs can achieve routing performance comparable to a monolithic index, we propose CubeGraph. This hierarchical grid index framework natively supports complex spatial query filters, offering high query execution efficiency while maintaining a strictly bounded index space overhead. Efficient Query Processing Strategies. We design two optimized query execution strategies: a predetermined cube search for simple boundaries, and an on-the-fly merged search for complex, irregular geometries. This adaptive approach guarantees a bounded search space and ensures high throughput across diverse spatial filters.

CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data

Extensive Evaluation. We design a comprehensive suite of experiments utilizing real-world and synthetic datasets under diverse query workloads. Our evaluations demonstrate that CubeGraph achieves highly stable performance across varying spatial constraints, delivering up to a 5× speedup over state-of-the-art baselines. The code, datasets, and other artifacts are available at https: //github.com/mingyu-hkustgz/CubeGraph-demo.

2

Preliminary

In this section, we formally define the hybrid search problem over vector similarity and spatio-temporal metadata in § 2.1. Following the definitions, we review related work on existing solutions in § 2.2. Finally, we introduce the index merging techniques utilized within our framework in § 2.3.

2.1

Problem Definition

We first introduce the basic notations and then formally define the core problem studied in this paper. Definition of a Data Point. A data point is defined as a tuple 𝑜 = (x, s), where 𝑜 is a unique object identifier, x ∈ R𝑑 is its 𝑑-dimensional vector embedding, and s ∈ R𝑚 represents its 𝑚dimensional spatio-temporal metadata (e.g., longitude, latitude, timestamp). Definition of a Dataset. A dataset is a collection D = {(x𝑖 , s𝑖 )} comprising 𝑖 ∈ [1, 𝑁 ] data points. Definition of a Spatio-Temporal Filter. A spatio-temporal filter is a predicate 𝜙 : R𝑚 → {0, 1} defined over the metadata space. A data point 𝑜𝑖 satisfies 𝜙 if and only if 𝜙 (s𝑖 ) = 1. This filter can represent axis-aligned rectangles, complex polygons, temporal windows, or any arbitrary intersection and union of these constraints. Definition of Filtered Candidate Set Given a dataset D and a filter 𝜙, the filtered candidate set is defined as D𝜙 = {(x𝑖 , s𝑖 ) ∈ D | 𝜙 (s𝑖 ) = 1}. Hybrid AKNN Query Given a query vector q ∈ R𝑑 , a spatiotemporal filter 𝜙, and an integer 𝑘, a hybrid approximate 𝑘-nearest neighbor (AKNN) query returns a result set R ⊆ D𝜙 with |R| = 𝑘, such that the vectors in R are approximately the 𝑘 closest to q under Euclidean distance (or inner product) among all valid points in D𝜙 . Table 2 summarizes the key notations used throughout this paper.

2.2

Existing Solutions

We briefly review graph-based approximate nearest neighbor search (ANNS) methods and existing strategies for handling filters. Graph-based ANNS. Proximity graph methods represent the dataset as a graph 𝐺 = (𝑉 , 𝐸), where each node 𝑣 ∈ 𝑉 corresponds to a data point, and edges connect approximate nearest neighbors in the high-dimensional vector space. Query processing typically follows a greedy beam search: starting from a fixed entry node, the algorithm iteratively expands to the neighbors closest to q, terminating when a local minimum is reached. For example, HNSW [26] organizes nodes into a hierarchy of layers, achieving 𝑂 (𝑑 log 𝑁 ) query time with 𝑂 (𝑁 ) space complexity by perform edge occlusion.

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Table 2: Summary of Notations Notation

Description

D 𝑁 𝑑 𝑚 x𝑖 s𝑖 q 𝜙 𝑘 D𝜙

Dataset of 𝑁 data points Number of data points in the dataset Dimensionality of vector embeddings Dimensionality of spatio-temporal metadata Vector embedding of data point 𝑜𝑖 Spatio-temporal metadata of data point 𝑜𝑖 Query vector Spatio-temporal filter predicate Number of nearest neighbors to retrieve Filtered candidate set satisfying 𝜙

Subsequent work, such as NSG and tMNG, improved the occlusion strategy to further enhance efficiency [9, 16, 20, 24, 30]. Pre-filtering and Post-filtering. The straightforward method to incorporate a filter 𝜙 into graph search is Pre-filtering and Postfiltering [14]. PreFiltering actively skips nodes where 𝜙 (s𝑖 ) = 0 during graph traversal. However, when filter selectivity is low (i.e., |D𝜙 | < |D|), the effective routing subgraph becomes severely sparse and disconnected, leading to catastrophic recall degradation. Conversely, PostFiltering traverses the full graph, ignoring the filter, applying 𝜙 only to the final retrieved candidate set. While this preserves recall, it wastes massive computational resources calculating distances for unqualified nodes, becoming prohibitively slow when filter selectivity is high. Filtered Graph Index Methods. To overcome the limitations of naive filtering, several methods modify the graph structure to natively support predicates. Filtered-DiskANN [14] builds perlabel subgraphs and stitches them together, though it is primarily designed for categorical label filters. NHQ [35] constructs a hybrid graph encoding both vector proximity and attribute proximity edges, supporting structured and unstructured constraints. ACORN [29] augments HNSW with a dynamic neighbor expansion strategy during search to maintain connectivity under arbitrary predicates. However, these methods are primarily optimized for low-dimensional or categorical metadata and struggle to scale efficiently when confronted with multi-dimensional spatio-temporal filters, the critical gap we address in § 3.

2.3

Index Merging

Vector index merging is a critical technique with wide applications in distributed systems, disk-based solutions, and heterogeneous computing architectures [16, 54]. In scenarios where memory constraints prevent building a monolithic index from scratch across the entire dataset, systems must rely on constructing smaller subindices. Index merging techniques enable the consolidation of these pre-built sub-indices to achieve near-optimal search performance. However, naively querying a large number of disjoint sub-indices significantly degrades search efficiency. To address this, overlapping-based methods, such as those used in DiskANN, force data points to be assigned to multiple partitions to maintain connectivity. More recent methods like FGIM [1] utilize an enhanced NN-Descent algorithm for fast index merging. Similarly, RNSM [18] identifies the nearest neighbors of partitioned data

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

in other partitions—a crucial factor in determining the quality of the merged index. It also greedily selects pivots and reuses their search results to accelerate the merging process. Our proposed framework leverages a nearest-neighbor-based index merging approach [18], which supports highly flexible merge operations while maintaining a low computational merge cost.

3

Problem Analysis

In this section, we analyze the inherent limitations of existing treegraph hybrid methods for spatio-temporal filtered approximate nearest neighbor search (ANNS) and motivate the design of our proposed framework, CubeGraph . 1D Range Filter Methods and Their Limitations. When the metadata is a scalar (e.g., a timestamp) and the filter is an interval [𝑙, 𝑟 ], state-of-the-art methods such as SeRF [55], WindowFilter [8], iRange [44], ESG [47], and WoW [40] organize graph indices using a compressed index or segment-tree-like structure. Each tree node covers a contiguous interval of the sorted metadata axis, and a query [𝑙, 𝑟 ] is decomposed into 𝑂 (log 𝑁 ) canonical nodes. The subgraph of each canonical node is searched independently, and the results are subsequently merged. However, this architecture incurs an 𝑂 (𝑁 log 𝑁 ) space complexity (as each point is replicated across 𝑂 (log 𝑁 ) nodes) and requires 𝑂 (𝑘 sub · log 𝑁 ) graph searches per query, where 𝑘 sub is the search budget allocated per sub-graph. Observation 1. For 1D range filters, tree-graph methods incur an 𝑂 (log 𝑁 ) multiplicative overhead in both storage space and query execution cost compared to a single monolithic graph index. Multi-Dimensional Spatio-Temporal Filters. When the metadata is 𝑑-dimensional (e.g., a 2D geolocation combined with a timestamp yields 𝑑 = 3), a natural extension is to organize the sub-graph indices using a multi-dimensional spatial tree, such as an R-tree [6] or KD-tree [32]. A spatial query filter 𝜙 (e.g., a rectangle or polygon) is processed by: (1) traversing the tree to identify all leaf nodes overlapping with 𝜙; (2) executing a graph search on the sub-index of each overlapping leaf; and (3) merging the retrieved results. A fundamental result from computational geometry establishes that the number of KD-tree nodes overlapping a 𝑑-dimensional orthogonal range query is Θ(𝑁 1−1/𝑑 ) in the worst case. Observation 2. For a 2D spatial filter, a KD-tree-based approach √ requires Θ( 𝑁 ) sub-index invocations per query; for 3D spatio-temporal filters, this complexity grows to Θ(𝑁 2/3 ). Given a dataset of 𝑁 = 106 points with 2D metadata, such a method invokes ∼ 103 independent sub-graph searches per query—each carrying its own beam-search initialization overhead—compared to a single graph search in pure ANNS. This subquery explosion renders multi-dimensional tree-graph methods fundamentally impractical at scale. Connectivity Degradation Under Filtering. Beyond the sheer volume of subqueries, these methods suffer from a secondary structural flaw: severe degradation of graph connectivity. When a filter 𝜙 exhibits high selectivity, retaining only a small fraction of the total nodes (|D𝜙 | ≪ 𝑁 ), the sub-graphs attached to individual tree nodes may contain very few qualifying points. Consequently, the greedy beam search within each isolated sub-graph becomes highly susceptible to getting trapped in local minima, leading to

Trovato et al.

a drastic drop in recall. This issue is orthogonal to the subquery explosion: even if the number of invoked sub-indices is manageable, the individual sub-graphs often become too sparse to navigate reliably. Observation 3. When filter selectivity is low (i.e., |D𝜙 |/𝑁 ≪ 1), tree-graph methods suffer from a compounding effect of (a) an excessively high subquery count and (b) poor intra-subgraph connectivity, both of which severely degrade recall and search efficiency. Motivation for CubeGraph. The aforementioned observations establish a clear design imperative: an ideal system must bound the number of sub-indices invoked per query to 𝑂 (1) regardless of the filter shape or dimensionality, while simultaneously preserving global graph connectivity across the filtered subset. CubeGraph addresses both challenges through two core innovations. First, a hierarchical grid index partitions the metadata space into cubes at multiple granularities, strictly bounding the number of cubes involved in any query to a small constant per level—independent of 𝑁 and the filter dimensionality. Second, a dynamic graph merging mechanism fuses the graphs of adjacent cubes on the fly during query execution. This creates a unified routing graph that preserves the navigability and connectivity of the original proximity graph, even under highly restrictive filters. These two components are detailed in § 4.

4

Methodology

In this section, we present the CubeGraph framework in detail. We first introduce the hierarchical grid structure in § 4.1. We then describe index construction in § 4.2 and query processing in § 4.3.

4.1

CubeGraph Framework

Framework Overview. Fig. 2 illustrates the CubeGraph framework. The hierarchical grid structure partitions the 𝑚-dimensional metadata space into multiple levels of granularity. At level ℓ, the space is divided into 𝑔ℓ uniform cubes. Each data point is assigned to exactly one cube per level based on its metadata s. For each cube, we build a local graph index on the vectors of points in that cube. During query processing, given a filter 𝜙, we identify all cubes at each level that intersect 𝜙. For adjacent intersecting cubes, we dynamically add cross-links to adjacent cubes, effectively merging the local graphs into a unified search graph G ∗ . This on-the-fly merging preserves the navigability of the graph across cube boundaries while keeping the search space bounded by the filter spatial extent.

4.2

Index Construction

The construction of CubeGraph proceeds in two phases: (1) building the hierarchical grid and local graph indices(e.g., HNSW), and (2) adding cross-cube edges to connect adjacent cubes. This twophase approach enables parallel construction of local indices while maintaining global connectivity through carefully placed inter-cube links. Phase 1: Hierarchical Grid and Local Index Construction. Algorithm 1 presents the hierarchical grid construction procedure. Given a dataset D with 𝑁 points, we first load the metadata and

CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Index Construction

Query Process Complex Spatial&Temporal Filter

2D CubeGraph Hierarchy Layer 1

Cross Cube Edges

Layer 2

Metadata-based Graph Index Per-Cube

Rectangle Filter

Composite Filter Radius Filter (Rectangle - Circle)

2x2 Metadata + Determines Relevant Cubes

4x4 Metadata Layer h Level L: 2L x 2L Cubes

Cross Edge Link Adjacent Cubes 3D CubeGraph Hierarchy

On-the-Fly Query Routing Cross Cube Edge Enable (Even Point is Filtered)

3D Cross Link Adjacent Cubes: 6 for Regular 3 for Corner Cube

Entry

2x2x2 Metadata Query

4x4x4 Metadata

Layer 1

Layer 2

Cross Cube Edge Disable (No-Overlap Cubes)

Vector Similarity-based Route Search

Figure 2: Framework of CubeGraph. The hierarchical grid partitions the metadata space into multiple levels of cubes. At each level, data points are assigned to their containing cubes and local graph indexes are built. During query processing, cubes intersecting the filter are identified, and their local graphs are merged on-the-fly via cross-cube connections (dashed lines), forming a unified search graph. Note, we only plot the cross-cube edges of the boundary nodes for simplicity; the CubeGraph index requires that each node link cross-cube edges to the adjacent cube nearest neighbors, whether on the boundary of meta space or not.

Algorithm 1: Hierarchical Grid Construction Input: Dataset D, num_layers 𝐿, 𝑀, 𝑒 𝑓c Output: Multi-layer cube index 1 Load metadata and compute global bounding box B; 2 for ℓ = 0 to 𝐿 − 1 do 3 Compute cube granularity: 𝑔ℓ = 2ℓ+1 per dimension; 4 Split (𝑔ℓ )𝑚 cubes with side length 𝑤 ℓ = |B|/𝑔ℓ ; 5 for each data point (x𝑖 , s𝑖 ) ∈ D parallel do 6 Compute cube ID: 𝑐𝑖 Assign point 𝑖 to cube 𝑐𝑖 ; 7 8

for each non-empty cube 𝑐 parallel do Build index on points in 𝑐 with parameters 𝑀, 𝑒 𝑓c ;

compute the global bounding box B spanning all metadata vectors (lines 1-2). For each layer ℓ ∈ [0, 𝐿 − 1], we partition the metadata space into (2ℓ+1 )𝑚 uniform cubes, where 𝑚 is the metadata dimensionality (line 4). Each cube has side length 𝑤 ℓ = |B|/2ℓ+1 per dimension. We assign each data point to its containing cube based on its metadata coordinates (lines 5-7). For each non-empty cube, we construct a local graph index using the standard construction algorithm with parameters 𝑀 (maximum degree) and 𝑒 𝑓c (construction beam width) (lines 8-10). Crucially, these local index constructions are independent and can be parallelized across all cubes using OpenMP, significantly reducing wall-clock construction time. After building local indices, we construct the adjacency list for each cube, identifying its 2𝑚 face-adjacent neighbors (line 11). Two cubes are face-adjacent if they share an (𝑚 − 1)-dimensional face, differing by exactly one unit in exactly one dimension. This adjacency structure is essential for the subsequent cross-cube edge addition phase.

Algorithm 2: Cross-Cube Edge Addition Input: Layer configuration, adjacent cube IDs, 𝑀cross , 𝑒 𝑓cross Output: Augmented Graph Indices with Cross-cube Edges 1 for each cube 𝑐 at each layer ℓ do 2 for each point 𝑝 in cube 𝑐 parallel do 3 for each adjacent cube 𝑐 adj of 𝑐 do 4 Set 𝑝 as query; 5 N ← Search AKNN of 𝑝 in 𝑐 adj with 𝑒 𝑓cross ; 6 Select top 𝑀cross nearest neighbors from N ; 7 Add selected neighbors as cross-cube edges to 𝑝;

Phase 2: Cross-Cube Edge Addition. Algorithm 2 describes the cross-cube edge addition procedure. For each cube and each of its adjacent cubes, we establish connectivity by adding cross-cube edges from each node to its adjacent cubes. Specifically, for each point 𝑝 in cube 𝑐, we search from the entry point of each adjacent cube 𝑐 adj using a beam search with width 𝑒 𝑓cross (lines 3-5). We then select the top 𝑀cross nearest neighbors from 𝑐 adj and add them as cross-cube edges to point 𝑝 (line 6). These cross-cube edges are stored separately from the intra-cube edges in the graph structure, enabling efficient identification during query processing. Design Rationale. The hierarchical structure with 𝐿 layers enables CubeGraph to adapt to filters of varying spatial extents. Coarse layers (small ℓ) handle large filters efficiently with fewer, larger cubes, while fine layers (large ℓ) provide precise filtering for small spatial regions. Cross-cube edges are essential for maintaining graph connectivity: without them, the search would be confined to a single cube, severely limiting recall. By connecting nodes of adjacent cubes, we create seamless routing paths that span multiple cubes

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Trovato et al.

Sequential Memory Access for Graph and Metadata

Intra-Cube Neighbors

Cross-Cube Neighbors

Id

MetaData

Obtain by Metadata Dim Default 2 Edges per Dim Random Read Per-Single Vector

Base Vectors

Graph Indices at Same Layer

Figure 3: Memory layout of CubeGraph. Each node in CubeGraph utilizes an identical memory layout. Unlike standard implementations such as hnswlib, our vector data is managed separately because the total number of nodes scales by a factor of 𝐿 across 𝐿 layers. Within any specific layer, a node maintains both intra-cube neighbors and cross-cube neighbors, the latter being determined by the metadata dimensionality. Additionally, aligning the graph structure with the metadata enables highly efficient filter evaluation during node traversal.

Algorithm 3: Predetermined Cube Search Input: Query q, filter 𝜙, 𝑘, layer ℓ, search budget 𝑒 𝑓 Output: Top-𝑘 results satisfying 𝜙 1 𝑅 ← ∅; 2 Identify cube list C = {𝑐 1 , . . . , 𝑐𝑚 } intersecting 𝜙; 3 Build adjacency bitmap: 𝐵 [𝑐] = 1 for all 𝑐 ∈ C; 4 Initialize priority queue 𝑄 with entry points in C; 5 while top result in 𝑄 better than 𝑘-th result in 𝑅 do 6 𝑝 ← pop closest candidate from 𝑄; 7 for each neighbor 𝑢 of 𝑝 (intra-cube or cross-cube) do 8 if 𝑢 is cross-cube edge and 𝐵 [𝑢.cube] = 0 then 9 continue; 10 11 12 13 14

while preserving the navigability properties of the underlying graph index. Fig. 2 illustrates how cross-cube edges (dashed lines) bridge local graphs during query processing. We also improve the memory layout for better search efficiency as detail in Fig. 3.

4.3

Query Processing

Query processing in CubeGraph consists of two stages: (1) layer selection and cube identification, and (2) graph search with filtering. We present two query processing strategies tailored to different filter characteristics: a predetermined cube search for simple filters and an on-the-fly merged search for complex filters. Layer Selection Strategy. Given a filter 𝜙, we first select the appropriate layer ℓ ∗ for query execution. The key insight is to match the filter’s characteristic length with the cube width at each layer. For an axis-aligned bounding box filter or convex hull, the characteristic length is the maximum side length; for a circular filter, it is the diameter. In practice, we select the layer ℓ ∗ by comparing the filter bounding box dimensions with the cube widths at each layer, choosing the layer where 𝑤 ℓ is closest to the filter characteristic length. More specifically, we find the layer with the largest cube width less than the characteristic length 𝑟 by binary search as the query layer where 𝑟 /2 < 𝑤𝑙 < 𝑟 . Cube Identification. After selecting layer ℓ ∗ , we identify all cubes intersecting the filter 𝜙. For simple filters (axis-aligned bounding boxes), we compute the cube IDs directly by discretizing the min/max bounds of filter. For complex filters (circles, polygons), we use a conservative approach: compute the filter’s bounding box, identify all cubes intersecting this bounding box during graph search, then apply the filter predicate during search. Fig. 2 illustrates cube identification for different filter shapes. Predetermined Cube Search. Algorithm 3 presents the predetermined cube search strategy, suitable for simple filters where all intersecting cubes can be identified upfront. Given a query vector q, filter 𝜙, parameter 𝑘 and search effort 𝑒 𝑓 , we first identify the set C = {𝑐 1, 𝑐 2, . . . , 𝑐𝑚 } of cubes intersecting 𝜙 at the selected layer (line 2). We construct an adjacency bitmap for efficient neighbor checking: for each cube in C, we mark it as searchable in a bitmap

if 𝜙 (s𝑢 ) = 1 then add 𝑢 to result set 𝑅; Add 𝑢 to 𝑄 if not visited; keep top 𝑒 𝑓 results in 𝑅; return top-𝑘 from 𝑅;

(line 3). We initialize the search by adding the entry points of all cubes in C to the candidate queue (line 4). During beam search, we follow intra-cube edges normally, but only follow cross-cube edges to cubes in C (lines 5-9). The filter predicate 𝜙 is applied to each candidate to ensure only qualifying points are returned (line 8). This approach minimizes overhead by pre-computing the search domain and avoiding dynamic cube discovery. On-the-Fly Merged Search. Algorithm 4 presents the on-the-fly merged search strategy, designed for complex filters where relevant cubes are discovered dynamically during search. Given a query vector q, filter 𝜙, an entry cube 𝑐 0 , and search budget 𝑒 𝑓 , we initialize a dynamic cube bitmap 𝐵 with only 𝑐 0 marked as searchable (lines 1-2). We perform beam search with the same termination condition as predetermined search: the search continues while the top candidate in the priority queue 𝑄 is better than the 𝑘-th result in 𝑅 (line 3). For each neighbor 𝑛 explored during beam search, we first check if its cube is marked as searchable in 𝐵 (line 4). If the neighbor satisfies the filter 𝜙, we mark its cube as searchable by setting 𝐵 [𝑛.cube] = 1 and add it to the result set 𝑅 (lines 5-6). We maintain the top 𝑒 𝑓 results in 𝑅 to control search budget (line 8). This dynamic discovery mechanism allows the search to naturally expand into relevant cubes as qualifying points are encountered, without requiring upfront computation of all intersecting cubes. This approach is particularly effective for complex filter shapes (circles, polygons) where geometric intersection tests are expensive. Comparison and Trade-offs. Table 3 compares the two query processing approaches. Predetermined cube search is optimal for simple filters (axis-aligned bounding boxes) where cube intersection can be computed efficiently. It has lower per-candidate overhead since the search domain is fixed. On-the-fly merged search excels for complex filters (circles, polygons, irregular regions) where geometric intersection tests are expensive or the filter shape is not known upfront. The dynamic discovery adds overhead (checking filter predicate and updating bitmap), but eliminates the cost of pre-computing all intersecting cubes. In practice, we select the

CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data

Algorithm 4: On-the-Fly Merged Search Input: Query q, filter 𝜙, 𝑘, entry cube 𝑐 0 , search budget 𝑒 𝑓 Output: Top-𝑘 results satisfying 𝜙 1 𝑅 ← ∅; 2 Initialize dynamic cube bitmap 𝐵 with 𝐵 [𝑐 0 ] = 1; 3 Initialize priority queue 𝑄 with entry point of 𝑐 0 ; 4 while top result in 𝑄 better than 𝑘-th result in 𝑅 do 5 𝑝 ← pop closest candidate from 𝑄; 6 for each neighbor 𝑛 of 𝑝 (intra-cube or cross-cube) do 7 if 𝐵 [𝑛.cube] = 0 then 8 continue// Skip non-searchable cubes if 𝜙 (s𝑛 ) = 1 then 𝐵 [𝑛.cube] ← 1// Mark cube as searchable Add 𝑛 to result set 𝑅;

9 10 11 12

Add 𝑛 to 𝑄 if not visited; keep top 𝑒 𝑓 results in 𝑅;

13 14

return top-𝑘 from 𝑅;

(removing from neighbor lists and repairing connections) costs 𝑂 (𝐿 · 𝑀 2 ). Cross-Cube Edge Maintenance. Insertions and deletions may degrade cross-cube connectivity over time. To maintain index quality, we periodically recompute cross-cube edges for affected nodes. We trigger recomputation when: (1) batch insertions exceed a threshold (e.g., 1% of cube size), or (2) deletion rate exceeds a threshold. For each affected cube, we identify affected nodes and recompute their cross-cube edges using the procedure from Algorithm 2. This maintenance is performed asynchronously to avoid blocking queries.

5

Analysis and Extension

In this section, we provide a theoretical analysis of CubeGraph using the framework of characteristic length, cube length, and elastic factor [49]. We analyze space and time complexity under the uniform distribution assumption, and discuss extensions to the CubeGraph framework for user-specific indexes.

5.1

Table 3: Comparison of Query Processing Approaches Aspect

Predetermined

On-the-Fly

Filter Type Cube Discovery Overhead Flexibility Use Case

Simple (boxes) Pre-computed Lower Limited Known Cubes

Complex (circles, polygons) Dynamic Medium High Unknown Intersection

strategy based on filter complexity: use a predetermined search for bounding boxes and an on-the-fly search for other shapes.

4.4

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Dynamic Updates

CubeGraph supports dynamic insertions and deletions while maintaining index quality and query performance. We describe the update procedures and analyze their complexity. Point Insertion. When a new data point (𝑜, x, s) arrives, we insert it into the index as follows. First, we compute the cube ID for the point at each layer ℓ ∈ [0, 𝐿 − 1] based on its metadata s (same computation as in construction). For each layer, we insert the point into the local graph index of its containing cube using the standard graph insertion algorithm, which connects the new point to its 𝑀 nearest neighbors. We add cross-cube edges for the new point by searching from the entry points of adjacent cubes and connecting to the top 𝑀cross nearest neighbors in each adjacent cube. The insertion complexity is 𝑂 (𝐿 · log 𝑁 + 𝐿 · 𝑚 · 𝑀cross · log 𝑁 ), dominated by graph index insertion and cross-edge addition. Point Deletion. We adopt a lazy deletion strategy for efficiency. When a point is deleted, we mark it as invalid in all containing cubes across all layers. During query processing, we skip invalidated points when they appear in the candidate queue. Periodically (e.g., when the deletion rate exceeds a threshold), we rebuild affected cube indices to reclaim memory and maintain search efficiency. Lazy deletion has 𝑂 (𝐿) complexity for marking, while eager deletion

Analysis

Uniform Distribution Model. We assume the metadata space S = [0, 𝑆]𝑚 is an 𝑚-dimensional hypercube. Given a dataset D of 𝑁 points, we assume the metadata vectors s𝑖 are independently and uniformly distributed in S. The hierarchical grid has 𝐿 levels with granularity parameter 𝑔, where level ℓ partitions S into 𝑔ℓ cubes. We denote the cube width (side length) at layer ℓ as 𝑤 ℓ = 𝑆/𝑔ℓ . Characteristic Length and Optimal Layer Selection. For a given filter 𝜙, we define its characteristic length 𝑟 as follows: for an axis-aligned bounding box or convex hull, 𝑟 = 𝑟 max is the maximum side length; for a circular or spherical filter, 𝑟 is the diameter. For rectangular filters, we also define 𝑟 min as the minimum side length and the aspect ratio 𝛼 = 𝑟 max /𝑟 min ≥ 1. The characteristic length captures the spatial extent of the filter in the metadata space, while the aspect ratio characterizes the shape of the filter (𝛼 = 1 for squares, 𝛼 > 1 for non-square rectangles). Proposition 1. For a filter 𝜙 with characteristic length 𝑟 , the optimal layer ℓ ∗ satisfies 𝑤 ℓ ∗ ≈ 𝑟 , where 𝑤 ℓ = 𝑆/𝑔ℓ is the cube width at layer ℓ. Specifically, selecting ℓ ∗ such that 𝑟 /2 < 𝑤 ℓ ∗ < 𝑟 guarantees at most 2𝑚 intersecting cubes. We analyze why 𝑤 ℓ ∗ ≈ 𝑟 is optimal in Appendix A.1 Corollary 1. Under optimal layer selection with 𝑤 ℓ ∗ ≈ 𝑟 max , the number of cubes intersecting a filter 𝜙 is 𝑂 (𝛼), where 𝛼 = 𝑟 max /𝑟 min is the aspect ratio. For filters with bounded aspect ratio (𝛼 = 𝑂 (1)), this gives 𝑂 (1) cubes, specifically at most 2𝑚 ·𝛼 cubes. For high aspect ratio filters (𝛼 ≫ 1), the cube count grows linearly with 𝛼. This bound is critical for understanding when CubeGraph maintains high graph search performance. Elastic Factor Analysis. We adapt the elastic factor concept from [49] to characterize query efficiency in CubeGraph . The elastic factor measures the overlap between the filtered candidate set and the searched set. Definition 5.1 (Elastic Factor for CubeGraph). Given a dataset D, a query (q, 𝜙), and the merged graph G ∗ at layer ℓ, the elastic factor

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

is defined as: |D𝜙 | |{(𝑜, x, s) ∈ D | 𝜙 (s) = 1}| ⋃︁ 𝑒 (D𝜙 , G ∗ ) = = |G ∗ | |{(𝑜, x, s) ∈ D | s ∈ C}| where C is the set of cubes intersecting 𝜙 at layer ℓ. The elastic factor 𝑒 ∈ (0, 1] measures what fraction of the searched points actually satisfy the filter. Under uniform distribution, the elastic factor can be approximated by the volume ratio: 𝑒≈

Vol(𝜙) ⋃︁ Vol( C)

where Vol(·) denotes the 𝑚-dimensional volume. Lemma 1. Under uniform distribution with optimal layer selection (Proposition 1), where 𝑤 ℓ ∗ ≈ 𝑟 , the elastic factor is lower bounded by a constant that depends on the filter shape. For circular filters in 𝑚 dimensions, 𝑒 ≥ 𝜋 𝑚/2 /(2𝑚 · Γ(𝑚/2 + 1)), where Γ is the gamma function. Proof. At the optimal layer, the filter with characteristic length 𝑚 𝑟 intersects at most 2𝑚 cubes, each with volume 𝑤 𝑚 ℓ ∗ ≈ 𝑟 . The 𝑚 𝑚 union of cubes has volume at most 2 · 𝑟 . For a circular filter with diameter 𝑟 , the volume is 𝜋 𝑚/2 · (𝑟 /2)𝑚 /Γ(𝑚/2 + 1). Therefore, 𝑒 ≥ 𝜋 𝑚/2 · (𝑟 /2)𝑚 /(Γ(𝑚/2 + 1) · 2𝑚 · 𝑟 𝑚 ) = 𝜋 𝑚/2 /(2𝑚 · Γ(𝑚/2 + 1)). For 𝑚 = 2, this gives 𝑒 ≥ 𝜋/16 ≈ 0.196; for 𝑚 = 3, 𝑒 ≥ 𝜋/(48) ≈ 0.065. □ Example 1. Consider a 2D circular filter with radius 𝑟 /2 (diameter 𝑟 ) in a metadata space of side length 𝑆 = 100. With optimal layer selection where 𝑤 ℓ ∗ ≈ 𝑟 , the filter intersects at most 4 cubes. The circle has area 𝜋 (𝑟 /2) 2 = 𝜋𝑟 2 /4, and the union of 4 cubes has area at most 4𝑟 2 . The elastic factor is 𝑒 ≈ 𝜋𝑟 2 /4/(4𝑟 2 ) = 𝜋/16 ≈ 0.196. In practice, the elastic factor is often higher because the filter may not span all 4 cubes fully. The elastic factor degrades quadratically with aspect ratio: for rectangles with 𝛼 = 𝑟 max /𝑟 min , we have 𝑒 ≈ 1/(2𝛼 2 ). See Appendix A.5 for detailed analysis of query performance degradation and Appendix A.8 for an example of high aspect ratio rectangles. Example 2. Consider a 2D rectangular filter with sides 100 × 10 (aspect ratio 𝛼 = 10) in a metadata space of side length 𝑆 = 1000. With optimal layer selection where 𝑤 ℓ ≈ 100, the rectangle intersects approximately 20 cubes (2 along the short dimension, 10 along the long dimension). The rectangle has area 1000, and the union of 20 cubes has area approximately 20 × 1002 = 200,000. The elastic factor is 𝑒 ≈ 1000/200,000 = 0.005, which is much lower than the 𝜋/16 ≈ 0.196 bound for circular filters. This demonstrates why high aspect ratio filters lead to poor query performance in CubeGraph .

Trovato et al.

Proof. Each data point appears in exactly one cube at each of the 𝐿 layers. At each layer, the point maintains: (1) up to 𝑀 intra-cube edges to neighbors within the same cube, and (2) up to 2𝑚 · 𝑀cross cross-cube edges to neighbors in adjacent cubes (there are 2𝑚 adjacent cubes in an 𝑚-dimensional grid). Therefore, each point stores 𝑂 (𝑀 + 𝑚 · 𝑀cross ) edges per layer, yielding total space 𝑂 (𝑁 · 𝐿 · (𝑀 + 𝑚 · 𝑀cross )). □ Corollary 2. With constant 𝐿, 𝑀, 𝑚, and 𝑀cross , the space complexity is 𝑂 (𝑁 ), linear in the dataset size. See Appendix A.3 for the proof. Construction Time Complexity. We analyze the time complexity of index construction. Theorem 2. The construction time complexity of CubeGraph is 𝑂 (𝑁 · 𝐿 · log 𝑁 + 𝑁 · 𝐿 · 𝑚 · 𝑀cross · log 𝑁 ). Proof. Construction consists of two phases: (1) building local graph indices within each cube, and (2) adding cross-cube edges. For phase (1), each of the 𝑁 points is inserted into 𝐿 layers, with each insertion costing 𝑂 (log 𝑁 ) on average for graph-based indices like HNSW, yielding 𝑂 (𝑁 · 𝐿 · log 𝑁 ) time. For phase (2), each point at each layer requires searching in 2𝑚 adjacent cubes to establish cross-cube edges. Each search identifies 𝑀cross neighbors with cost 𝑂 (log 𝑁 ), yielding 𝑂 (𝑁 · 𝐿 · 2𝑚 · 𝑀cross · log 𝑁 ) = 𝑂 (𝑁 · 𝐿 · 𝑚 · 𝑀cross · log 𝑁 ) time. The total construction time is the sum of both phases. □ Remark. Recent studies [18] show that cross-cube links require only minimal search effort (𝑒 𝑓𝑐 = 30) compared to full graph construction (𝑒 𝑓𝑐 = 200). See Appendix A.4 for details. Query Time Complexity. We now analyze the query time complexity, which depends critically on the relationship between characteristic length 𝑟 , cube width 𝑤 ℓ , and elastic factor 𝑒. Theorem 3. Given a query (q, 𝜙) with characteristic length 𝑟 , selecting the optimal layer ℓ ∗ where 𝑤 ℓ ∗ ≈ 𝑟 (as in Proposition 1), if the elastic factor 𝑒 ≥ 𝑐 for some constant 𝑐 ∈ (0, 1], the expected query time to retrieve top-𝑘 results is 𝑂 (𝐶 + 𝑘/𝑐), where 𝐶 is the expected cost to locate the top-1 neighbor in the merged graph G ∗ . Corollary 3. Under optimal layer selection with elastic factor 𝑒 ≥ 𝑐, the query time of CubeGraph is 𝑂 (𝐶 + 𝑘/𝑐), which is independent of the dataset size 𝑁 and depends only on the filter geometry (through 𝑟 and 𝑒) and the graph structure (through 𝐶). Dynamic Update Complexity. We briefly analyze the complexity of dynamic updates.

Space Complexity. We analyze the space complexity of CubeGraph under uniform distribution.

Theorem 4. Point insertion has time complexity 𝑂 (𝐿 · log 𝑁 + 𝐿 · 𝑚 · 𝑀cross · log 𝑁 ). Lazy deletion has time complexity 𝑂 (𝐿) for marking points as invalid, while eager deletion costs 𝑂 (𝐿 · 𝑀 2 ) for removing points and repairing neighbor connections.

Theorem 1. Under uniform metadata distribution, the space complexity of CubeGraph is 𝑂 (𝑁 · 𝐿 · (𝑀 + 𝑚 · 𝑀cross )), where 𝑁 is the dataset size, 𝐿 is the number of hierarchy levels, 𝑀 is the maximum degree for intra-cube edges, 𝑚 is the metadata dimensionality, and 𝑀cross is the maximum degree for cross-cube edges per adjacent cube.

Proof. For insertion, each point is inserted into 𝐿 layers. At each layer, inserting into the local graph costs 𝑂 (log 𝑁 ), and establishing cross-cube edges to 2𝑚 adjacent cubes costs 𝑂 (𝑚 ·𝑀cross ·log 𝑁 ). For lazy deletion, we mark the point as invalid in all 𝐿 layers, costing 𝑂 (𝐿). For eager deletion, we remove the point from neighbor lists

CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Table 4: The Statistics of Datasets Dataset

Size

Dim

Query Size

Metadata

SIFT1M YFCC MSMARC10M Deep100M

1M ≈1M 10M 100M

128 512 1024 96

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

2D/3D/4D Uniform 2D/3D Geo 2D/3D/4D Uniform 2D/3D Uniform

Visualization of Metadata Distribution

and repair connections, which costs 𝑂 (𝑀 2 ) per layer due to the need to reconnect up to 𝑀 neighbors. □

5.2

Extension

Lazy Update Mechanism. When new data points arrive, we adopt a lazy update strategy to maintain efficiency. Instead of immediately rebuilding affected cube indexes, we maintain a pending insertion buffer for each cube. Periodically (e.g., when the buffer size exceeds a threshold), we merge the buffered points into the corresponding cube’s graph index. This approach avoids frequent index reconstructions while ensuring that recent insertions are eventually incorporated. Query-Driven Index Enhancement. For user-specific workloads with particular filter patterns, CubeGraph supports query-driven index enhancement. When a query filter 𝜙 frequently accesses a region with high point density, we may create a finer-grained grid partition for that region or add dedicated graph indexes at a specific level to improve search efficiency. This enhancement is triggered adaptively based on query workload characteristics.

6

Experiments

Our experiments evaluate CubeGraph across five dimensions: search efficiency compared to state-of-the-art filtered ANNS baselines; query performance under diverse filter shapes (rectangles, circles, polygons) and spatial distributions; the effectiveness of hierarchical grid partitioning in bounding merged index counts for scalability; the trade-offs between predetermined and on-the-fly graph merging strategies for different workloads.

6.1

Experimental Setup

Datasets. Table 4 summarizes the statistics of the datasets used in our experiments. We use the following standard ANN benchmarks: • SIFT1M [4]: 1M 128-dimensional SIFT descriptors with 10K queries. We generate synthetic 2D/3D/4D various distribution attributes in [0, 1]𝑚 for spatio-temporal filtering. • YFCC: 1M 512-dimensional CLIP embeddings extracted from Flickr images with real geolocation metadata (latitude/longitude) and timestamp (normalized). We use the first 1M vectors for our experiments. • MSMARC10M: 10M 1024-dimensional text embeddings from the MS MARCO passage ranking dataset. We generate synthetic 2D/3D/4D uniform attributes for filtered search evaluation. • Deep100M: 100M 96-dimensional vectors sampled from the Deep1B dataset [4]. We generate 2D/3D uniform spatial attributes to test scalability. Baselines. We compare against the following state-of-the-art methods:

Uniform

Clustered

Skewed

Normal

Hollow

Real

Figure 4: Distribution of Metadata Attributes Across Datasets.

• PostFiltering: HNSW with post-filtering, which applies the filter predicate after retrieving candidates from a standard HNSW index. • ACORN-𝛾: A method that constructs a dense graph index for the entire dataset. We use 𝛾 = 12 as recommended for filtered search. Evaluation Metrics. We evaluate the performance of our method using the following metrics: • Recall: For a given query, let 𝑅 be the set of the exact 𝑘-nearest neighbors (ground truth) and 𝐴 be the set of 𝑘 neighbors returned by the approximate search. Recall is defined as |𝑅 ∩ 𝐴|/𝑘. • Query Per Second (Qps): The number of queries processed per second. Note, all metrics are averaged over the entire query set for each dataset and filter configuration. Metadata Distribution. For SIFT and MSMARC10M, we generate synthetic metadata attributes uniformly distributed in [0, 1]𝑚 for 𝑚 = 2, 3, 4. For YFCC, we use real geolocation metadata (latitude/longitude) and timestamp. For Deep100M, we generate synthetic 2D/3D uniform spatial attributes to test scalability. Query Workloads. We design query workloads with varying filter shapes and sizes: • Axis-Aligned Bounding Boxes: Rectangular filters with varying aspect ratios. • Circles: Circular filters with varying radius. • Polygons: Irregular filters defined by random polygons with 3-5 vertices. • Compose: Complex filters formed by combining basic shapes (e.g., points inside a bounding box but outside a circle). Filter Ratios. We vary the filter ratio (the fraction of volume to the metaspace) from 0.01 to 0.10 to evaluate performance under different selectivity levels. If metadata is uniformly distributed, the filter ratio directly corresponds to the expected fraction of points satisfying the filter. For synthetic filters, we control the filter ratio by adjusting the size of the filter (e.g., side length for bounding boxes, radius for circles).

6.2

Experimental Results

Exp-1: Search Efficiency. Fig 5 compares CubeGraph against ACORN and PostFiltering across SIFT, MSMARC10M, and YFCC with varying 2D filter ratios (0.01–0.10). On SIFT, CubeGraph achieves up to 5,730 Qps at 92% recall—72× and 21× speedup over ACORN

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Trovato et al.

ACORN-𝛾

CubeGraph

102

103

90

95

100

Qps

103

102

102

102.5 85

103

Qps

Qps

Qps

103.5 103

PostFiltering

85

recall@20(%)

90

95

100

85

90

recall@20(%)

(a) SIFT 2D ratio 0.01

100

85

95

100

recall@20(%)

(c) SIFT 2D ratio 0.05

(d) SIFT 2D ratio 0.10

103

102

102 Qps

102

Qps

Qps

102

101

101

101 85

90

95

100

85

recall@20(%)

90

95

100

85

90

recall@20(%)

(e) MSMARC10M 2D ratio 0.01

95

100

(h) MSMARC10M 2D ratio 0.10

Qps

102

Qps

101

90

recall@20(%)

(g) MSMARC10M 2D ratio 0.05

102

Qps

85

100

recall@20(%)

(f) MSMARC10M 2D ratio 0.02

102

95

Qps

Qps

90

recall@20(%)

(b) SIFT 2D ratio 0.02

103

95

102

101 101 90

85

95

100

85

recall@20(%)

90

95

100

85

90

recall@20(%)

(i) YFCC 2D ratio 0.01

95

100

85

90

recall@20(%)

(j) YFCC 2D ratio 0.02

95

100

recall@20(%)

(k) YFCC 2D ratio 0.05

(l) YFCC 2D ratio 0.10

Figure 5: Search efficiency comparison across different datasets with Bounding Boxes Filter (recall@20 vs. Qps). CubeGraph-Cube

PostFiltering

103

103 Qps

Qps

Qps

Qps

103 103

102

102

102 85

90

95

85

100

90

recall@20(%)

95

100

96

recall@20(%)

(a) SIFT 3D ratio 0.02

98

100

90

(b) SIFT 3D ratio 0.05

(c) SIFT 4D ratio 0.02

96

98

100

(d) SIFT 4D ratio 0.05 102 Qps

Qps

Qps

Qps

102

94

recall@20(%)

102 102

92

recall@20(%)

101

101

101 85

90

95

100

85

90

recall@20(%)

95

100

85

recall@20(%)

90

95

100

85

90

95

100

recall@20(%)

recall@20(%)

(e) MSMARC10M 3D ratio 0.02 (f) MSMARC10M 3D ratio 0.05 (g) MSMARC10M 4D ratio 0.02 (h) MSMARC10M 4D ratio 0.05 103

103

101

102

Qps

102

Qps

Qps

Qps

102 102

101 101 85

90

95

100

85

90

recall@20(%)

95

100

85

recall@20(%)

(i) YFCC 3D ratio 0.02

90

95

100

85

90

recall@20(%)

(j) YFCC 3D ratio 0.05

95

100

recall@20(%)

(k) YFCC 3D ratio 0.01

(l) YFCC 3D ratio 0.10

Figure 6: Search efficiency comparison across different dimensions (3D/4D) with Bounding Boxes filter (recall@20 vs. Qps). CubeGraph-Cube CubeGraph-Polygon-5

CubeGraph-Polygon-3 CubeGraph-Radius

CubeGraph-Polygon-4 CubeGraph-Compose

103.5

103.5

103

103

103

Qps

Qps

Qps

Qps

103.5 103

102.5 102.5

70

80

90

recall@20(%)

(a) SIFT 2D (ratio 0.05)

100

85

90

95

recall@20(%)

(b) SIFT 2D (ratio 0.10)

100

85

90

95

recall@20(%)

(c) SIFT 3D (ratio 0.10)

100

85

90

95

recall@20(%)

(d) SIFT 4D (ratio 0.10)

Figure 7: Comparison of Polygon and Radius filters vs Cube filter on SIFT (recall@20 vs. Qps).

100

CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Table 5: Indexing Time (seconds)

SIFT

CubeGraph PostFiltering ACORN-𝛾

88 47 49

YFCC 251 50 133

MSMARC10M 4767 647 3572

Table 6: Index Size (MB)

Deep100M Dataset CubeGraph PostFiltering ACORN-𝛾

16224 2467 10484

SIFT

YFCC

MSMARC10M

Deep100M

489 172*6 172 363

1956 172*6 172 360

39062 1716*6 1716 3638

37004 17166*6 17166 36724

Cube-merge4

Fly-Merge4 1,500 Qps

1,500 Qps

and PostFiltering, respectively. On MSMARC10M, CubeGraph sustains 144 Qps at 99%+ recall while PostFiltering drops to 15 Qps, with ACORN unable to exceed 88% recall. YFCC shows the largest gap: CubeGraph delivers 100× speedup over PostFiltering at comparable recall, while ACORN saturates at only 24% recall. Across all datasets, CubeGraph achieves 1–2 orders of magnitude higher throughput than baselines.

1,000

500

500 90

1,000

92

94

96

98

100

90

92

recall@20(%)

94

96

98

100

recall@100(%)

Exp-2: Multi-Dimensional Filters. We evaluate CubeGraph on queries with varying attribute dimensions (2D, 3D, 4D). Fig 6 presents the performance on SIFT with a box filter at different filter ratios. With 2D attributes and 10% filter ratio, CubeGraph achieves 2,767 Qps at 88% recall@20 and 652 Qps at 99.6% recall. Increasing dimensionality to 3D provides finer spatial filtering granularity, achieving 1,469 Qps at 97% recall. At 4D, CubeGraph maintains 515 Qps at 98% recall, demonstrating that higher dimensions slightly reduce throughput due to increased intersection complexity but still deliver excellent performance. These results confirm that CubeGraph efficiently handles multi-dimensional spatio-temporal filters.

Figure 8: Recall vs Qps comparison on SIFT dataset (𝑘 = 20: left, 𝑘 = 100: right). We compare hnsw-cube-merge4 and hnsw-fly-merge4 on the SIFT dataset.

Exp-3: Handling Complex Filter. Fig 7 evaluates CubeGraph with various filter shapes: box, polygon (3/4/5 vertices), radius, and composed filters on SIFT. At 2D ratio of 0.05, Polygon-5 achieves 1,978 Qps at 96% recall, which is 1.8× higher than Cube. This demonstrates that irregular filter shapes can reduce intersection overhead. Radius filter achieves 1,136 Qps at 99.7% recall, while the composed filter (Inside Nox but not in Radius) reaches 1,191 Qps at 99.5% recall. At 2D ratio of 0.10, Radius maintains 1,058 Qps at 99.5% recall with Cube at 652 Qps. In 3D, Radius achieves 687 Qps at 99.7% recall versus Cube 374 Qps—1.8× speedup. In 4D, both shapes perform comparably (209 vs 194 Qps at 99.5% recall). These results confirm CubeGraph adapts efficiently to diverse filter geometries.

Figure 9: Recall vs Qps comparison on SIFT dataset (𝑘 = 20: left, 𝑘 = 100: right). We compare the adjacent cube merge with different merge indices count on the SIFT dataset.

Exp-4: Index Time and Space. Table 5 reports the index construction time and space usage for CubeGraph and PostFiltering across four datasets ranging from 1M to 100M vectors. CubeGraph incurs moderate construction overhead compared to PostFiltering due to the hierarchical grid partitioning and cross-cube edge establishment. Our hierarchy terminates when cubes contain fewer than 50 nodes, ensuring sufficient points per leaf cube for effective graph navigation; empirically, 6 layers suffice for most datasets. However, this one-time construction cost is amortized over the entire query workload, and the resulting index structure enables dramatically faster query processing as demonstrated in Exp-1. The construction time scales linearly with dataset size, reaching approximately 5 hours for the Deep100M dataset, which is acceptable for offline index building. The index size remains comparable to PostFiltering across all datasets, demonstrating that CubeGraph achieves significant speedups without sacrificing space efficiency. Exp-5: Fly-Merge vs Cube-Merge. We evaluate the effectiveness of our two graph merging strategies: Fly-Merge (on-the-fly

Merge-16 Merge-128

1,500

1,500

1,000

1,000

Qps

Qps

Merge-4 Merge-64

500

500 0

0 20

40

60

recall@20(%)

80

100

20

40

60

80

100

recall@100(%)

dynamic discovery) and Cube-Merge (predetermined cube identification) with 4 cube graph indices merged. Fig. 8 presents the performance on the SIFT dataset with 𝑘 = 20 (left) and 𝑘 = 100 (right). Cube-Merge consistently outperforms Fly-Merge across all recall levels, achieving up to 1.4× higher throughput at comparable recall. This advantage stems from Cube-Merge’s upfront cube identification, which eliminates the dynamic discovery overhead during search. Fly-Merge incurs additional predicate evaluations and bitmap updates for each discovered cube, resulting in lower throughput despite its flexibility for complex filter shapes. Exp-6: Impact of Merge Number. We analyze how the number of merge indices affects query performance. Fig. 9 compares query performance for 4, 16, 64, and 128 cubes merged on the SIFT dataset. Merge-4 achieves the best performance, reaching over 99% recall@20 at 478 Qps. As the merge count increases, both recall and throughput degrade significantly. Merge-128 attains only 1/10 search efficiency of Merge-4, demonstrating that excessive graph merging fragments the proximity structure and impairs navigation. These results validate our theoretical analysis that bounded merge counts (proportional to the filter’s characteristic length) are essential for maintaining search efficiency. Exp-7: Scalability. We evaluate the scalability of CubeGraph on the Deep100M dataset containing 100M 96-dimensional vectors. Table 5 shows that CubeGraph constructs the index in approximately 5 hours (18,508 seconds), demonstrating practical scalability to hundred-million-scale datasets. Fig 10 presents the recall@20

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

CubeGraph

PostFiltering 103 Qps

103 Qps

Trovato et al.

102

85

90

95

100

102

85

recall@20(%)

90

95

100

recall@20(%)

(a) DEEP100M 2D ratio 0.01

(b) DEEP100M 2D ratio 0.02

Figure 10: Scalability on Deep100M dataset (100M vectors). Despite the massive dataset scale, CubeGraph maintains high search efficiency with Box Filter. Uniform

Normal

Clustered

Skewed

Hollow 103.5 Qps

Qps

103.5

103

103 102.5

70

80

90

recall@20(%)

(a) SIFT 2D (ratio 0.05)

100

85

90

95

100

recall@20(%)

(b) SIFT 2D (ratio 0.10)

Figure 11: Impact of metadata distribution on search efficiency.

vs. Qps performance. Despite the massive dataset size, CubeGraph achieves 99.5% recall at 250 Qps and maintains 99.5% recall at 255 Qps, demonstrating that the hierarchical grid structure effectively bounds the search space regardless of dataset cardinality. This confirms CubeGraph’s suitability for large-scale production deployments. Exp-8: Various Metadata Distributions. Fig. 11 shows CubeGraph under five metadata distributions on SIFT 2D: Uniform, Normal, Clustered, Skewed, and Hollow. At a ratio of 0.05, Skewed achieves 1,207 Qps at 99.6% recall, which is 2.5× higher than Uniform distribution because concentrated data reduces the effective search space. Clustered data yields similar to Uniform (494 Qps). At a ratio of 0.10, Skewed maintains 1.4× speedup, while Hollow performs comparably (847 Qps). Notably, Clustered degrades significantly at a higher ratio (313 Qps, half of Uniform), as dense clusters increase intracube competition. These results demonstrate CubeGraph adapts to diverse real-world data distributions, often benefiting from skewed and normal data while being robust to clustered distributions. These experiments also confirm that CubeGraph’s stable performance is not solely dependent on uniform distribution, making it suitable for a wide range of applications with varying metadata characteristics.

7

Related Work

Label Filtered Vector Search Methods. The utilization of crossgraph indices to handle filtered queries was initially explored in the context of label filtering [14, 22, 25, 35, 43, 49, 53], as demonstrated by UNG [7]; however, the performance dynamics of these merged indices were not fully analyzed. UNG leverages the inclusion relationships among labels and dynamically activates cross-graph edges, ensuring that vectors satisfying the label constraints form a navigable graph index. Building upon this, UniFilter [43] extends the UNG approach to an automaton-based framework. By designing a navigation graph on top of the base index, UniFilter achieves a plug-and-play capability without altering or disrupting the original graph structure. In contrast to these methods, CubeGraph addresses

a fundamentally distinct set of problem scenarios. While UNG requires the vectors within the merged index to exactly match the query filter, CubeGraph adopts a more flexible approach, enabling it to process significantly more complex spatio-temporal queries. Furthermore, the hierarchical structure of CubeGraph ensures robust search performance across queries of varying granularities. These characteristics make CubeGraph highly suitable for integration into modern spatio-temporal Retrieval-Augmented Generation systems. Numeric Filtered Vector Search Methods. Numeric filtering, which involves selecting vectors based on attributes like prices or timestamps [17, 23, 31, 39, 45, 47, 52, 55]. Previous work SeRF [55] use compress to reduce the 𝑂 (𝑁 2 ) space for all possible range filters, but it is limited to one-dimensional attributes and does not support complex filter shapes. Segment-Tree-based methods [8, 40, 44] build segment-tree-like tree features on top of the base graph index, but they are limited to one-dimensional attributes and do not support complex filter shapes. Hi-PNG [45] use the similar hierarchical structure of CubeGraph but studies interval-filtering ANNS (IFANNS), where both base and query vectors are associated with numerical intervals. In contrast, CubeGraph is designed to handle multi-dimensional spatio-temporal filters with complex geometries, making it more versatile for a wider range of applications. Index Merging Techniques. Index merging addresses the challenge of combining multiple graph indices into a unified structure, which is critical for distributed systems and partitioned data. Recent studies, FGIM and RNSM [1, 18], accelerate merging using NN-Descent, iteratively refining cross-partition edges through local neighbor propagation. RNSM [18] improves parallel efficiency by selecting pivots and performing local search based on pivots’ search results. Unlike previous work, CubeGraph applies the index merging concept to the hierarchical grid structure, treating each cube’s local graph as a partition. Cross-cube edges are established during construction using a lightweight search-based approach inspired by RNSM, ensuring robust connectivity with minimal overhead. This allows CubeGraph to efficiently handle filtered queries by merging only the relevant cube graphs, while maintaining high search performance through bounded merge counts.

8

Conclusion

In this paper, we presented CubeGraph, a highly efficient hierarchical grid index that addresses the core challenges of filtered approximate nearest neighbor search through dynamic graph stitching. By combining a multi-level grid structure with lightweight cross-cube edges, CubeGraph successfully overcomes the trade-off between bounding query intersections and preserving global routing. This architectural advantage translates to significant speedups over existing state-of-the-art baselines while strictly maintaining high recall. Backed by rigorous theoretical analysis on optimal layer selection and complexity, and validated by extensive experiments across diverse data distributions and filter shapes, CubeGraph establishes a robust new standard for filtered search. Moving forward, we aim to extend this framework to complex join queries and explore GPU acceleration for even greater efficiency.

CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data

References [1] 2026. Zekai Wu, Jiabao Jin, Peng Cheng, Xiaoyao Zhong, Lei Chen, Yongxin Tong, Zhitao Shen, Jingkuan Song, Heng Tao Shen, Xuemin Lin. arXiv preprint arXiv:2603.21710 (2026). https://arxiv.org/abs/2603.21710 [2] Md Mahbub Alam, Luis Torgo, and Albert Bifet. 2022. A survey on spatio-temporal data analytics systems. Comput. Surveys 54, 10s (2022), 1–38. [3] 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. Proceedings of the VLDB Endowment 9, 4 (2015). [4] Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. 2020. ANNBenchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems 87 (2020), 101374. [5] Artem Babenko and Victor Lempitsky. 2014. Additive quantization for extreme vector compression. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 931–938. [6] Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger. 1990. The R*-tree: An efficient and robust access method for points and rectangles. In Proceedings of the 1990 ACM SIGMOD international conference on Management of data. 322–331. [7] Yuzheng Cai, Jiayang Shi, Yizhuo Chen, and Weiguo Zheng. 2024. Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data 2, 6 (2024), 1–27. [8] Joshua Engels, Benjamin Landrum, Shangdi Yu, Laxman Dhulipala, and Julian Shun. 2024. Approximate Nearest Neighbor Search with Window Filters. ICML 2024 (2024). [9] 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. [10] Jianyang Gao and Cheng Long. 2023. High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations. Proc. ACM Manag. Data 1, 2 (2023), 137:1–137:27. https://doi.org/10.1145/3589282 [11] 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. [12] Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2014. Optimized Product Quantization. IEEE Trans. Pattern Anal. Mach. Intell. 36, 4 (2014), 744–755. [13] Aristides Gionis, Piotr Indyk, Rajeev Motwani, et al. 1999. Similarity search in high dimensions via hashing. In Vldb, Vol. 99. 518–529. [14] 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. [15] 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. [16] 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. Advances in Neural Information Processing Systems 32 (2019). [17] 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. Proceedings of the ACM on Management of Data 3, 3 (2025), 1–26. [18] Liuchang Jing, Mingyu Yang, Lei Li, Jianbin Qin, and Wei Wang. 2026. Multiple Index Merge for Approximate Nearest Neighbor Search. arXiv preprint arXiv:2602.17099 (2026). [19] Leonardo Kuffo, Elena Krippner, and Peter Boncz. 2025. PDX: A data layout for vector similarity search. Proceedings of the ACM on Management of Data 3, 3 (2025), 1–26. [20] Binhong Li, Xiao Yan, and Shangqi Lu. 2025. Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search. arXiv preprint arXiv:2510.05975 (2025). [21] Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. 2020. Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement. IEEE Trans. Knowl. Data Eng. 32, 8 (2020), 1475–1488. [22] Zhaoheng Li, Silu Huang, Wei Ding, Yongjoo Park, and Jianjun Chen. 2025. SIEVE: Effective Filtered Vector Search with Collection of Indexes. Proceedings of the VLDB Endowment 18, 11 (2025), 4723–4736. [23] Anqi Liang, Pengcheng Zhang, Bin Yao, Zhongpu Chen, Yitong Song, and Guangxu Cheng. 2024. UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search. Proceedings of the VLDB Endowment 18, 4 (Dec. 2024), 1118–1130. https://doi.org/10.14778/3717755.3717770 [24] Kejing Lu, Mineichi Kudo, Chuan Xiao, and Yoshiharu Ishikawa. 2021. HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search. Proc. VLDB Endow. 15, 2 (2021), 246–258. [25] Jiarui Luo, Miao Qiao, Chaoji Zuo, and Dong Deng. 2025. Tag-Filtered Approximate Nearest Neighbor Search. In 2025 IEEE 41st International Conference on Data

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Engineering (ICDE). IEEE, 3642–3654. [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] Jason Mohoney, Anil Pacaci, Shihabur Rahman Chowdhury, Ali Mousavi, Ihab F Ilyas, Umar Farooq Minhas, Jeffrey Pound, and Theodoros Rekatsinas. 2023. Highthroughput vector similarity search in knowledge graphs. Proceedings of the ACM on Management of Data 1, 2 (2023), 1–25. [28] 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. [29] 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. [30] Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang, and Jianliang Xu. 2023. Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases. Proc. ACM Manag. Data 1, 1 (2023), 54:1–54:27. https://doi.org/10.1145/3588908 [31] 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 (June 2025), 3256–3268. https://doi.org/10.14778/ 3748191.3748193 [32] 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. [33] Yitong Song, Bin Yao, Zhida Chen, Xin Yang, Jiong Xie, Feifei Li, and Mengshi Chen. 2025. Efficient top-k spatial-range-constrained approximate nearest neighbor search on geo-tagged high-dimensional vectors. The VLDB Journal 34, 1 (2025), 14. [34] 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. [35] Mengzhao Wang, Lingwei Lv, Xiaoliang Xu, Yuxiang Wang, Qiang Yue, and Jiongkang Ni. 2022. Navigable proximity graph-driven native hybrid queries with structured and unstructured constraints. arXiv preprint arXiv:2203.13601 (2022). [36] Mengzhao Wang, Haotian Wu, Xiangyu Ke, Yunjun Gao, Yifan Zhu, and Wenchao Zhou. 2025. Accelerating Graph Indexing for ANNS on Modern CPUs. arXiv preprint arXiv:2502.18113 (2025). [37] Mengzhao Wang, Weizhi Xu, Xiaomeng Yi, Songlin Wu, Zhangyang Peng, Xiangyu Ke, Yunjun Gao, Xiaoliang Xu, Rentong Guo, and Charles Xie. 2024. Starling: An I/O-Efficient Disk-Resident Graph Index Framework for HighDimensional Vector Similarity Search on Data Segment. Proc. ACM Manag. Data 2, 1 (2024), V2mod014:1–V2mod014:27. https://doi.org/10.1145/3639269 [38] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. Proceedings of the VLDB Endowment 14, 11 (2021), 1964–1978. [39] 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. [40] Ziqi Wang, Jingzhe Zhang, and Wei Hu. 2025. WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data 3, 6 (2025), 1–27. [41] 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. [42] Wenxuan Xia, Mingyu Yang, Wentao Li, and Wei Wang. 2026. Filtered Approximate Nearest Neighbor Search Cost Estimation. arXiv preprint arXiv:2602.06721 (2026). [43] 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. [44] Yuexuan Xu, Jianyang Gao, Yutong Gou, Cheng Long, and Christian S Jensen. 2024. iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search. arXiv preprint arXiv:2409.02571 (2024). [45] 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. [46] Mingyu Yang, Wentao Li, Jiabao Jin, Xiaoyao Zhong, Xiangyu Wang, Zhitao Shen, Wei Jia, and Wei Wang. 2024. Effective and General Distance Computation for Approximate Nearest Neighbor Search. arXiv preprint arXiv:2404.16322 (2024). [47] Mingyu Yang, Wentao Li, Zhitao Shen, Chuan Xiao, and Wei Wang. 2025. ESG: Elastic Graphs for Range-Filtering Approximate k-Nearest Neighbor Search. arXiv preprint arXiv:2504.04018 (2025).

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

[48] Mingyu Yang, Wentao Li, and Wei Wang. 2024. Fast High-dimensional Approximate Nearest Neighbor Search with Efficient Index Time and Space. arXiv preprint arXiv:2411.06158 (2024). [49] Mingyu Yang, Wenxuan Xia, Wentao Li, Raymond Chi-Wing Wong, and Wei Wang. 2025. Elastic Index Select for Label-Hybrid Search in Vector Database. arXiv preprint arXiv:2505.03212 (2025). [50] Ziqi Yin, Jianyang Gao, Pasquale Balsebre, Gao Cong, and Cheng Long. 2025. DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph. Proceedings of the ACM on Management of Data 3, 1 (2025), 1–28. [51] Yuanhang Yu, Dawei Cheng, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2026. Efficient Approximate Nearest Neighbor Search under Multi-Attribute Range Filter. arXiv preprint arXiv:2602.15488 (2026). [52] Fangyuan Zhang, Mengxu Jiang, Guanhao Hou, Jieming Shi, Hua Fan, Wenchao Zhou, Feifei Li, and Sibo Wang. 2025. Efficient Dynamic Indexing for Range

Trovato et al.

Filtered Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data 3, 3 (2025), 1–26. [53] Qianxi Zhang, Shuotao Xu, Qi Chen, Guoxin Sui, Jiadong Xie, Zhizhen Cai, Yaoqi Chen, Yinxuan He, Yuqing Yang, Fan Yang, et al. 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). 377–395. [54] Xiaoyao Zhong, Haotian Li, Jiabao Jin, Mingyu Yang, Deming Chu, Xiangyu Wang, Zhitao Shen, Wei Jia, George Gu, Yi Xie, et al. 2025. VSAG: An Optimized Search Framework for Graph-based Approximate Nearest Neighbor Search. arXiv preprint arXiv:2503.17911 (2025). [55] 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.

CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data

Appendix A.1 Proof of Theorem 1 (Optimal Layer Selection) We analyze three cases to show why 𝑤 ℓ ∗ ≈ 𝑟 is optimal: Case 1: 𝑤 ℓ ≫ 𝑟 (cubes too large). When the cube width is much larger than the filter’s characteristic length, the filter intersects only a few cubes (possibly just one). However, each cube contains 𝑚 𝑂 (𝑁 · 𝑤 𝑚 ℓ /𝑆 ) points under uniform distribution, while the filter covers only 𝑂 (𝑟 𝑚 ) volume. This leads to a low elastic factor 𝑒 ≈ (𝑟 /𝑤 ℓ )𝑚 ≪ 1, meaning most searched points do not satisfy the filter. Case 2: 𝑤 ℓ ≪ 𝑟 (cubes too small). When the cube width is much smaller than the filter’s characteristic length, the filter intersects 𝑂 ((𝑟 /𝑤 ℓ )𝑚 ) cubes. This creates two problems: (1) high merge overhead from connecting many cube graphs, and (2) graph search performance degradation. As the number of merged cubes grows, the graph index search becomes less efficient because: (a) more cross-cube edges must be traversed, (b) the larger search space reduces graph navigability, and (c) beam search becomes less effective with a fragmented graph structure. Experimental results (Section 6) demonstrate that query latency increases significantly as the number of merged cubes grows beyond a small constant. Case 3: High aspect ratio rectangles (𝛼 ≫ 1). For a rectangular filter with sides (𝑟 max, 𝑟 min ) where 𝛼 = 𝑟 max /𝑟 min ≫ 1, the analysis becomes more nuanced. If we select the layer based on 𝑟 max such that 𝑤 ℓ ≈ 𝑟 max , the rectangle intersects approximately 2 cubes along each dimension perpendicular to the long axis, but 𝑂 (𝛼) cubes along the long dimension. In 2D, this yields approximately 2𝛼 intersecting cubes; in 3D, approximately 4𝛼 cubes (assuming the third dimension is comparable to 𝑟 min ). Alternatively, selecting the layer based on 𝑟 min (i.e., 𝑤 ℓ ≈ 𝑟 min ) still results in 𝑂 (𝛼) cubes along the long dimension. Thus, for high aspect ratio filters, the number of intersecting cubes is 𝑂 (𝛼) rather than 𝑂 (1). This has two important consequences: (1) graph search performance degrades as 𝛼 increases due to merging more cubes, and (2) the elastic factor degrades approximately as 𝑂 (1/𝛼 2 ) (analyzed in detail below). Therefore, CubeGraph achieves optimal performance for filters with bounded aspect ratio (𝛼 = 𝑂 (1)). Optimal case: 𝑤 ℓ ≈ 𝑟 . When 𝑟 /2 < 𝑤 ℓ < 𝑟 , the filter intersects at most 2𝑚 cubes (4 in 2D, 8 in 3D). This keeps the number of merged cubes to a small constant, maintaining high graph search performance while achieving good elastic factor. The elastic factor is bounded below by a constant that depends on the filter shape (e.g., 𝜋/(4 · 2𝑚 ) for circular filters).

A.2 Proof of Lemma 1 (Elastic Factor Bound) At the optimal layer, the filter with characteristic length 𝑟 intersects 𝑚 at most 2𝑚 cubes, each with volume 𝑤 𝑚 ℓ ∗ ≈ 𝑟 . The union of cubes 𝑚 𝑚 has volume at most 2 · 𝑟 . For a circular filter with diameter 𝑟 , the volume is 𝜋 𝑚/2 · (𝑟 /2)𝑚 /Γ(𝑚/2 + 1). Therefore, 𝑒 ≥ 𝜋 𝑚/2 · (𝑟 /2)𝑚 /(Γ(𝑚/2 + 1) · 2𝑚 · 𝑟 𝑚 ) = 𝜋 𝑚/2 /(2𝑚 · Γ(𝑚/2 + 1)). For 𝑚 = 2, this gives 𝑒 ≥ 𝜋/16 ≈ 0.196; for 𝑚 = 3, 𝑒 ≥ 𝜋/(48) ≈ 0.065.

A.3 Proof of Theorem 1 (Space Complexity) Each data point appears in exactly one cube at each of the 𝐿 layers. At each layer, the point maintains: (1) up to 𝑀 intra-cube edges to

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

neighbors within the same cube, and (2) up to 2𝑚 · 𝑀cross cross-cube edges to neighbors in adjacent cubes (there are 2𝑚 adjacent cubes in an 𝑚-dimensional grid). Therefore, each point stores 𝑂 (𝑀 + 𝑚 · 𝑀cross ) edges per layer, yielding total space 𝑂 (𝑁 ·𝐿 · (𝑀 +𝑚 ·𝑀cross )).

A.4 Proof of Theorem 2 (Construction Time) Construction consists of two phases: (1) building local graph indices within each cube, and (2) adding cross-cube edges. For phase (1), each of the 𝑁 points is inserted into 𝐿 layers, with each insertion costing 𝑂 (log 𝑁 ) on average for graph-based indices like HNSW, yielding 𝑂 (𝑁 · 𝐿 · log 𝑁 ) time. For phase (2), each point at each layer requires searching in 2𝑚 adjacent cubes to establish cross-cube edges. Each search identifies 𝑀cross neighbors with cost 𝑂 (log 𝑁 ), yielding 𝑂 (𝑁 · 𝐿 · 2𝑚 · 𝑀cross · log 𝑁 ) = 𝑂 (𝑁 · 𝐿 · 𝑚 · 𝑀cross · log 𝑁 ) time. The total construction time is the sum of both phases.

A.5 Proof of Theorem 3 (Query Time Complexity) The query processing consists of three phases: Phase 1: Layer selection. We select the optimal layer ℓ ∗ by binary search over 𝐿 layers, comparing 𝑤 ℓ with the characteristic length 𝑟 . This costs 𝑂 (log 𝐿) time. Phase 2: Cube identification. At the optimal layer ℓ ∗ , we identify all cubes intersecting the filter 𝜙. By Corollary 1, there are at most 2𝑚 · 𝛼 such cubes, where 𝛼 = 𝑟 max /𝑟 min is the aspect ratio. For filters with bounded aspect ratio (𝛼 = 𝑂 (1)), this is 𝑂 (1) cubes. Phase 3: Graph search. We perform beam search on the merged graph G ∗ formed by the 𝑂 (1) intersecting cubes. Locating the top-1 neighbor costs 𝑂 (𝐶), where 𝐶 depends on the graph structure and search parameters. For each additional result, we visit amortized 𝑂 (1/𝑐) candidates because at least a fraction 𝑐 of visited neighbors satisfy the filter (due to the elastic factor bound 𝑒 ≥ 𝑐). Retrieving 𝑘 − 1 additional results costs 𝑂 (𝑘/𝑐). The total query time is 𝑂 (log 𝐿 + 𝐶 + 𝑘/𝑐) = 𝑂 (𝐶 + 𝑘/𝑐) since 𝐶 dominates for typical values of 𝐿 and 𝑘.

A.6 Detailed Discussion: Query Performance Degradation The 𝑂 (1) bound on the number of merged cubes (Corollary 1) is critical for achieving the 𝑂 (𝐶 + 𝑘/𝑐) query time. When 𝑤 ℓ ≪ 𝑟 , the number of merged cubes grows as 𝑂 ((𝑟 /𝑤 ℓ )𝑚 ), which causes significant performance degradation: • More cross-cube edges to traverse: Each additional cube introduces 𝑂 (𝑀cross ) cross-cube edges per boundary node, increasing the search space. • Reduced graph navigability: Merging many small cube graphs creates a fragmented structure where the small-world property of graph indices degrades. • Beam search inefficiency: With a larger, more fragmented search space, beam search becomes less effective at pruning irrelevant candidates. Our experiments (Section 6) validate this analysis by showing that query latency increases significantly as the number of merged cubes grows beyond 2𝑚 . By selecting the optimal layer where 𝑤 ℓ ∗ ≈ 𝑟 , CubeGraph maintains a small constant number of merged cubes, preserving high graph search performance.

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Impact of aspect ratio. For rectangular filters with high aspect ratio 𝛼 = 𝑟 max /𝑟 min , the number of merged cubes grows as 𝑂 (𝛼) (Corollary 1), and the elastic factor degrades as 𝑂 (1/𝛼 2 ). This causes the query time to increase from 𝑂 (𝐶 + 𝑘/𝑐) to 𝑂 (𝐶 + 𝑘 · 𝛼 2 ) due to the lower elastic factor. Additionally, merging 𝑂 (𝛼) cubes instead of 𝑂 (1) cubes causes graph search performance degradation. Experimental validation (Section 6) shows that query latency increases significantly for high aspect ratio filters.

A.7 Proof of Theorem 4 (Update Complexity) For insertion, each point is inserted into 𝐿 layers. At each layer, inserting into the local graph costs 𝑂 (log 𝑁 ), and establishing crosscube edges to 2𝑚 adjacent cubes costs 𝑂 (𝑚 · 𝑀cross · log 𝑁 ). For lazy deletion, we mark the point as invalid in all 𝐿 layers, costing 𝑂 (𝐿).

Trovato et al.

For eager deletion, we remove the point from neighbor lists and repair connections, which costs 𝑂 (𝑀 2 ) per layer due to the need to reconnect up to 𝑀 neighbors.

A.8 Example: High Aspect Ratio Rectangle Consider a 2D rectangular filter with sides 100 × 10 (aspect ratio 𝛼 = 10) in a metadata space of side length 𝑆 = 1000. With optimal layer selection where 𝑤 ℓ ≈ 100, the rectangle intersects approximately 20 cubes (2 along the short dimension, 10 along the long dimension). The rectangle has area 1000, and the union of 20 cubes has area approximately 20 × 1002 = 200,000. The elastic factor is 𝑒 ≈ 1000/200,000 = 0.005, which is much lower than the 𝜋/16 ≈ 0.196 bound for circular filters. This demonstrates why high aspect ratio filters lead to poor query performance in CubeGraph .

Related documents

• Property Testing for Recursive Query Languages#639749
• From Data Querying to Data Investigations: Rethinking Natural Language Interfaces for Databases#639750
• Aker: Density-Aware Approximate Caching for Vector Search (Extended Version)#639751
• Convolution Sum-Product Queries#639752
• Tree Databases#639753