EUVIMEDScopri EUVIMED
Crossref

Efficient and Robust Out-Of-Distribution Vector Similarity Search with Cross-Distribution Monotonic Graph

Qiang Yue, Mengzhao Wang, Xiaoliang Xu, Cheng Long, Yuxiang Wang, Jiahui Wang

Proceedings of the ACM on Management of Data · 2026-04-02 · 4 (1) · 1-29

DOI: 10.1145/3786643 ↗

At a glance

Journal article in Proceedings of the ACM on Management of Data, published online on 2026-04-07. Written by Qiang Yue and 5 co-authors. 95 references. Funded by: \"Pioneer\" and \"Leading Goose\" R&D Program of Zhejiang, National Natural Science Foundation of China.

AbstractDati bibliograficiCiteRelated studies

Abstract (original language)

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.

Funding

  • \"Pioneer\" and \"Leading Goose\" R&D Program of Zhejiang
  • National Natural Science Foundation of China

Cite

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}
}
Start for free →