# SPTAG: Microsoft's C++ Library for Billion-Scale Approximate Nearest Neighbor Search > SPTAG (Space Partition Tree And Graph) is a C++ library from Microsoft Research and Bing that builds and queries vector indices for approximate nearest neighbor search at large scale. It provides two index methods, a Python wrapper, a distributed serving layer, and support for online vector insertion and deletion. **microsoft/SPTAG** — A distributed approximate nearest neighborhood search (ANN) library which provides a high quality vector index build, search and distributed online serving toolkits for large scale vector search scenario. - Repository: https://github.com/microsoft/SPTAG - Stars: 5,020 · Forks: 621 - Language: C++ - License: MIT - Published: 2026-09-23 · Updated: 2026-09-23 · Language: en - Canonical page: https://hysenlabs.com/projects/microsoft-sptag ## What SPTAG Does and Why Microsoft Built It SPTAG solves the problem of finding the vectors most similar to a query vector within a very large collection, fast enough to serve search queries in production. The library assumes vectors can be compared by L2 distance or cosine distance, and returns the vectors with the smallest distance to the query. The library was released by Microsoft Research (MSR) and Microsoft Bing. The search use case in Bing is the original production context: large-scale retrieval over high-dimensional vectors at query-serving latency. The README describes it as designed for large scale vector approximate nearest neighbor search scenario. The term approximate is precise: SPTAG does not guarantee finding the exact nearest neighbors, but it finds results that are close enough for practical search and recommendation purposes, with indexing and query times that would not be achievable with exhaustive search over a large corpus. ## Two Index Methods: SPTAG-KDT and SPTAG-BKT SPTAG provides two index construction methods, and the README is specific about the trade-offs between them. SPTAG-KDT uses a kd-tree and a relative neighborhood graph (RNG). The README states it is advantageous in index building cost. This means the index takes less time and resources to construct, making it preferable when the vector corpus changes frequently or when build time is a constraint. SPTAG-BKT uses a balanced k-means tree instead of a kd-tree, combined with the same RNG structure. The README states it is advantageous in search accuracy in very high-dimensional data. kd-trees produce inaccurate distance bound estimates for very high-dimensional vectors; balanced k-means trees avoid this problem. For high-dimensional embeddings where retrieval quality matters more than index build time, SPTAG-BKT is the appropriate choice. Both methods share the same search mechanism: the search starts in the tree to find seed vectors, then continues through the RNG iteratively. The RNG is built on the k-nearest neighborhood graph to improve connectivity, which guides the search toward better candidates more efficiently than random graph traversal. ## Building SPTAG from Source SPTAG requires building from source on Linux or Windows. The dependencies are swig >= 4.0.2, cmake >= 3.12.0, and boost >= 1.67.0. The Linux build involves several steps for the optional third-party components: ```bash mkdir build cd build && cmake -DSPDK=OFF -DROCKSDB=OFF .. && make ``` Passing -DSPDK=OFF and -DROCKSDB=OFF disables the optional SPDK and RocksDB components, which require additional setup. This produces a Release folder with all build targets. On Windows, the cmake command uses -A x64 and generates a Visual Studio solution (SPTAGLib.sln) rather than a Makefile. The Docker path is simpler: ```bash docker build -t sptag . ``` This builds a container based on Ubuntu 20.04 with gcc-8/g++-8, Python 3.8, numpy, and the SPTAG binaries at /app/Release. The Dockerfile is the lowest-friction way to evaluate SPTAG without managing the build toolchain locally. After building, the README recommends running SPTAGTest (or Test.exe on Windows) from the Release folder to verify the build. The Python wrapper is installed via setup.py: ```bash python setup.py develop ``` The setup.py documentation notes that the SPTAG_RELEASE environment variable sets the release version, and that the Python version must be specified when building the wheel package. ## Online Updates and Distributed Serving Two features distinguish SPTAG from simpler ANN libraries: fresh updates and distributed serving. Fresh update means the index supports online vector insertion and deletion without rebuilding the entire index. The README lists this under Highlights. The SPFresh paper, published in SOSP 2023 ("SPFresh: Incremental In-Place Update for Billion-Scale Vector Search"), documents the algorithm for this incremental in-place update approach. A related paper, VBASE, from OSDI 2023, covers combining vector similarity search with relational queries via relaxed monotonicity. The VBASE approach introduced the result iterator with relaxed monotonicity signal support listed in the README's "What's NEW" section. Distributed serving means the library includes tooling for search over multiple machines. The README lists this under Highlights but does not detail the distributed architecture in the README text. The docs/GettingStart.md file in the repository covers the full usage details. For teams who need to update a production vector index without downtime, the fresh update capability is the relevant differentiator. An index that requires full rebuilds for every update cannot support continuously changing corpora at scale. ## Limitations: Build Complexity and Scope SPTAG is a C++ library that requires compilation. Unlike managed vector databases with REST APIs and cloud hosting, SPTAG starts with a build process that involves resolving C++ dependencies, compiler versions, and optional third-party libraries. The Dockerfile mitigates this for evaluation but does not solve deployment in environments without Docker. The Python wrapper provides a more accessible interface than raw C++, but it is built on top of the C++ code and still requires the compiled library to be present. Pure Python environments cannot install SPTAG as a simple pip package. SPTAG does not include a built-in REST API or HTTP serving layer in the repository. The docs reference an end-to-end tutorial for building a vector search online service using the Python wrapper, but the serving infrastructure is the developer's responsibility. The library compares L2 distances or cosine distances only. Teams working with other distance metrics such as inner product or dot product similarity would need to verify compatibility. ## Alternative: DiskANN and the Difference in Approach DiskANN is another approximate nearest neighbor library from Microsoft Research (a separate project). The key difference is the storage model: DiskANN is designed to keep most of the index on disk and serve queries efficiently through SSD I/O, making it suitable for corpora too large to fit in RAM. SPTAG's index is designed to reside in memory during serving. The RELATED SEARCHES for this project include Spann vs diskann, which reflects a common evaluation question. SPANN (described in the SPTAG research lineage) targets the hybrid memory-disk scenario, while SPTAG-KDT and SPTAG-BKT are memory-resident index structures. For teams with corpora that fit in server RAM, SPTAG is a well-understood option with production history at Bing. For corpora that require disk-based indexing to manage memory costs, DiskANN is the more appropriate starting point. ## Licence, Research Citation, and Repository Status SPTAG is licensed under the MIT licence, allowing use, modification, and distribution including in commercial products. The README asks that SPTAG be cited in academic publications, pointing to the SPFresh paper (SOSP 2023) as the reference to use. The citation details are in the README and in the SOSP 2023 proceedings. The repository has no GitHub Releases listed, so versioning is tracked through commits and tags rather than a release page. The last push was on 2026-09-24. The project accepts contributions through GitHub issues and pull requests. ## Conclusion SPTAG is a credible choice for teams running large-scale vector search on infrastructure they control, particularly where GPU support, online updates, or distributed serving are requirements. The Python wrapper and Docker image lower the barrier to evaluation. Before committing, verify that your build environment meets the dependency versions: swig >= 4.0.2, cmake >= 3.12.0, and boost >= 1.67.0. Teams whose use case fits a managed cloud service should evaluate hosted vector databases first, since SPTAG requires building from source and managing the multi-component serving stack. The SPFresh paper from SOSP 2023 documents the incremental update mechanism in detail and is the authoritative reference for the fresh update feature. ## FAQ ### What is the difference between SPTAG-KDT and SPTAG-BKT? SPTAG-KDT uses a kd-tree and is faster to build, making it better for frequently updated corpora. SPTAG-BKT uses a balanced k-means tree and is more accurate for very high-dimensional data because kd-trees produce inaccurate distance bounds at high dimensions. ### Does SPTAG support online insertion and deletion of vectors? Yes. The README lists Fresh update as a highlight, meaning vectors can be inserted and deleted from the index without a full rebuild. The algorithm is documented in the SPFresh paper published at SOSP 2023. ### How do I install the SPTAG Python wrapper? After building the C++ library, install the Python wrapper with python setup.py develop. The setup.py file in the repository root handles the installation and links the Python package to the compiled Release binaries. ## Sources - [Issues](https://github.com/microsoft/SPTAG/issues) - [License: MIT](https://github.com/microsoft/SPTAG/blob/main/LICENSE) - [microsoft/SPTAG on GitHub](https://github.com/microsoft/SPTAG) - [README](https://github.com/microsoft/SPTAG/blob/main/README.md) --- Hysen Labs editorial analysis, written from the project's own repository and release notes. Cite the canonical page: https://hysenlabs.com/projects/microsoft-sptag