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

arXiv: https://arxiv.org/abs/2604.06616 · HTML: https://mlsanity.com/paper/2604.06616/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Knowledge-graph and structured-knowledge RAG, one of 15 directions in Retrieval-augmented generation.
- Builds on 15 of its 43 references that are in the map.
- First posted on arXiv 8 Apr 2026.

## Placed in

- Retrieval-augmented generation / [Knowledge-graph and structured-knowledge RAG](https://mlsanity.com/rag/knowledge-graph-and-structured-knowledge-rag/)

## Builds on (most cited first, 15 of 15)

- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021)
- [ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data](https://mlsanity.com/paper/2403.04871/) (2024)
- [High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations](https://mlsanity.com/paper/2303.09855/) (2023)
- [High-Throughput Vector Similarity Search in Knowledge Graphs](https://mlsanity.com/paper/2304.01926/) (2023)
- [Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment](https://mlsanity.com/paper/2401.02116/) (2024)
- [Approximate Nearest Neighbor Search with Window Filters](https://mlsanity.com/paper/2402.00943/) (2024)
- [UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search](https://mlsanity.com/paper/2412.02448/) (2024)
- [A Survey on Spatio-temporal Data Analytics Systems](https://mlsanity.com/paper/2103.09883/) (2021)
- [PDX: A Data Layout for Vector Similarity Search](https://mlsanity.com/paper/2503.04422/) (2025)
- [Navigable Proximity Graph-Driven Native Hybrid Queries with Structured and Unstructured Constraints](https://mlsanity.com/paper/2203.13601/) (2022)
- [SIEVE: Effective Filtered Vector Search with Collection of Indexes](https://mlsanity.com/paper/2507.11907/) (2025)
- [DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph](https://mlsanity.com/paper/2502.07343/) (2025)
- [Efficient Approximate Nearest Neighbor Search under Multi-Attribute Range Filter](https://mlsanity.com/paper/2602.15488/) (2026)

## Abstract (arXiv)

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.