Web-scale search and recommendation scenarios increasingly use Approximate Nearest Neighbor Search (ANNS) algorithms to index and retrieve objects based on the similarity of their learnt representations in a geometric space. Since these scenarios often span billions or trillions of objects, efficient and scalable ANNS algorithms are critical to making these systems practical.
In this talk we discuss some recent empirical progress on this problem. Specifically, we present DiskANN, an ANNS algorithm that can index a billion points and serve queries at latencies of few milliseconds on a single commodity machine. This represents an order of magnitude more points indexed per machine than previous work. We will also discuss some fundamental open problems in this space in the latter half of the talk.
Based on joint works with Harsha Simhadri, Sujas J Subramanya, Aditi Singh, Rohan Kadekodi, Devvrit, Shikhar Jaiswal, Magdalen Dobson, Siddharth Gollapudi, Neel Karia, Varun Sivashankar, and Varun Suriyanarayana.
Short Bio:
He is a principal researcher at Microsoft Research India. His PhD was completed at Carnegie Mellon University in 2012. From 2012-2014, a Simons Postdoctoral Fellowship was held by him at the CS Department in Princeton University. Long, long ago, he was an undergrad at IIT Madras. Broad interest in basic problems in algorithms and optimization characterizes his work. Lately, work on the design of very large-scale (billions of vectors) approximate nearest neighbor search (ANNS) has been undertaken as part of the DiskANN project. Also, he spends his time thinking about basic problems in online and approximation algorithms, especially for graph-theoretic and clustering problems.
