CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data
Mingyu Yang, Wentao Li, Wei Wang · 2026
Read CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data by Mingyu Yang, Wentao Li, Wei Wang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-06616.txt.
Introduction
Yang, Li, and Wang build CubeGraph, an index for queries mixing vector similarity with space and time filters. Older systems nest vector indices inside spatial trees like R-trees, splintering vector space and forcing many separate sub-index calls per query. CubeGraph instead grids space hierarchically, keeps modular graphs in each cell, and stitches neighboring cells on the fly where they meet the filter. That restores one connected graph and a single-pass search, and real-data tests show it beats leading baselines on speed, scale, and flexibility.
Catalog record
| CREATOR | Mingyu Yang, Wentao Li, Wei Wang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 77199 |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.06616
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data Mingyu Yang, Wentao Li, Wei Wang Abstract . 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. † † authors: . PVLDB Reference Format: PVLDB, 14(1): XXX-XXX, 2020. doi:XX.XX/XXX.XX † † This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected] . Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/mingyu-hkustgz/CubeGraph . 1. Introduction 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 ( 1 ) . 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. 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 ). 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. Figure 1 . Motivating examples for hybrid vector similarity search with spatio-temporal filters. Each data object is represented by a high-dimensional vector embedding \mathbf{x}_{i} and associated with spatio-temporal metadata \mathbf{s}_{i} (e.g., geolocation and timestamp). (1) Urban event retrieval: a city management platform stores geo-tagged reports, images, and videos. Given a query vector \mathbf{q} (e.g., flooded streets ) and a spatio-temporal filter \phi , the task is to retrieve the top- k most similar objects satisfying \phi(\mathbf{s}_{i})=1 . (2) Regional multimedia retrieval: a multimedia database stores geo-tagged images and videos. Given a query image \mathbf{q} and a complex polygonal filter \phi , the system must return the top- k nearest neighbors within the specified spatio-temporal constraints. Existing database solutions typically model this as a filtered approximate k -nearest neighbor (AKNN) search problem. Since the exact result is hard to obtain in the high-dimensional space due to the curse of dimensionality ( 14 ) . Among various vector index ( 11 ; 2 ; 12 ; 4 ; 10 ; 49 ; 19 ) , graph-based vector indices (e.g., HNSW) offer superior naive AKNN query efficiency ( 3 ; 8 ; 27 ; 30 ; 21 ; 24 ; 31 ; 20 ; 15 ; 52 ; 19 ; 28 ; 39 ; 38 ; 37 ; 9 ; 47 ) , most existing methods attempt to adapt the graph structure or traversal process to accommodate metadata filters ( 30 ; 42 ; 45 ; 48 ; 13 ; 7 ; 58 ; 51 ; 55 ; 41 ; 16 ; 44 ; 57 ; 35 ; 43 ; 6 ; 29 ) . A standard graph index navigates the high-dimensional space by routing through proximity-based neighbor connections until converging on the k -nearest neighbors of query. Early execution paradigms, namely {\mathsf{PreFiltering}} and {\mathsf{PostFiltering}} , leave the underlying graph topology unchanged but modify the traversal logic. {\mathsf{PreFiltering}} prunes nodes failing the predicate during traversal, which severely degrades graph connectivity and search accuracy under low filter selectivity. Conversely, {\mathsf{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 ( 7 ) , iRange ( 45 ) , ESG ( 48 ) , and WoW ( 41 ) build segment-tree-like structures where each tree node maintains a separate graph index. Consequently, answering a range filter query introduces an O(\log N) multiplicative overhead to the query execution time, alongside an O(N\log N) space complexity since the graph index has linear complexity. 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 ( 34 ; 53 ) . During query execution, the engine traverses the tree and invokes the graph indices attached to the overlapping tree nodes, subsequently merging the results ( 34 ) . However, even with only 2D metadata, a KD-tree requires O(\sqrt{N}) 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. Our Idea. In this paper, we propose {\mathsf{CubeGraph}} , a novel index structure and search paradigm designed to efficiently process hybrid queries with arbitrary spatio-temporal filters. Our fundamental insight is that a graph