Timezone: »

 
Poster
DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node
Suhas Jayaram Subramanya · Fnu Devvrit · Harsha Vardhan Simhadri · Ravishankar Krishnawamy · Rohan Kadekodi

Wed Dec 11 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #94
in Applications -- Information Retrieval »

Current state-of-the-art approximate nearest neighbor search (ANNS) algorithms generate indices that must be stored in main memory for fast high-recall search. This makes them expensive and limits the size of the dataset. We present a new graph-based indexing and search system called DiskANN that can index, store, and search a billion point database on a single workstation with just 64GB RAM and an inexpensive solid-state drive (SSD). Contrary to current wisdom, we demonstrate that the SSD-based indices built by DiskANN can meet all three desiderata for large-scale ANNS: high-recall, low query latency and high density (points indexed per node). On the billion point SIFT1B bigann dataset, DiskANN serves > 5000 queries a second with < 3ms mean latency and 95%+ 1-recall@1 on a 16 core machine, where state-of-the-art billion-point ANNS algorithms with similar memory footprint like FAISS and IVFOADC+G+P plateau at around 50% 1-recall@1. Alternately, in the high recall regime, DiskANN can index and serve 5 − 10x more points per node compared to state-of-the-art graph- based methods such as HNSW and NSG. Finally, as part of our overall DiskANN system, we introduce Vamana, a new graph-based ANNS index that is more versatile than the graph indices even for in-memory indices.

Keywords: Combinatorial Optimization · Information Retrieval · Applications · Algorithms -> Large Scale Learning; Algorithms -> Similarity and Distance Learning; Optimization
[ Paper]  [ Slides] 

Author Information

Suhas Jayaram Subramanya (Carnegie Mellon University)
Fnu Devvrit (University of Texas at Austin)

Hi. I am Devvrit, a second year PhD student at UT Austin. I'm broadly interested in large scale machine learning, deep learning, and optimization. In my free time, I play badminton and look for adventure sports.

Harsha Vardhan Simhadri (Microsoft Research)
Ravishankar Krishnawamy (Microsoft Research India)
Rohan Kadekodi (The University of Texas at Austin)

More from the Same Authors