pith. sign in

arxiv: 2604.06616 · v2 · submitted 2026-04-08 · 💻 cs.DB · cs.AI· cs.IR

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

Mingyu Yang , Wentao Li , Wei Wang This is my paper

Pith reviewed 2026-05-10 17:28 UTC · model grok-4.3

classification 💻 cs.DB cs.AIcs.IR
keywords CubeGraphhybrid vector-spatial queriesdynamic graph stitchingretrieval-augmented generationspatial indexingnearest neighbor searchgrid partitioning
0
0 comments X

The pith

CubeGraph partitions space into grid cells and stitches their vector graphs on the fly to support unified nearest-neighbor search under arbitrary spatial filters.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper addresses hybrid queries that mix high-dimensional vector similarity with spatio-temporal constraints in retrieval-augmented generation systems. Existing methods nest vector indexes inside spatial trees, which splits the vector space into disjoint pieces and forces repeated index calls per query. CubeGraph instead divides space into a hierarchy of grid cells, each holding its own vector graph, then connects neighboring graphs dynamically only for cells that overlap the query region. This produces one connected structure for a single traversal pass. If the approach holds, hybrid workloads become faster and avoid the fragmentation penalty of nested designs.

Core claim

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.

What carries the argument

Dynamic on-the-fly stitching of adjacent cube-level vector graphs to restore global connectivity for single-pass traversal across query-overlapping cells.

If this is right

  • Hybrid queries execute in one traversal instead of multiple disjoint index calls.
  • Arbitrary spatial boundaries no longer require pre-built composite indexes.
  • Scalability improves because each cell's graph stays small and independent until query time.
  • The same grid can support both spatial and temporal filters by treating time as an extra dimension.
  • Query planners gain flexibility to choose stitching granularity without rebuilding the entire index.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same stitching idea might reduce latency in other settings where data is naturally partitioned, such as distributed vector stores.
  • If cell size is chosen poorly, stitching cost could grow with query complexity, suggesting a need for adaptive cell sizing.
  • Temporal data could reuse the grid without changing the core stitching logic, unifying space-time queries under one mechanism.
  • The approach implies that tree-based nesting may be fundamentally less suited to vector graphs than explicit grid partitions.

Load-bearing premise

That stitching graphs from neighboring cells can always restore full connectivity and keep overhead low even when query boundaries are irregular or cross many cells.

What would settle it

Measure traversal time and result completeness for queries whose spatial filter crosses cell boundaries in a non-rectangular way on a dataset larger than the index cache, then compare against a nested R-tree baseline.

Figures

Figures reproduced from arXiv: 2604.06616 by Mingyu Yang, Wei Wang, Wentao Li.

