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

Mingyu Yang; Wentao Li; Wei Wang

cs.DBApr 8, 2026

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

Authors: Mingyu Yang, Wentao Li, Wei Wang

Organizations: HKUST (GZ) & HKUST China · University of Leicester United Kingdom

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.

Figures & tables

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.

Feature	${\mathsf{CubeGraph}}$ (Our)	${\mathsf{PostFiltering}}$	${\mathsf{ACORN}}$	Tree-Graph
Performance	$\star\star\star$	$\star$	$\star$	$\star\star$
Compact	✓	✓	✓	$\times$
Connectivity	✓	✓	$\times$	$\times$
Flexibility	✓	✓	✓	$\times$

Table 1. Comparison of

{\mathsf{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).

Notation	Description
$\mathcal{D}$	Dataset of $N$ data points
$N$	Number of data points in the dataset
$d$	Dimensionality of vector embeddings
$m$	Dimensionality of spatio-temporal metadata
$\mathbf{x}_{i}$	Vector embedding of data point $o_{i}$
$\mathbf{s}_{i}$	Spatio-temporal metadata of data point $o_{i}$

Table 2. Summary of Notations

Figure 2. Framework of ${\mathsf{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 ${\mathsf{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.

Figure 3. Memory layout of

{\mathsf{CubeGraph}}

. Each node in

{\mathsf{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

L

across

L

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.

Aspect	Predetermined	On-the-Fly
Filter Type	Simple (boxes)	Complex (circles, polygons)
Cube Discovery	Pre-computed	Dynamic
Overhead	Lower	Medium
Flexibility	Limited	High
Use Case	Known Cubes	Unknown Intersection

Table 3. Comparison of Query Processing Approaches

Dataset	Size	Dim	Query Size	Metadata
SIFT1M	1,000,000	128	10,000	2D/3D/4D Uniform
YFCC	999,894	512	1,000	2D/3D Geo
WIKI	1,170,381	384	1,000	2D/3D Geo
MSMARC10M	10,000,000	1024	1,000	2D/3D/4D Uniform
Deep100M	100,000,000	96	1,000	2D/3D Uniform

Table 4. The Statistics of Datasets

Figure 4. Distribution of Metadata Attributes Across Datasets.

Panel of Figure 6 — Figure 6. Search efficiency comparison across different dimensions (3D/4D) with Bounding Boxes filter (recall@20 vs. Qps).

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

	SIFT	YFCC	WIKI	MSMARC10M	Deep100M
${\mathsf{CubeGraph}}$	88	251	397	4767	16224
${\mathsf{PostFiltering}}$	47	50	58	647	2467
${\mathsf{ACORN}}$ - $\gamma$	49	133	180	3572	10484
TreeGraph	153	328	556	12494	–
iRangeGraph	494	1007	3261	20192	–

Table 5. Indexing Time (seconds)

	SIFT	WIKI	YFCC	MSMARC10M	Deep100M
Dataset	489	1767	1956	39062	37004
${\mathsf{CubeGraph}}$	1038	1215	1038	10376	102996
${\mathsf{PostFiltering}}$	172	156	172	1716	17166
${\mathsf{ACORN}}$ - $\gamma$	363	2000	360	3638	36724
TreeGraph	1541	1961	1540	20880	–
iRangeGraph	888	1228	873	11934	–

Table 6. Index Size (MB)

Panel of Figure 8 — Figure 8. Dynamic update time comparison on (a) SIFT and (b) YFCC. Both datasets use 100K initial vectors with 32 threads. Incremental update is consistently faster than full rebuild across all update ratios.

Panel of Figure 9 — Figure 9. Recall vs Qps comparison on SIFT dataset ( $k=20$ : left, $k=100$ : right). We compare the adjacent cube merge with different merge indices count on the SIFT dataset with 2D metadata.

Panel of Figure 10 — Figure 10. Scalability on Deep100M dataset (100M vectors). Despite the massive dataset scale, $\mathsf{CubeGraph}$ maintains high search efficiency with Box Filter.

Panel of Figure 11 — Figure 11. Impact of metadata distribution on search efficiency.

Panel of Figure 12 — Figure 12. Impact of filter aspect ratio on CubeGraph search efficiency (filter ratio 0.1). As aspect ratio increases, QPS drops dramatically while recall stays high due to the degrade of elastic factor.

Panel of Figure 13 — Figure 13. Recall vs Qps comparison on SIFT dataset ( $k=20$ : left, $k=100$ : right). We compare hnsw-cube-merge4 and hnsw-fly-merge4 on the SIFT dataset.

Hybrid Retrieval

Hybrid retrieval combines lexical, dense, and structured search signals to find relevant evidence more reliably.

See all 91 papers

GraphER: An Efficient Graph-Based Enrichment and Reranking Method for Retrieval-Augmented Generation
Mar 26, 2026Ruizhong Miao, Yuying Wang, Rongguang Wang +4Multi-Hop Retrieval Retrieval-Augmented Generation
Oracle AI
Graphs RAG at Scale: Beyond Retrieval-Augmented Generation With Labeled Property Graphs and Resource Description Framework for Complex and Unknown Search Spaces
Mar 21, 2026Manie Tadayon, Mayank GuptaGraph Retrieval-Augmented Generation Graph-Based Retrieval
AI Scientist, Capital Group
GEM: A Native Graph-based Index for Multi-Vector Retrieval
Mar 20, 2026Yao Tian, Zhoujin Tian, Xi Zhao +2Multi-Vector Retrieval Graph-Based Retrieval
The Hong Kong University of Science and Technology, Hong Kong, China · Hong Kong Generative AI Research & Development Center, Hong Kong, China

Mar 26, 2026J/K move · Enter open · S save

GraphER: An Efficient Graph-Based Enrichment and Reranking Method for Retrieval-Augmented Generation

Ruizhong Miao, Yuying Wang, Rongguang Wang, Chenyang Li+3

Oracle AI

Multi-Hop Retrieval Retrieval-Augmented Generation Information Retrieval Graph-Based Retrieval

Open paper AskPDF arXiv

Semantic search in retrieval-augmented generation (RAG) systems is often insufficient for complex information needs, particularly when relevant evidence is scattered across multiple sources, because it may fail to retrieve the complete set of evidence. Existing approaches to addressing this problem either rely on iterative agentic retrieval, which can be computationally inefficient, or maintain additional structures such as knowledge graphs, which introduce storage and maintenance overhead. In this paper, we propose GraphER, a graph-based enrichment and reranking framework that (1) leverages the organizational structure of data to capture proximity relationships beyond semantic similarity, (2) constructs a graph at query time based on these proximities, and (3) applies graph-based ranking to surface the top candidate documents. Experiments across table retrieval, multi-hop retrieval, and long-document retrieval benchmarks demonstrate consistent improvements in terms of retrieval completeness. Additionally, GraphER requires no additional graph infrastructure and integrates seamlessly with standard vector stores. The framework is retriever-agnostic, supports multiple forms of proximity, and introduces minimal query-time latency.

Abstract

Hybrid Retrieval

Explore similar work

GraphER: An Efficient Graph-Based Enrichment and Reranking Method for Retrieval-Augmented Generation

Graphs RAG at Scale: Beyond Retrieval-Augmented Generation With Labeled Property Graphs and Resource Description Framework for Complex and Unknown Search Spaces

GEM: A Native Graph-based Index for Multi-Vector Retrieval