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.
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
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.
Forward citations
Cited by 6 Pith papers
-
iFVS: Towards Instance-Optimized Filtered Vector Search
iFVS adapts Product Quantization codebooks to individual filter predicates and query vectors, improving QPS-recall tradeoff over fixed-codebook PQ on SIFT1M/SIFT10M.
-
Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization
OPT-SNG introduces a martingale model for SNG pruning in ANNS, proves O(n^{2/3+ε}) max out-degree and O(log n) expected path length, and gives a closed-form optimal truncation parameter that yields 5.9× average constr...
-
ANNLib: A Development Framework for Efficient Approximate Nearest Neighbor Search
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.
-
Fast Approximate Vector Joins via Offline-Online Co-Design
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%.
-
RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval
RetrievalAttention approximates full attention in long-context LLMs by retrieving relevant KV vectors from CPU-based ANNS indexes with an attention-aware algorithm, achieving near-full accuracy while accessing only 1-...
-
NAVIS: Concurrent Search and Update with Low Position-Seeking Overhead in On-SSD Graph-Based Vector Search
NAVIS improves concurrent search and update throughput in on-SSD graph vector search by up to 2.74x for insertions and 1.37x for searches through reduced position-seeking overhead.
Discussion (0). Sign in to comment.