ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph

Summary: Introduces ARKGraph, an index for approximate KNN graphs over vectors within arbitrary numeric-key ranges. Grouping stable KNNs across nearby ranges reduces average space from O(Kn³) to O(Kn log n), enabling direct construction and fast neighbor restoration. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h63035b739110eb73
Venue: VLDB
Year: 2023
Pagerank: 5.9512758e-05
Overall Rank: 5,903 | 60.33%
DOI: 10.14778/3603581.3603601
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Chaoji Zuo (Rutgers University)
2. Dong Deng (Rutgers University)

BibTeX Citation

@article{zuo_vldb23,
        title = {{ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph}},
        author = {Zuo, Chaoji and Deng, Dong},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {10},
        pages = {2645--2658},
        doi = {10.14778/3603581.3603601},
        url = {https://doi.org/10.14778/3603581.3603601},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,958	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD	9.3118048e-05
4,347	UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search	2025	VLDB	6.6457039e-05
6,132	Dynamic Range-Filtering Approximate Nearest Neighbor Search	2025	VLDB	5.8755887e-05
6,230	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	5.842393e-05
8,350	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	5.3481387e-05
8,679	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	5.2892731e-05
10,332	WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search	2026	SIGMOD	5.0322912e-05
10,468	FAVOR: Efficient Filter-Agnostic Vector ANNS Based on Selectivity-Aware Exclusion Distances	2026	SIGMOD	4.9769913e-05
10,639	Curator: Efficient Vector Search with Low-Selectivity Filters	2026	SIGMOD	4.9769913e-05
10,779	Harmonizing Efficiency and Accuracy in Filtered Vector Search	2026	VLDB	4.9769913e-05
10,823	X-Wim: Massive Parallelization of Weighted Matching in Bipartite Graphs	2026	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0019923528
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.0005758001
74	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00037145866
90	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00034847854
189	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.0002585319
278	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.00022310642
297	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00021849337
338	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00020600264
339	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.00020561716
562	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016350316
576	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016118297
712	Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan	2016	VLDB	0.00014593534

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,668	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
2	10,837	Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization	2026	VLDB
3	4,051	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB
4	1,166	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD
5	11,057	Elastic Index Selection for Label-Hybrid AKNN Search	2026	VLDB
6	1,958	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD
7	6,461	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD
8	10,333	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
9	10,839	RNSG: A Range-Aware Graph Index for Efficient Range-Filtered Approximate Nearest Neighbor Search	2026	VLDB
10	2,717	iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search	2024	SIGMOD