Figure 1
Figure 1. Figure 1: Motivating examples for hybrid vector similarity search [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Framework of 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 o… view at source ↗
Figure 3
Figure 3. Figure 3: Memory layout of CubeGraph. Each node in CubeGraph uti￾lizes 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 𝐿 across 𝐿 layers. Within any specific layer, a node maintains both intra-cube neighbors and cross-cube neighbors, the latter being determined by the metadata dimensionality. Ad… view at source ↗
Figure 4
Figure 4. Figure 4: Distribution of Metadata Attributes Across Datasets. [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Search efficiency comparison across different datasets with Bounding Boxes Filter (recall@20 vs. Qps). [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Search efficiency comparison across different dimensions (3D/4D) with Bounding Boxes filter (recall@20 vs. Qps). [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Comparison of Polygon and Radius filters vs Cube filter on SIFT (recall@20 vs. Qps). [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Dynamic update time comparison on (a) SIFT and (b) YFCC. [PITH_FULL_IMAGE:figures/full_fig_p011_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Recall vs Qps comparison on SIFT dataset ( [PITH_FULL_IMAGE:figures/full_fig_p012_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Scalability on Deep100M dataset (100M vectors). Despite [PITH_FULL_IMAGE:figures/full_fig_p012_10.png] view at source ↗
Figure 12
Figure 12. Figure 12: Impact of filter aspect ratio on CubeGraph search effi [PITH_FULL_IMAGE:figures/full_fig_p016_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Recall vs Qps comparison on SIFT dataset ( [PITH_FULL_IMAGE:figures/full_fig_p016_13.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper proposes CubeGraph, a novel indexing framework for hybrid vector similarity search combined with arbitrary spatio-temporal filters in RAG systems. It partitions the spatial domain into a hierarchical grid, maintains independent modular vector graphs within each cell, and dynamically stitches adjacent cube-level graphs on the fly during query execution whenever cells intersect the query filter. This is claimed to restore global connectivity, enabling a single-pass nearest-neighbor traversal that avoids the fragmentation and overhead of nested R-tree plus vector-index baselines. Extensive evaluations on real-world datasets are said to show superior query performance, scalability, and flexibility for complex hybrid workloads.

Significance. If the dynamic stitching mechanism preserves nearest-neighbor paths across cell boundaries without introducing substantial per-query overhead or connectivity gaps for irregular regions, the approach could offer a more integrated and efficient alternative to decoupled indexing structures, with potential benefits for large-scale spatio-temporal RAG applications.

major comments (3)
  1. [Query Execution] The description of the stitching algorithm (how cross-cell edges or virtual links are identified and materialized at query time, and whether it uses boundary-point matching or k-NN links) is insufficient to evaluate whether global connectivity is restored for arbitrary (non-rectangular) query regions without missing paths or repeated stitching steps.
  2. [Query Execution] No analysis is provided of typical numbers of cells stitched per query, resulting graph diameter changes, or overhead measurements relative to the savings from avoiding multiple sub-index calls; this is load-bearing for the claimed performance advantage over nested baselines.
  3. [Evaluation] The abstract and evaluation sections assert superior performance and scalability on real-world datasets but supply no quantitative metrics, error bars, dataset sizes, or direct comparisons to specific baselines (e.g., R-tree + HNSW), preventing independent assessment of the central claims.
minor comments (2)
  1. [System Overview] Notation for the hierarchical grid partitioning and cell adjacency could be clarified with an additional diagram in the system overview.
  2. [Query Execution] The paper would benefit from explicit pseudocode or a small example walk-through of the stitching process for a sample polygonal query.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough review and constructive suggestions. We address each of the major comments below and outline the revisions we intend to incorporate in the updated manuscript.

read point-by-point responses

  1. Referee: [Query Execution] The description of the stitching algorithm (how cross-cell edges or virtual links are identified and materialized at query time, and whether it uses boundary-point matching or k-NN links) is insufficient to evaluate whether global connectivity is restored for arbitrary (non-rectangular) query regions without missing paths or repeated stitching steps.

    Authors: We agree that a more detailed exposition of the stitching algorithm is necessary for full reproducibility and evaluation. In the revised manuscript, we will provide pseudocode and a step-by-step explanation of how cross-cell virtual links are identified using boundary-point matching combined with k-NN searches between adjacent cells. We will also analyze how this mechanism ensures no missing paths for non-rectangular regions by dynamically including all intersecting cells and their connections, avoiding repeated stitching through caching of stitched subgraphs where possible. revision: yes

  2. Referee: [Query Execution] No analysis is provided of typical numbers of cells stitched per query, resulting graph diameter changes, or overhead measurements relative to the savings from avoiding multiple sub-index calls; this is load-bearing for the claimed performance advantage over nested baselines.

    Authors: The current manuscript focuses on overall query performance but lacks a dedicated breakdown of stitching costs. We will add this analysis in the evaluation section, including empirical data on the average number of cells stitched per query across different spatial filter complexities, measured changes in effective graph diameter, and a cost-benefit comparison showing how the single-pass traversal overhead is offset by avoiding multiple index invocations compared to nested R-tree plus vector index approaches. revision: yes

  3. Referee: [Evaluation] The abstract and evaluation sections assert superior performance and scalability on real-world datasets but supply no quantitative metrics, error bars, dataset sizes, or direct comparisons to specific baselines (e.g., R-tree + HNSW), preventing independent assessment of the central claims.

    Authors: We acknowledge the need for more explicit quantitative reporting. We will revise the abstract to highlight key performance numbers and ensure the evaluation section provides dataset sizes, error bars from multiple runs, and direct comparisons against baselines such as R-tree combined with HNSW. This will allow for better independent assessment of the scalability and performance advantages. revision: yes

Circularity Check

0 steps flagged

No circularity: engineering system design with no derivations, predictions, or self-referential fits

full rationale

The paper presents CubeGraph as a hierarchical grid partitioning scheme with per-cell vector graphs and on-the-fly stitching for hybrid queries. No equations, fitted parameters, or first-principles derivations are claimed. The central mechanism (dynamic stitching to restore connectivity) is described as an algorithmic choice, not derived from prior results or self-citations. Evaluations are empirical on real-world datasets, with no 'predictions' that reduce to inputs by construction. Self-citation is absent from the provided text. This matches the default expectation of no significant circularity for a system-design contribution.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The abstract provides no explicit free parameters, axioms, or invented entities beyond the high-level system description; the CubeGraph framework itself is the proposed artifact.

pith-pipeline@v0.9.0 · 5499 in / 1079 out tokens · 50914 ms · 2026-05-10T17:28:36.438582+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

61 extracted references · 61 canonical work pages

  1. [1]

    Zekai Wu, Jiabao Jin, Peng Cheng, Xiaoyao Zhong, Lei Chen, Yongxin Tong, Zhitao Shen, Jingkuan Song, Heng Tao Shen, Xuemin Lin.arXiv preprint arXiv:2603.21710(2026)

    2026. Zekai Wu, Jiabao Jin, Peng Cheng, Xiaoyao Zhong, Lei Chen, Yongxin Tong, Zhitao Shen, Jingkuan Song, Heng Tao Shen, Xuemin Lin.arXiv preprint arXiv:2603.21710(2026). https://arxiv.org/abs/2603.21710

    work page arXiv 2026

  2. [2]

    Md Mahbub Alam, Luis Torgo, and Albert Bifet. 2022. A survey on spatio- temporal data analytics systems.Comput. Surveys54, 10s (2022), 1–38

    work page 2022

  3. [3]

    Fabien André, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. 2015. Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan.Proceedings of the VLDB Endowment9, 4 (2015)

    work page 2015

  4. [4]

    Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. 2020. ANN- Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems87 (2020), 101374

    work page 2020

  5. [5]

    Artem Babenko and Victor Lempitsky. 2014. Additive quantization for extreme vector compression. InProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 931–938

    work page 2014

  6. [6]

    Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger

    work page

  7. [7]

    InProceedings of the 1990 ACM SIGMOD international conference on Management of data

    The R*-tree: An efficient and robust access method for points and rectangles. InProceedings of the 1990 ACM SIGMOD international conference on Management of data. 322–331

    work page 1990

  8. [8]

    Yuzheng Cai, Jiayang Shi, Yizhuo Chen, and Weiguo Zheng. 2024. Navigating La- bels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search.Proceedings of the ACM on Management of Data2, 6 (2024), 1–27

    work page 2024

  9. [9]

    Joshua Engels, Benjamin Landrum, Shangdi Yu, Laxman Dhulipala, and Julian Shun. 2024. Approximate Nearest Neighbor Search with Window Filters.ICML 2024(2024)

    work page 2024

  10. [10]

    Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph.Proc. VLDB Endow.12, 5 (2019), 461–474

    work page 2019

  11. [11]

    Jianyang Gao and Cheng Long. 2023. High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations. Proc. ACM Manag. Data1, 2 (2023), 137:1–137:27. https://doi.org/10.1145/3589282

    work page doi:10.1145/3589282 2023

  12. [12]

    Jianyang Gao and Cheng Long. 2024. RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search.Proceedings of the ACM on Management of Data2, 3 (2024), 1–27

    work page 2024

  13. [13]

    Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2014. Optimized Product Quantization.IEEE Trans. Pattern Anal. Mach. Intell.36, 4 (2014), 744–755

    work page 2014

  14. [14]

    Aristides Gionis, Piotr Indyk, Rajeev Motwani, et al. 1999. Similarity search in high dimensions via hashing. InVldb, Vol. 99. 518–529

    work page 1999

  15. [15]

    Siddharth Gollapudi, Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy, Nikit Begwani, Swapnil Raz, Yiyong Lin, Yin Zhang, Neelam Mahapatro, Premku- mar Srinivasan, et al. 2023. Filtered-diskann: Graph algorithms for approximate nearest neighbor search with filters. InProceedings of the ACM Web Conference

    work page 2023

  16. [16]

    Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. InProceedings of the thirtieth annual ACM symposium on Theory of computing. 604–613

    work page 1998

  17. [17]

    Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. Diskann: Fast accurate billion-point nearest neighbor search on a single node.Advances in Neural Information Processing Systems32 (2019)

    work page 2019

  18. [18]

    Mengxu Jiang, Zhi Yang, Fangyuan Zhang, Guanhao Hou, Jieming Shi, Wenchao Zhou, Feifei Li, and Sibo Wang. 2025. DIGRA: A Dynamic Graph Indexing for Approximate Nearest Neighbor Search with Range Filter.Proceedings of the ACM on Management of Data3, 3 (2025), 1–26

    work page 2025

  19. [19]

    Chenzhe Jin, Yunan Zhang, Jiayi Liu, and Jianguo Wang. 2026. Efficient Vector Index Merging in Vector Databases. 4, 1 (2026). https://doi.org/10.1145/3786645

    work page doi:10.1145/3786645 2026

  20. [20]

    Liuchang Jing, Mingyu Yang, Lei Li, Jianbin Qin, and Wei Wang. 2026. Mul- tiple Index Merge for Approximate Nearest Neighbor Search.arXiv preprint arXiv:2602.17099(2026)

    work page arXiv 2026

  21. [21]

    Leonardo Kuffo, Elena Krippner, and Peter Boncz. 2025. PDX: A data layout for vector similarity search.Proceedings of the ACM on Management of Data3, 3 (2025), 1–26

    work page 2025

  22. [22]

    Binhong Li, Xiao Yan, and Shangqi Lu. 2025. Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search.arXiv preprint arXiv:2510.05975 (2025)

    work page arXiv 2025

  23. [23]

    Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. 2020. Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement.IEEE Trans. Knowl. Data Eng. 32, 8 (2020), 1475–1488

    work page 2020

  24. [24]

    Zhaoheng Li, Silu Huang, Wei Ding, Yongjoo Park, and Jianjun Chen. 2025. SIEVE: Effective Filtered Vector Search with Collection of Indexes.Proceedings of the VLDB Endowment18, 11 (2025), 4723–4736

    work page 2025

  25. [25]

    Anqi Liang, Pengcheng Zhang, Bin Yao, Zhongpu Chen, Yitong Song, and Guangxu Cheng. 2024. UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search.Proceedings of the VLDB Endowment18, 4 (Dec. 2024), 1118–1130. https://doi.org/10.14778/3717755.3717770

    work page doi:10.14778/3717755.3717770 2024

  26. [26]

    Kejing Lu, Mineichi Kudo, Chuan Xiao, and Yoshiharu Ishikawa. 2021. HVS: Hi- erarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search.Proc. VLDB Endow.15, 2 (2021), 246–258

    work page 2021

  27. [27]

    Jiarui Luo, Miao Qiao, Chaoji Zuo, and Dong Deng. 2025. Tag-Filtered Approx- imate Nearest Neighbor Search. In2025 IEEE 41st International Conference on Data Engineering (ICDE). IEEE, 3642–3654

    work page 2025

  28. [28]

    Yu A Malkov and Dmitry A Yashunin. [n. d.]. hnswlib. https://github.com/ nmslib/hnswlib

    work page

  29. [29]

    Malkov and Dmitry A

    Yury A. Malkov and Dmitry A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs.IEEE Trans. Pattern Anal. Mach. Intell.42, 4 (2020), 824–836

    work page 2020

  30. [30]

    Jason Mohoney, Anil Pacaci, Shihabur Rahman Chowdhury, Ali Mousavi, Ihab F Ilyas, Umar Farooq Minhas, Jeffrey Pound, and Theodoros Rekatsinas. 2023. High-throughput vector similarity search in knowledge graphs.Proceedings of the ACM on Management of Data1, 2 (2023), 1–25

    work page 2023

  31. [31]

    James Jie Pan, Jianguo Wang, and Guoliang Li. 2024. Vector Database Manage- ment Techniques and Systems. InCompanion of the 2024 International Conference on Management of Data. 597–604

    work page 2024

  32. [32]

    Liana Patel, Peter Kraft, Carlos Guestrin, and Matei Zaharia. 2024. Acorn: Per- formant and predicate-agnostic search over vector embeddings and structured data.Proceedings of the ACM on Management of Data2, 3 (2024), 1–27

    work page 2024

  33. [33]

    Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang, and Jianliang Xu. 2023. Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases. Proc. ACM Manag. Data1, 1 (2023), 54:1–54:27. https://doi.org/10.1145/3588908

    work page doi:10.1145/3588908 2023

  34. [34]

    Zhencan Peng, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. 2025. Dynamic Range-Filtering Approximate Nearest Neighbor Search.Proceedings of the VLDB Endowment18, 10 (June 2025), 3256–3268. https://doi.org/10.14778/ 3748191.3748193

    work page arXiv 2025

  35. [35]

    Parikshit Ram and Kaushik Sinha. 2019. Revisiting kd-tree for nearest neighbor search. InProceedings of the 25th acm sigkdd international conference on knowledge discovery & data mining. 1378–1388

    work page 2019

  36. [36]

    Yitong Song, Bin Yao, Zhida Chen, Xin Yang, Jiong Xie, Feifei Li, and Mengshi Chen. 2025. Efficient top-k spatial-range-constrained approximate nearest neigh- bor search on geo-tagged high-dimensional vectors.The VLDB Journal34, 1 (2025), 14

    work page 2025

  37. [37]

    Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xi- angyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, et al. 2021. Milvus: A purpose-built vector data management system. InProceedings of the 2021 International Conference on Management of Data. 2614–2627

    work page 2021

  38. [38]

    Mengzhao Wang, Lingwei Lv, Xiaoliang Xu, Yuxiang Wang, Qiang Yue, and Jiongkang Ni. 2022. Navigable proximity graph-driven native hybrid queries with structured and unstructured constraints.arXiv preprint arXiv:2203.13601 (2022)

    work page arXiv 2022

  39. [39]

    Mengzhao Wang, Haotian Wu, Xiangyu Ke, Yunjun Gao, Yifan Zhu, and Wenchao Zhou. 2025. Accelerating Graph Indexing for ANNS on Modern CPUs.arXiv preprint arXiv:2502.18113(2025)

    work page arXiv 2025

  40. [40]

    Mengzhao Wang, Weizhi Xu, Xiaomeng Yi, Songlin Wu, Zhangyang Peng, Xi- angyu Ke, Yunjun Gao, Xiaoliang Xu, Rentong Guo, and Charles Xie. 2024. Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High- Dimensional Vector Similarity Search on Data Segment.Proc. ACM Manag. Data2, 1 (2024), V2mod014:1–V2mod014:27. https://doi.org/10.1145/3639269

    work page doi:10.1145/3639269 2024

  41. [41]

    Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A com- prehensive survey and experimental comparison of graph-based approximate nearest neighbor search.Proceedings of the VLDB Endowment14, 11 (2021), 1964–1978

    work page 2021

  42. [42]

    Yuxiang Wang, Ziyuan He, Yongxin Tong, Zimu Zhou, and Yiman Zhong. 2025. Timestamp Approximate Nearest Neighbor Search over High-Dimensional Vec- tor Data. In2025 IEEE 41st International Conference on Data Engineering (ICDE). IEEE, 3043–3055

    work page 2025

  43. [43]

    Ziqi Wang, Jingzhe Zhang, and Wei Hu. 2025. WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data3, 6 (2025), 1–27

    work page 2025

  44. [44]

    Chuangxian Wei, Bin Wu, Sheng Wang, Renjie Lou, Chaoqun Zhan, Feifei Li, and Yuanzhe Cai. 2020. AnalyticDB-V: a hybrid analytical engine towards query fusion for structured and unstructured data.Proceedings of the VLDB Endowment 13, 12 (2020), 3152–3165

    work page 2020

  45. [45]

    Wenxuan Xia, Mingyu Yang, Wentao Li, and Wei Wang. 2026. Filtered Approxi- mate Nearest Neighbor Search Cost Estimation.arXiv preprint arXiv:2602.06721 (2026)

    work page arXiv 2026

  46. [46]

    Jiadong Xie, Jeffrey Xu Yu, Siyi Teng, and Yingfan Liu. 2025. Beyond Vector Search: Querying With and Without Predicates.Proceedings of the ACM on Management of Data3, 6 (2025), 1–26

    work page 2025

  47. [47]

    Yuexuan Xu, Jianyang Gao, Yutong Gou, Cheng Long, and Christian S Jensen

    work page

  48. [48]

    iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search.arXiv preprint arXiv:2409.02571(2024)

    work page arXiv 2024

  49. [49]

    Ming Yang, Yuzheng Cai, and Weiguo Zheng. 2025. Hi-PNG: Efficient Interval- Filtering ANNS via Hierarchical Interval Partition Navigating Graph. InPro- ceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 2. 3518–3529. 13

    work page 2025

  50. [50]

    Mingyu Yang, Wentao Li, Jiabao Jin, Xiaoyao Zhong, Xiangyu Wang, Zhitao Shen, Wei Jia, and Wei Wang. 2024. Effective and General Distance Computation for Approximate Nearest Neighbor Search.arXiv preprint arXiv:2404.16322(2024)

    work page arXiv 2024

  51. [51]

    Mingyu Yang, Wentao Li, Zhitao Shen, Chuan Xiao, and Wei Wang. 2025. ESG: Elastic Graphs for Range-Filtering Approximate k-Nearest Neighbor Search. arXiv preprint arXiv:2504.04018(2025)

    work page arXiv 2025

  52. [52]

    Mingyu Yang, Wentao Li, and Wei Wang. 2024. Fast High-dimensional Approx- imate Nearest Neighbor Search with Efficient Index Time and Space.arXiv preprint arXiv:2411.06158(2024)

    work page arXiv 2024

  53. [53]

    2026.Technical Report

    Mingyu Yang, Wentao Li, and Wei Wang. 2026.Technical Report. https://github. com/mingyu-hkustgz/CubeGraph/blob/main/technical_report.pdf

    work page 2026

  54. [54]

    Mingyu Yang, Wenxuan Xia, Wentao Li, Raymond Chi-Wing Wong, and Wei Wang. 2025. Elastic Index Select for Label-Hybrid Search in Vector Database. arXiv preprint arXiv:2505.03212(2025)

    work page arXiv 2025

  55. [55]

    Ziqi Yin, Jianyang Gao, Pasquale Balsebre, Gao Cong, and Cheng Long. 2025. DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph. Proceedings of the ACM on Management of Data3, 1 (2025), 1–28

    work page 2025

  56. [56]

    Yuanhang Yu, Dawei Cheng, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2026. Efficient Approximate Nearest Neighbor Search under Multi-Attribute Range Filter.arXiv preprint arXiv:2602.15488(2026)

    work page arXiv 2026

  57. [57]

    Fangyuan Zhang, Mengxu Jiang, Guanhao Hou, Jieming Shi, Hua Fan, Wenchao Zhou, Feifei Li, and Sibo Wang. 2025. Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search.Proceedings of the ACM on Management of Data3, 3 (2025), 1–26

    work page 2025

  58. [58]

    Qianxi Zhang, Shuotao Xu, Qi Chen, Guoxin Sui, Jiadong Xie, Zhizhen Cai, Yaoqi Chen, Yinxuan He, Yuqing Yang, Fan Yang, et al. 2023. {VBASE}: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity. In17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23). 377–395

    work page 2023

  59. [59]

    Xiaoyao Zhong, Haotian Li, Jiabao Jin, Mingyu Yang, Deming Chu, Xiangyu Wang, Zhitao Shen, Wei Jia, George Gu, Yi Xie, et al. 2025. VSAG: An Optimized Search Framework for Graph-based Approximate Nearest Neighbor Search.arXiv preprint arXiv:2503.17911(2025)

    work page arXiv 2025

  60. [60]

    Chaoji Zuo, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. 2024. SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search.Pro- ceedings of the ACM on Management of Data2, 1 (2024), 1–26. 14 Appendix A.1 Proof of Proposition 1 (Optimal Layer Selection) We establish the cube-count bound and then justify the optimality of𝑤 ℓ∗ ≈𝑟against...

    work page 2024

  61. [61]

    With optimal layer selection where 𝑤 ℓ∗ ≈ 100, the rectangle intersects at most3 × 2 = 6 cubes (3along the long dimension,2along the short dimension since 𝑟min = 10 <𝑤 ℓ∗)

    in a metadata space of side length 𝑆= 1000. With optimal layer selection where 𝑤 ℓ∗ ≈ 100, the rectangle intersects at most3 × 2 = 6 cubes (3along the long dimension,2along the short dimension since 𝑟min = 10 <𝑤 ℓ∗). The rectangle has area1000, and the union of 6cubes has area approximately6 × 1002 = 60,000. The elastic factor is 𝑒≈ 1000/60,000 ≈ 0.017, m...

    work page