Trees seed the search, graphs finish it: Microsoft’s ANN library

What it does SPTAG is a C++ library for approximate nearest neighbor search over large vector datasets. It assumes your data lives as vectors comparable by L2 or cosine distance, and it returns the closest matches without scanning everything. The library offers two index flavors: SPTAG-KDT, which pairs kd-trees with a relative neighborhood graph, and SPTAG-BKT, which swaps in balanced k-means trees for better accuracy on very high-dimensional data.

The interesting bit Instead of betting everything on one data structure, SPTAG uses trees only to find promising seed points, then hands off to a relative neighborhood graph to iteratively refine the search. The balanced k-means variant specifically exists because kd-trees grow sloppy distance bounds in very high dimensions—a neat admission that classic spatial indexes break down when your vectors get wide.

Key highlights

• Backed by recent systems research, including SOSP 2023’s SPFresh and OSDI 2023’s VBASE, plus an earlier NeurIPS 2021 SPANN paper.
• Supports online deletion and insertion of vectors, so the index can stay warm rather than requiring a full rebuild.
• Distributed serving lets the search span multiple machines.
• Released under the MIT license by Microsoft Research and Bing.

Caveats

• The project carries a broad third-party dependency surface—SPDK, RocksDB, and others—which the README treats as mandatory compile-time companions.
• The repository ships large enough assets that the README recommends skipping git-lfs smudge for a tolerable clone.

Verdict If you are building a billion-scale embedding search pipeline and need an index that supports online updates and distributed queries, SPTAG is worth evaluating. If you want a drop-in, dependency-light vector index, the build complexity may send you elsewhere.