Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-based ANN Search

Summary: MARGO introduces a monotonic-path-aware objective that weights edges by their importance and computes weights on-the-fly during index construction. A greedy two-stage (intra/inter) optimizer prioritizes high-weight edges for disk locality, giving up to 26.6% search speedup at equal recall and 5.5× faster layout. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 14050
Venue: VLDB
Year: 2025
Pagerank: 4.1905499e-05
Overall Rank: 10,744 | 25.33%
DOI: 10.14778/3749646.3749697

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016113151
210	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034086264
494	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.00021769407
1,013	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014632051
1,347	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.00012463441
2,002	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	9.8258191e-05
2,160	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	9.4037759e-05
2,264	Manu: A Cloud Native Vector Database Management System	2022	VLDB	9.1587362e-05
2,687	HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search	2022	VLDB	8.3079951e-05
2,692	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	8.2857267e-05
2,969	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	7.7955562e-05
5,236	RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search	2024	VLDB	5.6077913e-05
5,690	FARGO: Fast Maximum Inner Product Search via Global Multi-Probing	2023	VLDB	5.3699421e-05
5,747	Hercules Against Data Series Similarity Search	2022	VLDB	5.3427166e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,042	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD	4.1905499e-05
10,691	Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts	2025	VLDB	4.1905499e-05
8,239	MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search	2025	SIGMOD	4.5471319e-05
10,073	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD	4.1905499e-05
7,542	A Topology-Aware Localized Update Strategy for Graph-Based ANN Index	2026	VLDB	4.7103816e-05
10,165	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1905499e-05
5,577	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	5.423881e-05
10,256	I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration	2026	VLDB	4.1905499e-05
210	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034086264
2,002	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	9.8258191e-05