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: 14049
Venue: VLDB
Year: 2025
Pagerank: 4.1945683e-05
Overall Rank: 10,737 | 25.31%
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.0016162015
212	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00033913475
495	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.00021767688
1,010	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014652858
1,364	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.00012370117
2,023	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	9.7544991e-05
2,181	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	9.3451821e-05
2,262	Manu: A Cloud Native Vector Database Management System	2022	VLDB	9.1624446e-05
2,690	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	8.293714e-05
2,725	HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search	2022	VLDB	8.2294908e-05
2,971	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	7.7970531e-05
5,233	RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search	2024	VLDB	5.6131833e-05
5,707	FARGO: Fast Maximum Inner Product Search via Global Multi-Probing	2023	VLDB	5.3611041e-05
5,738	Hercules Against Data Series Similarity Search	2022	VLDB	5.3478528e-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.1945683e-05
10,683	Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts	2025	VLDB	4.1945683e-05
8,245	MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search	2025	SIGMOD	4.5514956e-05
10,073	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD	4.1945683e-05
7,544	A Topology-Aware Localized Update Strategy for Graph-Based ANN Index	2026	VLDB	4.7149033e-05
10,165	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1945683e-05
5,569	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	5.4290942e-05
10,256	I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration	2026	VLDB	4.1945683e-05
212	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00033913475
2,023	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	9.7544991e-05