arxiv: 2603.12913 · v2 · submitted 2026-03-13 · 💻 cs.DB

Recognition: 1 theorem link

· Lean Theorem

RNSG: A Range-Aware Graph Index for Efficient Range-Filtered Approximate Nearest Neighbor Search

Zhiqiu Zou , Ziqi Yin , Rong-Hua Li , Hongchao Qin , Qiangqiang Dai , Guoren Wang

Authors on Pith no claims yet

Pith reviewed 2026-05-15 11:46 UTC · model grok-4.3

classification 💻 cs.DB

keywords range-filtered approximate nearest neighborgraph indexrange queryrelative neighborhood graphmonotonic searchbeam searchvector database index

0 comments

The pith

A single graph index built on range-aware relative neighborhoods supports efficient search for any attribute range in approximate nearest neighbor queries.

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

The paper establishes a theoretical range-aware relative neighborhood graph that incorporates both vector similarity and numerical attribute values. It proves this structure allows correct beam-search retrieval while ensuring that the subgraph induced by any query range remains a valid index. These properties eliminate the need to build separate graphs for different ranges. A practical approximation called RNSG is then constructed and shown to deliver faster queries with smaller indexes and lower build costs on real datasets.

Core claim

The RRNG is defined so that an object connects to another when they are mutual nearest neighbors under a combined spatial-attribute distance; this yields monotonic search-ability for correct beam search and structural heredity so every range-induced subgraph stays a valid RRNG, allowing one index to answer all RFANN queries.

What carries the argument

The range-aware relative neighborhood graph (RRNG), whose edges encode mutual nearest-neighbor relations that respect both vector distance and numerical attribute proximity.

If this is right

Only one index needs to be built and stored regardless of how many different ranges are queried.
Query processing reduces to extracting the induced subgraph for the given range and running standard beam search on it.
Index construction time and memory drop compared with methods that pre-build multiple range-specific graphs.
Query throughput improves while recall stays comparable to prior state-of-the-art approaches on real vector-plus-attribute collections.

Where Pith is reading between the lines

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

The same heredity property might let the index support sliding-window or multi-dimensional range filters without rebuilding.
If the approximation quality can be bounded theoretically, the method could be adapted to other graph-based ANN indexes.
Dynamic updates that maintain the RRNG properties would remove the need for periodic full rebuilds in changing datasets.

Load-bearing premise

The practical RNSG approximation preserves monotonic search-ability and structural heredity well enough on real data to keep both correctness and claimed speed.

What would settle it

An experiment in which beam search on the RNSG subgraph for some range returns a neighbor farther than the true nearest neighbor inside that range.

Figures

Figures reproduced from arXiv: 2603.12913 by Guoren Wang, Hongchao Qin, Qiangqiang Dai, Rong-Hua Li, Zhiqiu Zou, Ziqi Yin.

**Figure 3.** Figure 3: Differences between MRNG and RRNG, node labels denote numeric attribute values. The RRNG tends to replace edges (e.g., the edge (1, 4)) with large attribute differences with those having smaller attribute differences (e.g., the edges (1, 2) and (2, 4)). In the MRNG, 1 → 4 is a monotonic path, while in the RRNG 1 → 2 → 4 is a monotonic path. The RRNG is a directed graph 𝐺 = (𝑉 , 𝐸) whose outgoing edges sati… view at source ↗

