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.9396547e-05
Overall Rank: 5,891 | 60.52%
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,968	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD	9.2810141e-05
4,368	UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search	2025	VLDB	6.6237291e-05
5,142	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	6.2420637e-05
6,146	Dynamic Range-Filtering Approximate Nearest Neighbor Search	2025	VLDB	5.8561603e-05
8,364	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	5.3304544e-05
8,699	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	5.2717835e-05
10,358	WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search	2026	SIGMOD	5.0156513e-05
10,534	FAVOR: Efficient Filter-Agnostic Vector ANNS Based on Selectivity-Aware Exclusion Distances	2026	SIGMOD	4.9605343e-05
10,700	Curator: Efficient Vector Search with Low-Selectivity Filters	2026	SIGMOD	4.9605343e-05
10,840	Harmonizing Efficiency and Accuracy in Filtered Vector Search	2026	VLDB	4.9605343e-05
10,884	X-Wim: Massive Parallelization of Weighted Matching in Bipartite Graphs	2026	VLDB	4.9605343e-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.0019892478
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00057610161
75	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00037163157
90	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00034749222
181	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.00026425782
281	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.00022262975
286	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00022090962
325	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.00020930941
339	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00020558018
562	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016344855
578	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016079505
710	Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan	2016	VLDB	0.00014598403

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,684	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
2	10,898	Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization	2026	VLDB
3	1,165	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD
4	4,077	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB
5	11,118	Elastic Index Selection for Label-Hybrid AKNN Search	2026	VLDB
6	1,968	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD
7	6,475	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD
8	10,359	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
9	10,900	RNSG: A Range-Aware Graph Index for Efficient Range-Filtered Approximate Nearest Neighbor Search	2026	VLDB
10	2,728	iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search	2024	SIGMOD