Pith. sign in

REVIEW 6 cited by

OOD-DiskANN: Efficient and Scalable Graph ANNS for Out-of-Distribution Queries

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2211.12850 v2 pith:3IEO6JZQ submitted 2022-10-22 cs.LG cs.IR

Shikhar Jaiswal , Ravishankar Krishnaswamy , Ankit Garg , Harsha Vardhan Simhadri , Sheshansh Agrawal This is my paper · ORCID
classification cs.LGcs.IR
keywords queriesalgorithmsannsindexquerydataefficiencyindices
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original 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% improvement in mean query latency over SoTA algorithms of a similar memory footprint. OOD-DiskANN is scalable and has the efficiency of graph-based ANNS indices. Some of our contributions can improve query efficiency for ID queries as well.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 6 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. iFVS: Towards Instance-Optimized Filtered Vector Search

    cs.DB 2026-07 conditional novelty 7.0 of 10

    iFVS adapts Product Quantization codebooks to individual filter predicates and query vectors, improving QPS-recall tradeoff over fixed-codebook PQ on SIFT1M/SIFT10M.

  2. ANNLib: A Development Framework for Efficient Approximate Nearest Neighbor Search

    cs.LG 2026-07 conditional novelty 6.0 of 10

    A modular ANNS framework decouples search algorithms from graph storage, delivering filtered search, dynamic updates, and snapshot queries at performance close to that of specialized systems.

  3. Fast Approximate Vector Joins via Offline-Online Co-Design

    cs.DB 2026-03 conditional novelty 6.0 of 10

    A merged index and soft work sharing speed up approximate threshold-based vector joins by up to 56x, with a hybrid search improving out-of-distribution recall by up to 43%.

  4. PathWeaver: A High-Throughput Multi-GPU System for Graph-Based Approximate Nearest Neighbor Search

    cs.DC 2025-07 conditional novelty 6.0 of 10

    PathWeaver speeds up multi-GPU graph-based approximate nearest neighbor search by pipelining search results across GPU shards, staging entry points, and filtering neighbors by direction.

  5. DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search

    cs.DB 2025-05 reject novelty 6.0 of 10

    DARTH learns to predict a query's current recall during HNSW/IVF search and stops early at a user-specified target, achieving speedups up to 14.6x on HNSW and 41.8x on IVF, yet 13-15% of queries miss the target.

  6. Inference-time sparse attention with asymmetric indexing

    cs.CL 2025-02 conditional novelty 6.0 of 10

    Saap approximates attention by clustering keys with k-means and learning a query classifier, reducing KV-cache lookups about 20x at 4-5% selectivity with small accuracy loss on several long-context benchmarks.

Pith tools