**Figure 4.** Figure 4: Illustration of the hereditary property of RRNG, [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗

**Figure 5.** Figure 5: Recall-QPS curves on six datasets under mixed, 1%, 10%, and 50% selectivity workloads (upper and right is better). [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗

**Figure 6.** Figure 6: Construction cost and deployed index size on the original benchmark datasets. Top: index construction time, where [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗

**Figure 7.** Figure 7: Parameter sensitivity on SIFT1M. The top row varies [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗

**Figure 9.** Figure 9: Additional robustness and extension experiments: [PITH_FULL_IMAGE:figures/full_fig_p012_9.png] view at source ↗

**Figure 11.** Figure 11: Illustration of entry node set generation. [PITH_FULL_IMAGE:figures/full_fig_p017_11.png] view at source ↗

**Figure 12.** Figure 12: One-sided prefix-range query experiment on [PITH_FULL_IMAGE:figures/full_fig_p018_12.png] view at source ↗

**Figure 13.** Figure 13: Large-scale recall-QPS curves on SpaceV10M. RNSG [PITH_FULL_IMAGE:figures/full_fig_p018_13.png] view at source ↗

read the original abstract

Range-filtered approximate nearest neighbor (RFANN) search is a fundamental operation in modern data systems. Given a set of objects, each with a vector and a numerical attribute, an RFANN query retrieves the nearest neighbors to a query vector among those objects whose numerical attributes fall within the range specified by the query. Existing state-of-the-art methods for RFANN search often require constructing multiple range-specific graph indexes to achieve high query performance, which incurs significant indexing overhead. To address this, we first establish a novel graph indexing theory, the range-aware relative neighborhood graph (RRNG), which jointly considers spatial and attribute proximity. We prove that the RRNG satisfies two crucial properties: (1) monotonic search-ability, which ensures correct nearest neighbor retrieval via beam search; and (2) structural heredity, which guarantees that any range-induced subgraph remains a valid RRNG, thus enabling efficient search with a single graph index. Based on this theoretical foundation, we propose a new graph index called RNSG as a practical solution that efficiently approximates RRNG. We develop fast algorithms for both constructing the RNSG index and processing RFANN queries with it. Extensive experiments on five real-world datasets show that RNSG achieves significantly higher query performance with a more compact index and lower construction cost than existing state-of-the-art methods.

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.

Desk Editor's Note private letter to a colleague

RNSG gives a single-index method for range-filtered ANN via new RRNG theory with two properties, but the practical approximation lacks formal preservation proofs and rests on experiments.

read the letter

The main point is that this paper defines a range-aware relative neighborhood graph (RRNG) with two properties that support using one index for all range queries instead of building separate graphs per range. They prove monotonic search-ability so beam search retrieves correct neighbors, and structural heredity so any range-induced subgraph stays a valid RRNG. RNSG is their fast-to-build approximation of that ideal graph, with new construction and query algorithms on top of it. Experiments on five datasets report better query times, smaller indexes, and lower build costs than prior methods that use multiple indexes. That single-index angle is the practical win for database systems handling filtered vector search. The soft spot is exactly where the stress-test note points: the proofs apply only to exact RRNG, and nothing in the abstract or claims shows a theorem or bound that the specific approximation rules in RNSG preserve monotonic search-ability or heredity. If the neighbor selection or pruning steps break either property on some range or dataset, the correctness and efficiency arguments rest entirely on the empirical numbers holding up. I'd want to check the construction details and any tests for property violations in the full text. This work is for people building or studying graph indexes for approximate nearest neighbor search with attribute filters. A reader focused on vector databases or filtered ANN would get concrete value from the theory and the reported speedups. It deserves peer review because the core idea is clean, the experiments are on real data, and the single-index claim is worth verifying in detail even if the approximation needs tighter analysis.

Referee Report

1 major / 2 minor

Summary. The paper introduces the range-aware relative neighborhood graph (RRNG) as a theoretical foundation for range-filtered approximate nearest neighbor (RFANN) search. It proves that RRNG satisfies monotonic search-ability (enabling correct beam search) and structural heredity (ensuring range-induced subgraphs remain valid RRNGs). Based on this, it proposes RNSG as a practical approximation with fast construction and query algorithms, claiming that a single index suffices for all ranges and delivers superior query performance, compactness, and lower construction cost than prior methods on five real-world datasets.

Significance. If the RNSG approximation preserves the proven RRNG properties, the work would meaningfully reduce indexing overhead in vector databases by replacing multiple range-specific indexes with one graph, while maintaining correctness via beam search. The combination of a new graph-theoretic foundation with empirical gains on real data positions it as a practical advance for RFANN workloads.

major comments (1)

[§3 and §4] §3 (RRNG properties) and §4 (RNSG construction): Theorems establishing monotonic search-ability and structural heredity are stated only for the exact RRNG. No subsequent theorem, lemma, or approximation bound shows that the neighbor-selection and pruning rules used to build RNSG preserve either property for beam search or for arbitrary range-induced subgraphs. Because the single-index claim rests on these properties holding for the deployed index, the absence of such a guarantee makes the correctness argument rest entirely on the empirical section.

minor comments (2)

[Table 1] Table 1 (dataset statistics): the reported index sizes and construction times for RNSG versus baselines would be clearer if accompanied by the exact parameter settings (e.g., beam width, pruning threshold) used for each competitor.
[Figure 3] Figure 3 (query latency vs. recall): the curves for different range widths are plotted without error bars or mention of the number of query repetitions, making it difficult to judge statistical significance of the reported speedups.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. We address the major comment point by point below.

read point-by-point responses

Referee: [§3 and §4] §3 (RRNG properties) and §4 (RNSG construction): Theorems establishing monotonic search-ability and structural heredity are stated only for the exact RRNG. No subsequent theorem, lemma, or approximation bound shows that the neighbor-selection and pruning rules used to build RNSG preserve either property for beam search or for arbitrary range-induced subgraphs. Because the single-index claim rests on these properties holding for the deployed index, the absence of such a guarantee makes the correctness argument rest entirely on the empirical section.

Authors: We agree that the monotonic search-ability and structural heredity theorems in §3 are stated only for the exact RRNG. RNSG in §4 is explicitly introduced as an efficient approximation that applies neighbor-selection and pruning rules derived from the RRNG definition but relaxed for scalability. No formal approximation bound or lemma is provided showing that these rules preserve the two properties exactly. The single-index claim therefore rests on the empirical observation that the resulting RNSG remains sufficiently close to RRNG for beam search to succeed on range-induced subgraphs. We will revise the manuscript to make this distinction explicit, add a short discussion in §4 on the heuristic rationale for property preservation, and clarify that practical correctness is supported by the experimental results rather than a formal guarantee. revision: partial

Circularity Check

0 steps flagged

No circularity: RRNG properties derived from definition; RNSG approximation does not reduce claims to inputs

full rationale

The paper first defines the RRNG construction rule that jointly encodes spatial and attribute proximity, then proves monotonic search-ability and structural heredity directly from that definition (no fitted parameters or self-citation chains are invoked to establish the two properties). RNSG is introduced afterward as a practical approximation with its own fast construction and query algorithms; the single-index claim follows from the proven heredity property of the ideal RRNG rather than from any renaming, self-referential prediction, or load-bearing self-citation. No step equates a derived quantity to its own input by construction, and the derivation remains self-contained against external graph-indexing benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 2 invented entities

The central claim rests on the newly introduced RRNG definition and the two proved properties that enable single-index search; RNSG is presented as a practical approximation whose fidelity to the ideal graph is not quantified in the abstract.

axioms (1)

domain assumption RRNG satisfies monotonic search-ability and structural heredity.
These two properties are stated as proved and form the load-bearing foundation for using a single index.

invented entities (2)

RRNG no independent evidence
purpose: Graph that jointly encodes vector proximity and attribute proximity for range-filtered search.
Newly defined structure whose properties are proved in the paper.
RNSG no independent evidence
purpose: Practical approximation to RRNG enabling fast construction and queries.
Proposed implementation whose approximation error is not detailed in the abstract.

pith-pipeline@v0.9.0 · 5556 in / 1343 out tokens · 36887 ms · 2026-05-15T11:46:23.355645+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We prove that the RRNG satisfies two crucial properties: (1) monotonic search-ability... and (2) structural heredity, which guarantees that any range-induced subgraph remains a valid RRNG

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

75 extracted references · 75 canonical work pages · 4 internal anchors

[1]

Cecilia Aguerrebere, Ishwar Singh Bhati, Mark Hildebrand, Mariano Tepper, and Theodore Willke. 2023. Similarity Search in the Blink of an Eye with Compressed Indices.Proceedings of the VLDB Endowment16, 11 (2023), 3433–3446

work page 2023
[2]

Fabien André, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. 2016. Cache locality is not enough: High-performance nearest neighbor search with product quantization fast scan. In42nd International Conference on Very Large Data Bases, Vol. 9. 12

work page 2016
[3]

Akhil Arora, Sakshi Sinha, Piyush Kumar, and Arnab Bhattacharya. 2018. HD- Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces.Proc. VLDB Endow.11, 8 (2018), 906–919

work page 2018
[4]

Sunil Arya and David M Mount. 1993. Approximate nearest neighbor queries in fixed dimensions.. InSODA, Vol. 93. 271–280

work page 1993
[5]

Martin Aumüller, Erik Bernhardsson, and Alexander John Faithfull. 2020. ANN- Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Inf. Syst.87 (2020)

work page 2020
[6]

Ilias Azizi, Karima Echihabi, and Themis Palpanas. 2023. Elpis: Graph-based similarity search for scalable data science.Proceedings of the VLDB Endowment 16, 6 (2023), 1548–1559

work page 2023
[7]

Ilias Azizi, Karima Echihabi, and Themis Palpanas. 2025. Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art.Proc. ACM Manag. Data3, 1 (2025), 43:1–43:31

work page 2025
[8]

nearest neighbor

Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, and Uri Shaft. 1999. When is “nearest neighbor” meaningful?. InICDT. 217–235

work page 1999
[9]

Alina Beygelzimer, Sham Kakade, and John Langford. 2006. Cover trees for nearest neighbor. InICML. 97–104

work page 2006
[10]

Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021. Spann: Highly-efficient billion-scale approximate nearest neighborhood search.Advances in Neural Information Processing Systems34 (2021), 5199–5212

work page 2021
[11]

Yannis Chronis, Helena Caminal, Yannis Papakonstantinou, Fatma Özcan, and Anastasia Ailamaki. 2025. Filtered Vector Search: State-of-the-Art and Research Opportunities.Proceedings of the VLDB Endowment18, 12 (2025), 5488–5492

work page 2025
[12]

Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. 2004. Locality- sensitive hashing scheme based on p-stable distributions. InProceedings of the twentieth annual symposium on Computational geometry. 253–262

work page 2004
[13]

Mark De Berg, Otfried Cheong, Marc Van Kreveld, and Mark Overmars. 2008. Computational geometry: algorithms and applications

work page 2008
[14]

Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun

Magdalen Dobson, Zheqi Shen, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. 2023. Scaling Graph-Based ANNS Al- gorithms to Billion-Size Datasets: A Comparative Analysis.CoRRabs/2305.04359 (2023)

work page arXiv 2023
[15]

Wei Dong, Moses Charikar, and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures. InWWW. 577–586

work page 2011
[16]

Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2024. The faiss library.arXiv preprint arXiv:2401.08281(2024)

work page internal anchor Pith review Pith/arXiv arXiv 2024
[17]

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

work page 2024
[18]

Steven Fortune. 2004. Voronoi Diagrams and Delaunay Triangulations. In Handbook of Discrete and Computational Geometry, Second Edition. 513–528

work page 2004
[19]

Cong Fu, Changxu Wang, and Deng Cai. 2021. High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility.IEEE Transactions on Pattern Analysis and Machine Intelligence44, 8 (2021), 4139–4150

work page 2021
[20]

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
[21]

Junhao Gan, Jianlin Feng, Qiong Fang, and Wilfred Ng. 2012. Locality-sensitive hashing scheme based on dynamic collision counting. InProceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012, Scottsdale, AZ, USA, May 20-24, 2012. 541–552

work page 2012
[22]

Jianyang Gao, Yutong Gou, Yuexuan Xu, Yongyi Yang, Cheng Long, and Raymond Chi-Wing Wong. 2025. Practical and asymptotically optimal quantization of high-dimensional vectors in euclidean space for approximate nearest neighbor search.Proceedings of the ACM on Management of Data3, 3 (2025), 1–26

work page 2025
[23]

Jianyang Gao and Cheng Long. 2024. Rabitq: Quantizing high-dimensional vectors with a theoretical error bound for approximate nearest neighbor search. Proc. ACM Manag. Data2, 3 (2024), 1–27

work page 2024
[24]

Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized product quantization.IEEE transactions on pattern analysis and machine intelligence36, 4 (2013), 744–755

work page 2013
[25]

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. InWWW. 3406–3416. 13

work page 2023
[26]

Yunchao Gong, Svetlana Lazebnik, Albert Gordo, and Florent Perronnin. 2012. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval.IEEE transactions on pattern analysis and machine intelligence35, 12 (2012), 2916–2929

work page 2012
[27]

Rentong Guo, Xiaofan Luan, Long Xiang, Xiao Yan, Xiaomeng Yi, Jigao Luo, Qianya Cheng, Weizhi Xu, Jiarui Luo, Frank Liu, Zhenshan Cao, Yanliang Qiao, Ting Wang, Bo Tang, and Charles Xie. 2022. Manu: A Cloud Native Vector Database Management System.Proceedings of the VLDB Endowment15, 12 (2022), 3548–3561

work page 2022
[28]

Ben Harwood and Tom Drummond. 2016. Fanng: Fast approximate nearest neighbour graphs. InCVPR. 5713–5722

work page 2016
[29]

Jae-Pil Heo, Youngwoon Lee, Junfeng He, Shih-Fu Chang, and Sung-Eui Yoon

work page
[30]

Pattern Anal

Spherical Hashing: Binary Code Embedding with Hyperspheres.IEEE Trans. Pattern Anal. Mach. Intell.37, 11 (2015), 2304–2316

work page 2015
[31]

Qiang Huang, Jianlin Feng, Yikai Zhang, Qiong Fang, and Wilfred Ng. 2015. Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search.Proc. VLDB Endow.9, 1 (2015), 1–12

work page 2015
[32]

Piotr Indyk and Rajeev Motwani. 1998. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. InSTOC. 604–613

work page 1998
[33]

Hosagrahar V Jagadish, Beng Chin Ooi, Kian-Lee Tan, Cui Yu, and Rui Zhang

work page
[34]

iDistance: An adaptive B+-tree based indexing method for nearest neighbor search.ACM Transactions on Database Systems (TODS)30, 2 (2005), 364–397

work page 2005
[35]

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 pro- cessing Systems32 (2019)

work page 2019
[36]

Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization for nearest neighbor search.IEEE transactions on pattern analysis and machine intelligence33, 1 (2010), 117–128

work page 2010
[37]

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.Proc. ACM Manag. Data3, 3 (2025), 1–26

work page 2025
[38]

Joseph B Kruskal. 1956. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.Proceedings of the American Mathematical society 7, 1 (1956), 48–50

work page 1956
[39]

Kankanhalli, and Anthony K

Yifan Lei, Qiang Huang, Mohan S. Kankanhalli, and Anthony K. H. Tung. 2020. Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring. In Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020. 2589– 2599

work page 2020
[40]

Hui Li, Shiyuan Deng, Xiao Yan, Xiangyu Zhi, and James Cheng. 2025. SAQ: Push- ing the Limits of Vector Quantization through Code Adjustment and Dimension Segmentation.arXiv preprint arXiv:2509.12086(2025)

work page arXiv 2025
[41]

Jie Li, Haifeng Liu, Chuanghua Gui, Jianyu Chen, Zhenyuan Ni, Ning Wang, and Yuan Chen. 2018. The design and implementation of a real time visual search system on JD E-commerce platform. InProceedings of the 19th International Middleware Conference Industry. 9–16

work page 2018
[42]

Jinfeng Li, Xiao Yan, Jie Zhang, An Xu, James Cheng, Jie Liu, Kelvin Kai Wing Ng, and Ti-Chung Cheng. 2018. A General and Efficient Querying Method for Learning to Hash. InProceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15,

work page 2018
[43]

Mocheng Li, Xiao Yan, Baotong Lu, Yue Zhang, James Cheng, and Chenhao Ma

work page
[44]

ACM Manag

Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study.Proc. ACM Manag. Data(2026)

work page 2026
[45]

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 Transactions on Knowl- edge and Data Engineering32, 8 (2020), 1475–1488

work page 2020
[46]

Anqi Liang, Pengcheng Zhang, Bin Yao, Zhongpu Chen, Yitong Song, and Guangxu Cheng. 2024. UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search.Proc. VLDB Endow.18, 4 (2024), 1118–1130

work page 2024
[47]

Ying Liu, Dengsheng Zhang, Guojun Lu, and Wei-Ying Ma. 2007. A survey of content-based image retrieval with high-level semantics.Pattern recognition40, 1 (2007), 262–282

work page 2007
[48]

Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov

work page
[49]

Approximate nearest neighbor algorithm based on navigable small world graphs.Information Systems45 (2014), 61–68

work page 2014
[50]

Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs.IEEE Transactions on Pattern Analysis and Machine Intelligence42, 4 (2018), 824–836

work page 2018
[51]

Yusuke Matsui, Yusuke Uchida, Hervé Jégou, and Shin’ichi Satoh. 2018. A survey of product quantization.ITE Transactions on Media Technology and Applications 6, 1 (2018), 2–10

work page 2018
[52]

James Jie Pan, Jianguo Wang, and Guoliang Li. 2024. Survey of vector database management systems.VLDB J.33, 5 (2024), 1591–1615

work page 2024
[53]

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
[54]

Rodrigo Paredes and Edgar Chávez. 2005. Using thek-Nearest Neighbor Graph for Proximity Searching in Metric Spaces. InSPIRE (Lecture Notes in Computer Science), Vol. 3772. 127–138

work page 2005
[55]

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

work page 2024
[56]

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 (2025), 3256–3268

work page 2025
[57]

Ninh Pham and Tao Liu. 2022. Falconn++: A locality-sensitive filtering ap- proach for approximate nearest neighbor search.Advances in Neural Information Processing Systems35 (2022), 31186–31198

work page 2022
[58]

Jeffrey Pound, Floris Chabert, Arjun Bhushan, Ankur Goswami, Anil Pacaci, and Shihabur Rahman Chowdhury. 2025. MicroNN: An On-device Disk-resident Updatable Vector Database. InCompanion of SIGMOD. 608–621

work page 2025
[59]

Parikshit Ram and Kaushik Sinha. 2019. Revisiting kd-tree for nearest neighbor search. InKDD. 1378–1388

work page 2019
[60]

Yufei Tao, Ke Yi, Cheng Sheng, and Panos Kalnis. 2010. Efficient and Accurate Nearest Neighbor and Closest Pair Search in High-Dimensional Space.ACM Transactions on Database Systems35, 3 (2010), 20:1–20:46

work page 2010
[61]

Ertem Tuncel, Hakan Ferhatosmanoglu, and Kenneth Rose. 2002. VQ-index: an index structure for similarity searching in multimedia databases. InProceedings of the 10th ACM International Conference on Multimedia 2002, Juan les Pins, France, December 1-6, 2002. 543–552

work page 2002
[62]

Jingdong Wang, Heng Tao Shen, Jingkuan Song, and Jianqiu Ji. 2014. Hashing for similarity search: A survey.arXiv preprint arXiv:1408.2927(2014)

work page internal anchor Pith review Pith/arXiv arXiv 2014
[63]

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. InSIGMOD. 2614–2627

work page 2021
[64]

Jingdong Wang, Ting Zhang, Nicu Sebe, Heng Tao Shen, et al. 2017. A survey on learning to hash.IEEE transactions on pattern analysis and machine intelligence 40, 4 (2017), 769–790

work page 2017
[65]

Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A Com- prehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search.Proc. VLDB Endow.14, 11 (2021), 1964–1978

work page 2021
[66]

Roger Weber, Hans-Jörg Schek, and Stephen Blott. 1998. A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces. InVLDB. 194–205

work page 1998
[67]

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
[68]

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

work page
[69]

ACM Manag

irangegraph: Improvising range-dedicated graphs for range-filtering near- est neighbor search.Proc. ACM Manag. Data2, 6 (2024), 1–26

work page 2024
[70]

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.Proc. ACM Manag. Data3, 3 (2025), 1–26

work page 2025
[71]

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. InOSDI. 377–395

work page 2023
[72]

Penghao Zhao, Hailin Zhang, Qinhan Yu, Zhengren Wang, Yunteng Geng, Fangcheng Fu, Ling Yang, Wentao Zhang, Jie Jiang, and Bin Cui. 2024. Retrieval- augmented generation for ai-generated content: A survey.arXiv preprint arXiv:2402.19473(2024)

work page internal anchor Pith review arXiv 2024
[73]

Zhiqiu Zou, Ziqi Yin, Rong-Hua Li, Hongchao Qin, Qiangqiang Dai, and Guoren Wang. [n.d.]. RNSG: A Range-Aware Graph Index for Efficient Range-Filtered Approximate Nearest Neighbor Search. Inhttps:// github.com/ fallleaves01/ R-NSG/ blob/ main/ RNSG-FULL.pdf. Full version manuscript

work page
[74]

Zhiqiu Zou, Ziqi Yin, Rong-Hua Li, Hongchao Qin, Qiangqiang Dai, and Guoren Wang. 2026. RNSG: A Range-Aware Graph Index for Efficient Range-Filtered Approximate Nearest Neighbor Search. arXiv:2603.12913 [cs.DB] https://arxiv. org/abs/2603.12913

work page internal anchor Pith review Pith/arXiv arXiv 2026
[75]

Chaoji Zuo, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. 2024. SeRF: seg- ment graph for range-filtering approximate nearest neighbor search.Proceedings of the ACM on Management of Data2, 1 (2024), 1–26. 14 A APPENDIX A.1 Baseline Configuration Details Table 2 summarizes the construction-parameter policy used for the baseline comparison in Section 5...

work page 2024