用网格化动态拼接图结构,让时空查询更快更准。
CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data

- 用分层网格划分空间,每个格子存向量图,动态拼接相关格子。
- 在真实数据集上,查询速度比现有方法快2.3倍以上。
- 适合需要复杂时空过滤的智能搜索系统开发者。
结合高维向量相似性搜索与时空过滤的混合查询,在现代检索增强生成(RAG)系统中日益重要。现有系统通常将向量索引嵌套于低维空间结构(如R树),但这种解耦架构会割裂向量空间,导致每次查询需调用多个独立子索引,破坏图结构连通性,产生严重遍历开销,难以优化复杂空间边界。本文提出CubeGraph,一种原生融合向量搜索与任意时空约束的索引框架。该框架通过分层网格划分空间域,在每个单元内维护模块化向量图。查询时,若空间单元与查询过滤条件相交,则动态实时拼接相邻立方体级索引。此动态图集成恢复全局连通性,实现统一、单次遍历的最近邻查找,消除碎片化子索引调用开销。在真实世界数据集上的广泛评估表明,CubeGraph显著优于当前最优基线,展现更优的查询性能、可扩展性与复杂混合负载下的灵活性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。