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

• URL: http://arxiv.org/abs/2604.06616v1
• Date: Wed, 08 Apr 2026 02:49:55 GMT
• Title: CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data
• Abstract summary: CubeGraph is a framework designed to integrate vector search with arbitrary spatial constraints.<n>During query execution, CubeGraph stitches together adjacent cube-level indices on the fly whenever spatial cells intersect with the query filter.
• Score: 11.878755010092922
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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.

Related papers

• A Versioned Unified Graph Index for Dynamic Timestamp-Aware Nearest Neighbor Search [4.414455125136369]
  TiGER is a novel approach for performing fast time-aware approximate nearest neighbor searches on dynamic vector datasets.<n>Our proposed algorithm builds and maintains a unified graph for all vectors by leveraging an index structure based on integrated versioned connectivity.
  arXiv  Detail & Related papers  (2026-08-27T19:51:28Z)
• Unified Dominance Graph for Interval-Predicate Approximate Nearest Neighbor Search [8.875776605139185]
  We study Interval-Predicate ANNS, where validity is determined by a predicate between an object interval and a query interval.<n>Existing range-filtering ANNS methods are designed for single-dimensional scalar filters.<n>We propose the Unified Dominance Graph (UDG), a graph-indexing framework for the closed two-bound conjunctive fragment of IPANNS.
  arXiv  Detail & Related papers  (2026-06-23T06:46:28Z)
• Beyond Chunk-Local Extraction: Cross-Chunk Graph Augmentation for GraphRAG [11.699085890492833]
  GraphRAG extends retrieval-augmented generation by organizing corpora as explicit knowledge graphs.<n>Existing frameworks extract entities and relations within individual chunks, leaving cross-chunk relations systematically absent from the index.<n>We present CrossAug, a GNN-guided CROSS-Chunk Graph AUGmentation method that enriches GraphRAG indices with cross-chunk relational structure.
  arXiv  Detail & Related papers  (2026-05-27T05:55:53Z)
• Curator: Efficient Vector Search with Low-Selectivity Filters [12.774238654446032]
  Graph-based indexes achieve state-of-the-art performance on unfiltered ANNS but encounter connectivity breakdown on low-selectivity filtered queries.<n>Recent research proposes specialized graph indexes that address this issue by expanding graph degree.<n>We present Curator, a partition-based index that complements existing graph-based approaches for low-selectivity filtered ANNS.
  arXiv  Detail & Related papers  (2026-01-03T21:35:01Z)
• The Hybrid Multimodal Graph Index (HMGI): A Comprehensive Framework for Integrated Relational and Vector Search [6.821769033209393]
  This paper introduces the Hybrid Multimodal Graph Index (HMGI), a novel framework designed to bridge the gap between vector databases and graph databases.<n>By integrating semantic similarity search directly with relational context, HMGI aims to outperform pure vector databases in complex, relational-heavy query scenarios.
  arXiv  Detail & Related papers  (2025-10-11T09:06:26Z)
• HedraRAG: Coordinating LLM Generation and Database Retrieval in Heterogeneous RAG Serving [10.130938079844121]
  HedraRAG is a runtime system built on a graph-based abstraction that exposes optimization opportunities across stage-level parallelism, intra-request similarity, and inter-request skewness.<n>The resulting execution plans are mapped onto hybrid CPU-GPU pipelines to improve resource utilization and reduce latency.
  arXiv  Detail & Related papers  (2025-07-12T04:42:43Z)
• Divide-Then-Rule: A Cluster-Driven Hierarchical Interpolator for Attribute-Missing Graphs [51.13363550716544]
  Deep graph clustering is an unsupervised task aimed at partitioning nodes with incomplete attributes into distinct clusters.<n>Existing imputation methods for attribute-missing graphs often fail to account for the varying amounts of information available across node neighborhoods.<n>We propose Divide-Then-Rule Graph Completion (DTRGC) to address this issue.
  arXiv  Detail & Related papers  (2025-07-12T03:33:19Z)
• Divide by Question, Conquer by Agent: SPLIT-RAG with Question-Driven Graph Partitioning [62.640169289390535]
  SPLIT-RAG is a multi-agent RAG framework that addresses the limitations with question-driven semantic graph partitioning and collaborative subgraph retrieval.<n>The innovative framework first create Semantic Partitioning of Linked Information, then use the Type-Specialized knowledge base to achieve Multi-Agent RAG.<n>The attribute-aware graph segmentation manages to divide knowledge graphs into semantically coherent subgraphs, ensuring subgraphs align with different query types.<n>A hierarchical merging module resolves inconsistencies across subgraph-derived answers through logical verifications.
  arXiv  Detail & Related papers  (2025-05-20T06:44:34Z)
• RGL: A Graph-Centric, Modular Framework for Efficient Retrieval-Augmented Generation on Graphs [58.10503898336799]
  We introduce the RAG-on-Graphs Library (RGL), a modular framework that seamlessly integrates the complete RAG pipeline.<n>RGL addresses key challenges by supporting a variety of graph formats and integrating optimized implementations for essential components.<n>Our evaluations demonstrate that RGL not only accelerates the prototyping process but also enhances the performance and applicability of graph-based RAG systems.
  arXiv  Detail & Related papers  (2025-03-25T03:21:48Z)
• Multi-Scene Generalized Trajectory Global Graph Solver with Composite Nodes for Multiple Object Tracking [61.69892497726235]
  Composite Node Message Passing Network (CoNo-Link) is a framework for modeling ultra-long frames information for association. In addition to the previous method of treating objects as nodes, the network innovatively treats object trajectories as nodes for information interaction. Our model can learn better predictions on longer-time scales by adding composite nodes.
  arXiv  Detail & Related papers  (2023-12-14T14:00:30Z)
• Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
  This paper proposes a novel unsupervised approach called spatial-spectral clustering with anchor graph (SSCAG) for HSI data clustering. The proposed SSCAG is competitive against the state-of-the-art approaches.
  arXiv  Detail & Related papers  (2021-04-24T08:09:27Z)
• Graph Neural Networks with Composite Kernels [60.81504431653264]
  We re-interpret node aggregation from the perspective of kernel weighting. We present a framework to consider feature similarity in an aggregation scheme. We propose feature aggregation as the composition of the original neighbor-based kernel and a learnable kernel to encode feature similarities in a feature space.
  arXiv  Detail & Related papers  (2020-05-16T04:44:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.