Ood-diskann: Efficient And Scalable Graph ANNS For Out-of-distribution Queries

Abstract

State-of-the-art algorithms for Approximate Nearest Neighbor Search (ANNS) such as DiskANN, FAISS-IVF, and HNSW build data dependent indices that offer substantially better accuracy and search efficiency over data-agnostic indices by overfitting to the index data distribution. When the query data is drawn from a different distribution - e.g., when index represents image embeddings and query represents textual embeddings - such algorithms lose much of this performance advantage. On a variety of datasets, for a fixed recall target, latency is worse by an order of magnitude or more for Out-Of-Distribution (OOD) queries as compared to In-Distribution (ID) queries. The question we address in this work is whether ANNS algorithms can be made efficient for OOD queries if the index construction is given access to a small sample set of these queries. We answer positively by presenting OOD-DiskANN, which uses a sparing sample (1% of index set size) of OOD queries, and provides up to 40% improveme

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyjaiswal2022ood

Related papers

• Freshdiskann: A Fast And Accurate Graph-based ANN Index For Streaming Similarity Search (2021)0.00
• DGAI: Decoupled On-disk Graph-based ANN Index For Efficient Updates And Queries (2025)0.00
• Diskann++: Efficient Page-based Search Over Isomorphic Mapped Graph Index Using Query-sensitivity Entry Vertex (2023)0.00
• In-place Updates Of A Graph Index For Streaming Approximate Nearest Neighbor Search (2025)0.00
• SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search (2021)0.00
• Aisaq: All-in-storage ANNS With Product Quantization For Dram-free Information Retrieval (2024)0.00
• Frequency-aware Graph Construction And Search For Dynamic Vector Databases (2025)0.00
• Roargraph: A Projected Bipartite Graph For Efficient Cross-modal Approximate Nearest Neighbor Search (2024)8.09