Efficient and Robust Out-Of-Distribution Vector Similarity Search with Cross-Distribution Monotonic Graph
Proceedings of the ACM on Management of Data · 02.04.2026 · 4 (1) · 1-29
DOI: 10.1145/3786643 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 07.04.2026. Verfasst von Qiang Yue und 5 weiteren Autor:innen. Die Arbeit nennt 95 Literaturangaben. Gefördert von: \"Pioneer\" and \"Leading Goose\" R&D Program of Zhejiang, National Natural Science Foundation of China.
Abstract (Originalsprache)
Vector similarity search is a key component in many AI applications. While graph-based methods represent the state-of-the-art for vector similarity search, existing graph indexes often suffer from poor navigability and clusterability in Out-Of-Distribution (OOD) scenarios (e.g., database and queries are sourced from different modalities). Recent studies have attempted to mitigate this issue by projecting and integrating query-derived auxiliary index structures, but these approaches remain largely heuristic and lack theoretical grounding. In this work, we propose Cross-Distribution Monotonic Graph (CDMG), a novel graph index designed to inherently support navigability and clusterability for OOD queries. CDMG introduces an integration strategy that bridges the distribution gap between database and query vectors, ensuring a key property—cross-distribution monotonicity—that guarantees monotonic search paths for OOD queries on graph indexes. Theoretical analysis demonstrates that CDMG achieves a lower search time complexity in OOD scenarios compared with existing graph indexes. Furthermore, we introduce CDMG+, a practical variant of CDMG that improves construction efficiency by introducing query synthesis, fusion-based distance computation, as well as optimized candidate acquisition and neighbor selection strategies. Extensive empirical evaluations demonstrate that our techniques outperform state-of-the-art methods, achieving up to a 3.6× speedup on real-world OOD datasets.
Förderung
- \"Pioneer\" and \"Leading Goose\" R&D Program of Zhejiang
- National Natural Science Foundation of China
Zitieren
APA
Yue, Q., Wang, M., Xu, X., Long, C., Wang, Y., & Wang, J. (2026). Efficient and Robust Out-Of-Distribution Vector Similarity Search with Cross-Distribution Monotonic Graph. Proceedings of the ACM on Management of Data, 4(1), 1-29. https://doi.org/10.1145/3786643
Vancouver
Yue Q, Wang M, Xu X, Long C, Wang Y, Wang J. Efficient and Robust Out-Of-Distribution Vector Similarity Search with Cross-Distribution Monotonic Graph. Proceedings of the ACM on Management of Data. 2026;4(1):1-29. doi:10.1145/3786643
BibTeX
@article{Yue2026,
author = {Yue, Qiang and Wang, Mengzhao and Xu, Xiaoliang and Long, Cheng and Wang, Yuxiang and Wang, Jiahui},
title = {Efficient and Robust Out-Of-Distribution Vector Similarity Search with Cross-Distribution Monotonic Graph},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {1},
pages = {1--29},
doi = {10.1145/3786643}
}
EUVIMED