DistributedANN: Efficient Scaling of a Single DiskANN Graph Across Thousands of Computers

We present DistributedANN, a distributed vector search service that makes it possible to search over a single 50 billion vector graph index at $26$ms median latency at 100,000 queries/second. This is $6 \times$ more efficient than the best partitioning and selective routing strategies that route the vector query to a subset of partitions. DistributedANN is built using two well-understood components: a distributed key-value store and an in-memory ANN index. DistributedANN has replaced conventional shard-out architectures for serving the Bing search engine, and we share our experience from making this transition.