SPTAG Documentation

1. Project Overview & Quickstart (microsoft/SPTAG)

File: README.md

SPTAG: A library for fast approximate nearest neighbor search

SPTAG

SPTAG (Space Partition Tree And Graph) is a library for large scale vector approximate nearest neighbor search scenario released by Microsoft Research (MSR) and Microsoft Bing.

What's NEW

Result Iterator with Relaxed Monotonicity Signal Support
New Research Paper SPFresh: Incremental In-Place Update for Billion-Scale Vector Search - published in SOSP 2023
New Research Paper VBASE: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity - published in OSDI 2023

Introduction

This library assumes that the samples are represented as vectors and that the vectors can be compared by L2 distances or cosine distances.
Vectors returned for a query vector are the vectors that have smallest L2 distance or cosine distances with the query vector.

SPTAG provides two methods: kd-tree and relative neighborhood graph (SPTAG-KDT)
and balanced k-means tree and relative neighborhood graph (SPTAG-BKT).
SPTAG-KDT is advantageous in index building cost, and SPTAG-BKT is advantageous in search accuracy in very high-dimensional data.

How it works

SPTAG is inspired by the NGS approach [WangL12]. It contains two basic modules: index builder and searcher.
The RNG is built on the k-nearest neighborhood graph [WangWZTG12, WangWJLZZH14]
for boosting the connectivity. Balanced k-means trees are used to replace kd-trees to avoid the inaccurate distance bound estimation in kd-trees for very high-dimensional vectors.
The search begins with the search in the space partition trees for
finding several seeds to start the search in the RNG.
The searches in the trees and the graph are iteratively conducted.

Highlights

Fresh update: Support online vector deletion and insertion
Distributed serving: Search over multiple machines

Build

Requirements

swig >= 4.0.2
cmake >= 3.12.0
boost >= 1.67.0

Fast clone

text

set GIT_LFS_SKIP_SMUDGE=1
git clone --recurse-submodules https://github.com/microsoft/SPTAG

OR

git config --global filter.lfs.smudge "git-lfs smudge --skip -- %f"
git config --global filter.lfs.process "git-lfs filter-process --skip"

Install

For Linux:
Compile SPDK

bash

cd ThirdParty/spdk
./scripts/pkgdep.sh
CC=gcc-9 ./configure
CC=gcc-9 make -j

Compile isal-l_crypto

bash

cd ThirdParty/isal-l_crypto
./autogen.sh
./configure
make -j

Build RocksDB

bash

mkdir build && cd build
cmake -DUSE_RTTI=1 -DWITH_JEMALLOC=1 -DWITH_SNAPPY=1 -DCMAKE_C_COMPILER=gcc-7 -DCMAKE_CXX_COMPILER=g++-7 -DCMAKE_BUILD_TYPE=Release -DCMAKE_CXX_FLAGS="-fPIC" ..
make -j
sudo make install

Build SPTAG

bash

mkdir build
cd build && cmake -DSPDK=OFF -DROCKSDB=OFF .. && make

It will generate a Release folder in the code directory which contains all the build targets.

For Windows:

bash

mkdir build
cd build && cmake -A x64 -DSPDK=OFF -DROCKSDB=OFF ..

It will generate a SPTAGLib.sln in the build directory.
Compiling the ALL_BUILD project in the Visual Studio (at least 2019) will generate a Release directory which contains all the build targets.

For detailed instructions on installing Windows binaries, please see here

Using Docker:

bash

docker build -t sptag .

Will build a docker container with binaries in /app/Release/.

Verify

Run the SPTAGTest (or Test.exe) in the Release folder to verify all the tests have passed.

Usage

The detailed usage can be found in Get started. There is also an end-to-end tutorial for building vector search online service using Python Wrapper in Python Tutorial.
The detailed parameters tunning can be found in Parameters.

References

Please cite SPTAG in your publications if it helps your research:

text

/* Detailed source-code truncated for AI context efficiency. */

Contribute

This project welcomes contributions and suggestions from all the users.

We use GitHub issues for tracking suggestions and bugs.

License

The entire codebase is under MIT license

File: datasets/SPACEV1B/README.md

SPACEV1B: A billion-Scale vector dataset for text descriptors

This is a dataset released by Microsoft from SpaceV, Bing web vector search scenario, for large scale vector search related research usage. It consists of more than one billion document vectors
and 29K+ query vectors encoded by Microsoft SpaceV Superior model. This model is trained to capture generic intent representation for both documents and queries.
The goal is to match the query vector to the closest document vectors in order to achieve topk relevant documents for each query.

Introduction

This dataset contains:

vectors.bin: It contains 1,402,020,720 100-dimensional int8-type document descriptors.
query.bin: It contains 29,316 100-dimensional int8-type query descriptors.
truth.bin: It contains 100 nearest ground truth（include vector ids and distances) of 29,316 queries according to L2 distance.
query_log.bin: It contains 94,162 100-dimensional int8-type history query descriptors.

How to read the vectors, queries, and truth

python

import struct
import numpy as np
import os

part_count = len(os.listdir('vectors.bin'))
for i in range(1, part_count + 1):
    fvec = open(os.path.join('vectors.bin', 'vectors_%d.bin' % i), 'rb')
    if i == 1:
        vec_count = struct.unpack('i', fvec.read(4))[0]
        vec_dimension = struct.unpack('i', fvec.read(4))[0]
        vecbuf = bytearray(vec_count * vec_dimension)
        vecbuf_offset = 0
    while True:
        part = fvec.read(1048576)
        if len(part) == 0: break
        vecbuf[vecbuf_offset: vecbuf_offset + len(part)] = part
        vecbuf_offset += len(part)
    fvec.close()
X = np.frombuffer(vecbuf, dtype=np.int8).reshape((vec_count, vec_dimension))

fq = open('query.bin', 'rb')
q_count = struct.unpack('i', fq.read(4))[0]
q_dimension = struct.unpack('i', fq.read(4))[0]
queries = np.frombuffer(fq.read(q_count * q_dimension), dtype=np.int8).reshape((q_count, q_dimension))

ftruth = open('truth.bin', 'rb')
t_count = struct.unpack('i', ftruth.read(4))[0]
topk = struct.unpack('i', ftruth.read(4))[0]
truth_vids = np.frombuffer(ftruth.read(t_count * topk * 4), dtype=np.int32).reshape((t_count, topk))
truth_distances = np.frombuffer(ftruth.read(t_count * topk * 4), dtype=np.float32).reshape((t_count, topk))

License

The entire dataset is under O-UDA license

File: docs/GettingStart.md

Quick start

Memory SPTAG Index Build

bash

Usage:
./IndexBuiler [options]
Options:
 -d, --dimension <value>       Dimension of vector, required.
 -v, --vectortype <value>      Input vector data type (e.g. Float, Int8, Int16), required.
 -f, --filetype <value>        Input file type (DEFAULT, TXT, XVEC). Default is DEFAULT.
 -i, --input <value>           Input raw data, required.
 -o, --outputfolder <value>    Output folder, required.
 -a, --algo <value>            Index Algorithm type (e.g. BKT, KDT), required.

 -t, --thread <value>          Thread Number.
 -dl, --delimiter <value>      Vector delimiter.
 -norm, --normalized <value>   Vector is normalized.
 -c, --config <value>          Config file for builder.
 -pq, --quantizer <value>      Quantizer File
 -m, --metaindex <value>       Enable delete vectors through metadata
 Index.<ArgName>=<ArgValue>    Set the algorithm parameter ArgName with value ArgValue.

Memory SPTAG Index Search

bash

Usage:
./IndexSearcher [options]
Options:
-d, --dimension <value>       Dimension of vector.
-v, --vectortype <value>      Input vector data type. Default is float.
-i, --input <value>           Input query data.
-f, --filetype <value>        Input file type (DEFAULT, TXT, XVEC). Default is DEFAULT.
-x, --index <value>           Index folder.

-t, --thread <value>          Thread Number.
--delimiter <value>           Vector delimiter.
-norm, --normalized <value>   Vector is normalized.
-r, --truth <value>           Truth file.
-o, --result <value>          Output result file.
-m, --maxcheck <value>        MaxCheck for index.
-a, --withmeta <value>        Output metadata instead of vector id.
-k, --KNN <value>             K nearest neighbors for search.
-tk, --truthKNN <value>       truth set number.
-df, --data <value>           original data file.
-dft, --dataFileType <value>  original data file type. (TXT, or DEFAULT)
-b, --batchsize <value>       Batch query size.
-g, --gentruth <value>        Generate truth file.
-q, --debugquery <value>      Debug query number.
-adc, --adc <value>           Enable ADC Distance computation
Index.<ArgName>=<ArgValue>    Set the algorithm parameter ArgName with value ArgValue.

SPANN Index Build

Create a configure file buildconfig.ini as follows:

text

[Base]
ValueType=UInt8
DistCalcMethod=L2
IndexAlgoType=BKT
Dim=128
VectorPath=sift1b/base.1B.u8bin
VectorType=DEFAULT
QueryPath=sift1b/query.public.10K.u8bin
QueryType=DEFAULT
WarmupPath=sift1b/query.public.10K.u8bin
WarmupType=DEFAULT
TruthPath=sift1b/public_query_gt100.bin
TruthType=DEFAULT
IndexDirectory=sift1b
QuantizerFilePath=

[SelectHead]
isExecute=true
TreeNumber=1
BKTKmeansK=32
BKTLeafSize=8
SamplesNumber=1000
SelectThreshold=10
SplitFactor=6
SplitThreshold=25
Ratio=0.12
NumberOfThreads=45

[BuildHead]
isExecute=true
NeighborhoodSize=32
TPTNumber=32
TPTLeafSize=2000
MaxCheck=16324
MaxCheckForRefineGraph=16324
RefineIterations=3
NumberOfThreads=45

[BuildSSDIndex]
isExecute=true
BuildSsdIndex=true
InternalResultNum=64
ReplicaCount=8
PostingPageLimit=3
NumberOfThreads=45
MaxCheck=16324
TmpDir=/tmp/
SearchInternalResultNum=32
SearchPostingPageLimit=3
SearchResult=result.txt
ResultNum=10
MaxDistRatio=8.0

Then run ".\IndexBuilder.exe -c buildconfig.ini -d 128 -v UInt8 -f DEFAULT -i FromFile -o sift1b -a SPANN" to build the index.

Another build and search combined executable is SSDServing.exe which is used in the paper experiments.

For sift1b dataset, use the default configuration below (buildconfig.ini) and run .\SSDServing.exe buildconfig.ini:

text

[Base]
ValueType=UInt8
DistCalcMethod=L2
IndexAlgoType=BKT
Dim=128
VectorPath=sift1b/base.1B.u8bin
VectorType=DEFAULT
QueryPath==sift1b/query.public.10K.u8bin
QueryType=DEFAULT
WarmupPath==sift1b/query.public.10K.u8bin
WarmupType=DEFAULT
TruthPath==sift1b/public_query_gt100.bin
TruthType=DEFAULT
IndexDirectory=sift1b

[SelectHead]
isExecute=true
TreeNumber=1
BKTKmeansK=32
BKTLeafSize=8
SamplesNumber=1000
SaveBKT=false
SelectThreshold=10
SplitFactor=6
SplitThreshold=25
Ratio=0.12
NumberOfThreads=45
BKTLambdaFactor=1.0

[BuildHead]
isExecute=true
NeighborhoodSize=32
TPTNumber=32
TPTLeafSize=2000
MaxCheck=16324
MaxCheckForRefineGraph=16324
RefineIterations=3
NumberOfThreads=45
BKTLambdaFactor=-1.0

[BuildSSDIndex]
isExecute=true
BuildSsdIndex=true
InternalResultNum=64
ReplicaCount=8
PostingPageLimit=3
NumberOfThreads=45
MaxCheck=16324
TmpDir=/tmp/

[SearchSSDIndex]
isExecute=true
BuildSsdIndex=false
InternalResultNum=96
NumberOfThreads=1
HashTableExponent=4
ResultNum=10
MaxCheck=1024
MaxDistRatio=8.0
SearchPostingPageLimit=3

For sift1m dataset, use the default configuration below (buildconfig.ini) and run .\SSDServing.exe buildconfig.ini:

text

[Base]
ValueType=Float
DistCalcMethod=L2
IndexAlgoType=BKT
Dim=128
VectorPath=sift1m/sift_base.fvecs
VectorType=XVEC
QueryPath=sift1m/sift_query.fvecs
QueryType=XVEC
WarmupPath=sift1m/sift_query.fvecs
WarmupType=XVEC
TruthPath=sift1m/sift_groundtruth.ivecs
TruthType=XVEC
IndexDirectory=sift1m

[SelectHead]
isExecute=true
TreeNumber=1
BKTKmeansK=32
BKTLeafSize=8
SamplesNumber=1000
SaveBKT=false
SelectThreshold=50
SplitFactor=6
SplitThreshold=100
Ratio=0.16
NumberOfThreads=64
BKTLambdaFactor=-1

[BuildHead]
isExecute=true
NeighborhoodSize=32
TPTNumber=32
TPTLeafSize=2000
MaxCheck=8192
MaxCheckForRefineGraph=8192
RefineIterations=3
NumberOfThreads=64
BKTLambdaFactor=-1

[BuildSSDIndex]
isExecute=true
BuildSsdIndex=true
InternalResultNum=64
ReplicaCount=8
PostingPageLimit=12
NumberOfThreads=64
MaxCheck=8192
TmpDir=/tmp/

[SearchSSDIndex]
isExecute=true
BuildSsdIndex=false
InternalResultNum=32
NumberOfThreads=1
HashTableExponent=4
ResultNum=10
MaxCheck=2048
MaxDistRatio=8.0
SearchPostingPageLimit=12

Quantizer Training and Quantizing Vectors

Use Quantizer.exe to train PQQuantizer and output quantizer & quantized vectors:

bash

Usage:
./Quantizer [options]
Options:
-d, --dimension <value>                 Dimension of vector.
-v, --vectortype <value>                Input vector data type. Default is float.
-f, --filetype <value>                  Input file type (DEFAULT, TXT, XVEC). Default is DEFAULT.
-i, --input <value>                     Input raw data.
-o, --output <value>                    Output quantized vectors.
-om, --outputmeta <value>               Output metadata.
-omi, --outputmetaindex <value>         Output metadata index.

-t, --thread <value>                    Thread Number.
-dl, --delimiter <value>                Vector delimiter.
-norm, --normalized <value>             Vector is normalized.
-oq, --outputquantizer <value>          Output quantizer.
-qt, --quantizer <value>                Quantizer type.
-qd, --quantizeddim <value>             Quantized Dimension.
-ts, --train_samples <value>            Number of samples for training.
-debug, --debug <value>                 Print debug information.
-kml, --lambda <value>                  Kmeans lambda parameter.

Input File Format

DEFAULT (Binary)

Input raw data for index build and input query file for index search (suppose vector dimension is 3):

text

<4 bytes int representing num_vectors><4 bytes int representing num_dimension>
<num_vectors * num_dimension * sizeof(data type) bytes raw data>

Truth file to calculate recall (suppose K is 2):

text

< 4 bytes int representing num_queries><4 bytes int representing K>
<num_queries * K * sizeof(int) representing truth neighbor ids>

TXT

Input raw data for index build and input query file for index search (suppose vector dimension is 3):

text

<metadata1>\t<v11>|<v12>|<v13>|
<metadata2>\t<v21>|<v22>|<v23>|
...

where each line represents a vector with its metadata and its value separated by a tab space. Each dimension of a vector is separated by | or use --delimiter to define the separator.

Truth file to calculate recall (suppose K is 2):

text

<t11> <t12>
<t21> <t22>
...

where each line represents the K nearest neighbors of a query separated by a blank space. Each neighbor is given by its vector id.

Meta Files Format

Data for index build to provide the metadata of the vectors. There are two files:

meta.bin

text

<vector 1 meta><vector 2 meta>...

metaindex.bin

text

<4 bytes int representing num_vectors><sizeof(uint64_t)*(num_vectors + 1) bytes representing position_array where the meta start and end positions in meta.bin for vector i is position_array[i] and position_array[i+1] respectively>

Quantizer File Format

Data for using PQ quantizer in index build and index search

text

<1 byte uint8 representing QuantizerType -- 0: NONE, 1: PQ, 2: OPQ><1 byte uint8 representing ReconstructDataType -- 0: int8, 1: uint8, 2: int16, 3: float><4 bytes int representing num_codebooks><4 bytes int representing entries_per_codebook><4 bytes int representing codebook_dim>
<sizeof(ReconstructType)*num_codebooks*entries_per_codebook*codebook_dim representing codebook entries>[<sizeof(float) * reconstruct_dim * reconstruct_dim representing OPQ rotation matrix, row major order>]

Note that num_codebooks*codebook_dim=full_dim. The current PQ implementation only supports entries_per_codebook <= 256 (i.e. quantizing to byte).

Server

bash

Usage:
./Server [options]
Options: 
  -m, --mode <value>              Service mode, interactive or socket.
  -c, --config <value>            Configure file of the index

Write a server configuration file service.ini as follows:

[Service]
ListenAddr=0.0.0.0
ListenPort=8000
ThreadNumber=8
SocketThreadNumber=8

[QueryConfig]
DefaultMaxResultNumber=6
DefaultSeparator=|

[Index]
List=BKT

[Index_BKT]
IndexFolder=BKT_gist

Client

bash

Usage:
./Client [options]
Options:
-s, --server                       Server address
-p, --port                         Server port
-t,                                Search timeout
-cth,                              Client Thread Number
-sth                               Socket Thread Number

Aggregator

bash

Usage:
./Aggregator

Write Aggregator.ini as follows:

[Service]
ListenAddr=0.0.0.0
ListenPort=8100
ThreadNumber=8
SocketThreadNumber=8

[Servers]
Number=2

[Server_0]
Address=127.0.0.1
Port=8000

[Server_1]
Address=127.0.0.1
Port=8010

Python Support

Singlebox PythonWrapper

text

/* Detailed source-code truncated for AI context efficiency. */

Python Client Wrapper, Suppose there is a sever run at 127.0.0.1:8000 serving ten-dimensional vector datasets:

python

import SPTAGClient
import numpy as np
import time

def testSPTAGClient():
   index = SPTAGClient.AnnClient('127.0.0.1', '8000')
   while not index.IsConnected():
       time.sleep(1)
   index.SetTimeoutMilliseconds(18000)

   q = np.ones((10, 10), dtype=np.float32)
   for t in range(q.shape[0]):
       result = index.Search(q[t], 6, 'Float', False)
       print (result[0])
       print (result[1])

if __name__ == '__main__':
   testSPTAGClient()

C# Support

Singlebox CsharpWrapper

using System;
using System.Text;

public class test
{
   static int dimension = 10;
   static int n = 10;
   static int k = 3;

   static byte[] createFloatArray(int n)
   {
       byte[] data = new byte[n * dimension * sizeof(float)];
       for (int i = 0; i < n; i++)
           for (int j = 0; j < dimension; j++)
               Array.Copy(BitConverter.GetBytes((float)i), 0, data, (i * dimension + j) * sizeof(float), 4);
       return data;
   }

   static byte[] createMetadata(int n)
   {
       StringBuilder sb = new StringBuilder();
       for (int i = 0; i < n; i++)
           sb.Append(i.ToString() + '\n');
       return Encoding.ASCII.GetBytes(sb.ToString());
   }

   static void Main()
   {
       {
           AnnIndex idx = new AnnIndex("BKT", "Float", dimension);
           idx.SetBuildParam("DistCalcMethod", "L2", "Index");
           byte[] data = createFloatArray(n);
           byte[] meta = createMetadata(n);
           idx.BuildWithMetaData(data, meta, n, false, false);
           idx.Save("testcsharp");
       }

       AnnIndex index = AnnIndex.Load("testcsharp");
       BasicResult[] res = index.SearchWithMetaData(createFloatArray(1), k);
       for (int i = 0; i < res.Length; i++)
           Console.WriteLine("result " + i.ToString() + ":" + res[i].Dist.ToString() + "@(" + res[i].VID.ToString() + "," + Encoding.ASCII.GetString(res[i].Meta) + ")"); 
       Console.WriteLine("test finish!");
   }
}

File: docs/LinuxInstallation.md

Setup SPTAG on Ubuntu

In this section, will describe how to setup SPTAG on Ubuntu machine.

Update ubuntu and build env

text

sudo apt-get update && sudo apt-get install build-essential

Install cmake

Download cmake. You can find the cmake releases here.

bash

# e.g. download cmake version 3.14.7
wget https://github.com/Kitware/CMake/releases/download/v3.14.7/cmake-3.14.7-Linux-x86_64.sh -P opt/

Follow these instructions:
1. chmod +x opt/cmake-3.<your_version>.sh (chmod makes the script executable)
2. sudo bash opt/cmake-3.<your_version>.sh
3. The script installs to a target directory so in order to get the cmake command, make a symbolic link from the target directory where cmake was extracted to: sudo ln -s <target_directory>/cmake-3.<your_version>/bin/* /usr/local/bin
4. cmake --version Note: If you encounter this error: The program 'cmake' is currently not installed, Please try the command from step 3 again with a full path (e.g. sudo ln -s /home/<your name>/SPTAG/opt/cmake-3.<your_version>-Linux-x86_64/bin/* /usr/local/bin)

Install boost

Download boost 1.67 version:

bash

wget https://netix.dl.sourceforge.net/project/boost/boost/1.67.0/boost_1_67_0.tar.gz

(There are some version mis-matching issues and reported on github issue)

Extract and install

bash

tar -xzvf boost*
cd boost_1_67_0
./bootstrap.sh --prefix=/usr/local
./b2
sudo ./b2 install
sudo apt-get install swig

Generate a Release folder in the code directory which will contain all the build targets:

bash

mkdir build
cd build && cmake .. && make

Add SPTAG module to python path

bash

# so python can find the SPTAG module
ENV PYTHONPATH=/app/Release

File: docs/Parameters.md

Parameters

Common Parameters

ParametersName	type	default	definition
Samples	int	1000	how many points will be sampled to do tree node split
TPTNumber	int	32	number of TPT trees to help with graph construction
TPTLeafSize	int	2000	TPT tree leaf size
NeighborhoodSize	int	32	number of neighbors each node has in the neighborhood graph
GraphNeighborhoodScale	int	2	number of neighborhood size scale in the build stage
CEF	int	1000	number of results used to construct RNG
MaxCheckForRefineGraph	int	10000	how many nodes each node will visit during graph refine in the build stage
NumberOfThreads	int	1	number of threads to uses for speed up the build
DistCalcMethod	string	Cosine	choose from Cosine and L2
MaxCheck	int	8192	how many nodes will be visited for a query in the search stage

BKT

ParametersName	type	default	definition
BKTNumber	int	1	number of BKT trees
BKTKMeansK	int	32	how many childs each tree node has

KDT

ParametersName	type	default	definition
KDTNumber	int	1	number of KDT trees

Parameters that will affect the index size

NeighborhoodSize
BKTNumber
KDTNumber

Parameters that will affect the index build time

NumberOfThreads
TPTNumber
TPTLeafSize
GraphNeighborhoodScale
CEF
MaxCheckForRefineGraph

Parameters that will affect the index quality

TPTNumber
TPTLeafSize
GraphNeighborhoodScale
CEF
MaxCheckForRefineGraph
NeighborhoodSize
KDTNumber

Parameters that will affect search latency and recall

MaxCheck

NNI for parameters tuning

Prepare vector data file data.tsv, query data file query.tsv, and truth file truth.txt following the format introduced in the Get Started.

Install microsoft nni and write the following python code (nni_sptag.py), parameter search space configuration (search_space.json) and nni environment configuration (config.yml).

nni_sptag.py

python

import nni
import os

vector_dimension = 10
vector_type = 'Float'
index_algo = 'BKT'
threads = 32
k = 3

def main():
    para = nni.get_next_parameter()
    cmd_build = "./indexbuilder -d %d -v %s -i data.tsv -o index -a %s -t %d " % (vector_dimension, vector_type, index_algo, threads)
    for p, v in para.items():
        cmd_build += "Index." + p + "=" + str(v)
    cmd_test = "./indexsearcher index Index.QueryFile=query.tsv Index.TruthFile=truth.txt Index.K=%d" % (k)
    os.system(cmd_build)
    os.system(cmd_test + " > out.txt")
    with open("out.txt", "r") as fd:
        lines = fd.readlines()
        res = lines[-2]
        segs = res.split()
        recall = float(segs[-2])
        avg_latency = float(segs[-5])
    score = recall
    nni.report_final_result(score)

if __name__ == '__main__':
    main()

search_space.json

json

{
        "BKTKmeansK": {"_type": "choice", "_value": [2, 4, 8, 16, 32]},
        "GraphNeighborhoodScale": {"_type": "choice", "_value": [2, 4, 8, 16, 32]}
}

config.yml

yaml

authorName: default

experimentName: example_sptag

trialConcurrency: 1

maxExecDuration: 1h

maxTrialNum: 10

#choice: local, remote, pai

trainingServicePlatform: local

searchSpacePath: search_space.json

#choice: true, false

useAnnotation: false

tuner:

  #choice: TPE, Random, Anneal, Evolution, BatchTuner, MetisTuner

  #SMAC (SMAC should be installed through nnictl)

  builtinTunerName: TPE

  classArgs:

    #choice: maximize, minimize

    optimize_mode: maximize

trial:

  command: python3 nni_sptag.py

  codeDir: .

  gpuNum: 0

Then start the tuning (tunning results can be found in the Web UI urls in the command output):

bash

nnictl create --config config.yml

stop the tunning:

bash

nnictl stop

File: docs/WindowsInstallation.md

Requirements

swig >= 3.0

Steps to install SWIG:

Download the latest SWIG binary from http://www.swig.org/download.html, if you need a specific version, windows binaries are located at https://sourceforge.net/projects/swig/files/swigwin/. Once downloaded, please unzip to a local folder (prefarably inside the SPTAG folder)
Add the path where it was unzipped to the environment PATH example: C:\Sptag\swigwin-3.0.12\ in System properties

cmake >= 3.12.0

If you have Visual Studio 2019 you already have the required tools to compile, please ensure you have the Desktop Development with C++ selected to get all the tools, just ensure this option is enabled in the installation workloads
If not, please download cmake

boost == 1.67.0

Boost's precompiled binaries are available at https://sourceforge.net/projects/boost/files/boost-binaries/1.67.0/ (to avoid compiling from scratch)

Select the lastest version for 1.67.0 (boost_1_67_0-msvc-14.1-64.exe)
Launch the installation
Add the folder path to PATH environment variable, for instance C:\Sptag\boost_1_67_0\

On the off chance of needing to build boost, because you encountered this message during the Build step Could NOT find Boost (missing: system thread serialization wserialization regex filesystem), try the following

Locate and run bootstrap.bat, this creates a file called b2.exe
Run the generated exe (in this case b2.exe), be patient this may take +1 hr
Once complete, the built libraries will be located in \stage\lib (or something along the lines)

Build

git clone microsoft/SPTAG
Go the folder location where you cloned the repo in the command prompt and execute the following commands:

text

mkdir build
cd build
cmake -A x64 ..

From the build folder, open SPTAGLib.sln solution in Visual Studio and compile all projects
[..]/build/release contains now all components needed, add this path to PYTHONPATH environment variable to reference the required modules

File: Script_AE/iniFile/README.md

If want to generate these data

In our paper, we use SIFT and SPACEV dataset and synthetic benchmark.
these dataset can be download here：

text

http://big-ann-benchmarks.com/neurips21.html

Download Dataset

bash

wget https://dl.fbaipublicfiles.com/billion-scale-ann-benchmarks/bigann/base.1B.u8bin
wget https://comp21storage.blob.core.windows.net/publiccontainer/comp21/spacev1b/spacev1b_base.i8bin

Download Query

bash

wget https://dl.fbaipublicfiles.com/billion-scale-ann-benchmarks/bigann/query.public.10K.u8bin
wget https://comp21storage.blob.core.windows.net/publiccontainer/comp21/spacev1b/query.i8bin

To generate dataset for Overall Performance

bash

# generate dataset for index build
python generate_dataset.py --src source_file_path --dst output_file_path --topk 100000000
# generate dataset for update
python generate_dataset.py --src source_file_path --dst output_file_path --topk 200000000

To generate trace for Overall Performance & generate truth for Overall Performance

This will takes hundreds of hours to generate groundTruth (the nearest K vectors of all queries) without GPU support

bash

bash generateOverallPerformanceTraceAndTruth.sh

To generate trace for Stress Test

bash

/home/sosp/SPFresh/Release/usefultool -GenStress true --vectortype UInt8 --VectorPath /home/sosp/data/sift_data/base.1B.u8bin --filetype DEFAULT --UpdateSize 10000000 --BaseNum 1000000000 --TraceFileName bigann1b_update_trace -d 128 --Batch 20 -f DEFAULT

To generate SPANN Index for Overall Peformance

build base SPANN Index

This will takes 1 days to generate SPANN Index of SPACEV100M with a 160 threads machine (we build it offline)

bash

/home/sosp/SPFresh/Release/ssdserving build_SPANN_spacev100m.ini
mv iniFile/store_spacev100m/*.ini /home/sosp/data/store_spacev100m

To generate DiskANN Index for Overall Performance

This will takes 0.5 days to generate DiskANN Index of SPACEV100M with a 160 threads machine (we build it offline)

bash

mkdir /home/yuming/data/store_diskann_100m
/home/sosp/DiskANN_Baseline/build/tests/build_disk_index int8 /home/sosp/data/spacev_data/spacev100m_base.i8bin /home/yuming/data/store_diskann_100m/diskann_spacev_100m_ 64 75 128 128 16 l2 0

To generate SPANN Index for Stress Test

This will takes 5 days to generate SPANN Index of SPACEV100M with a 160 threads machine (we build it offline)

bash

/home/sosp/SPFresh/Release/ssdserving build_SPANN_sift1b.ini
mv iniFile/store_sift1b/indexloader_stress.ini /home/sosp/data/store_sift_cluster/indexloader.ini

To generate data for figure 1,9,10

bash

# using sift
python generate_dataset.py --src /home/sosp/data/sift_data/base.1B.u8bin --dst /home/sosp/data/sift_data/bigann2m_base.u8bin --topk 2000000
# this command require numpy and sklearn
python data_clustering_sift.py --src /home/sosp/data/sift_data/bigann2m_base.u8bin --dst /home/sosp/data/sift_data/bigann1m_update_clustering
mv /home/sosp/data/sift_data/bigann1m_update_clustering0 /home/sosp/data/sift_data/bigann1m_update_clustering
mv /home/sosp/data/sift_data/bigann1m_update_clustering1 /home/sosp/data/sift_data/bigann1m_update_clustering_trace0
mv /home/sosp/data/sift_data/bigann1m_update_clustering2 /home/sosp/data/sift_data/bigann2m_update_clustering
#generate truth
/home/sosp/SPFresh/Release/ssdserving genTruth_clustering.ini
mv /home/sosp/data/sift_data/bigann2m_update_clustering_origin_truth0 /home/sosp/data/sift_data/bigann2m_update_clustering_origin_truth

#build index
/home/sosp/SPFresh/Release/ssdserving build_clustering_1m.ini
mv iniFile/store_sift_cluster/*.ini /home/sosp/data/store_sift_cluster/
/home/sosp/SPFresh/Release/ssdserving build_clustering_2m.ini
mv iniFile/store_sift_cluster_2m/indexloader_clustering_2m.ini /home/sosp/data/store_sift_cluster/indexloader.ini

To generate data for figure 11

bash

python generate_dataset.py --src /home/sosp/data/sift_data/base.1B.u8bin --dst /home/sosp/data/sift_data/bigann1m_base.u8bin --topk 1000000
# build index
/home/sosp/SPFresh/Release/ssdserving build_sift1m.ini
mv iniFile/store_sift1m/indexloader_sift1m.ini /home/sosp/data/store_sift1m/indexloader.ini

File: Script_AE/README.md

Reproduce All Experiment Results(Result Reproduced)

In this folder, we provide scripts for reproducing figures in our paper. A Standard_L16s_v3 instance is needed to reproduce all the results.

The name of each script corresponds to the number of each figure in our paper. Since some of the scripts in this directory take a long computing time (as we mark below), we strongly recommend you create a tmux session to avoid script interruption due to network instability.

Dataset and Benchmark

For artifact evaluation, we strongly recommend the reviewers to use those pre-downloaded and built dataset and benchmark in the ~/data/ folder on the provided Lsv3 instance, since the provided index and dataset requires lots of computation resource and takes about two weeaks to generate these data in a 80-core machine (we build these data offline)

To generate data, you can refer to ./Script_AE/iniFile/README.md.

Additional Setup

here is additional setup for evaluation

How to check current state

if we can not see the /dev/nvme0n1 after the following command, it means this disk has been taken over by SPDK
Using SPDK will bind the disk to SPDK and the /dev/nvme0n1 will not be shown after "lsblk"

bash

lsblk

If the device has been binded to SPDK, the following command can reset

bash

sudo ./SPFresh/ThirdParty/spdk/scripts/setup.sh reset

SPFresh & SPANN+

Since we use SPDK to build our storage, we need to bind PCI dev to SPDK

bash

sudo nvme format /dev/nvme0n1
sudo ./SPFresh/ThirdParty/spdk/scripts/setup.sh
cp bdev.json /home/sosp/SPFresh/

DiskANN

DiskANN Baseline use the filesystem provided by kernel to maintain its on-disk file, so if we want to run DiskANN, we need to release the disk from SPDK

bash

sudo ./SPFresh/ThirdParty/spdk/scripts/setup.sh reset

Prepare DiskANN for evaluation

bash

sudo mkfs.ext4 /dev/nvme0n1
sudo mount /dev/nvme0n1 /home/sosp/testbed
sudo chmod 777 /home/sosp/testbed

If you want to switch Evaluation from DiskANN to SPFresh, you must umount the filesystem at first and follow the above SPDK command

bash

sudo umount /home/sosp/testbed
sudo nvme format /dev/nvme0n1
sudo ./SPFresh/ThirdParty/spdk/scripts/setup.sh

Start to Run

all files for running is already set in those folders in Azure VM for AE.

Motivation (Figure 1)

It takes about 22 minutes

bash

bash motivation.sh

Plot the result

bash

bash plot_motivation_result.sh

Overall Performance (Figure 6)

It takes about 6 days to reproduce this figure

SPFresh

This takes about 43 hours and 50 minutes

bash

bash overall_spacev_spfresh.sh

SPANN+

This takes about 43 hours and 30 minutes

bash

bash overall_spacev_spann.sh

DiskANN

Before running, move DiskANN Index to the disk (if binded by SPDK, First reset and mkfs (follow the instruction above))

bash

cp -r /home/sosp/data/store_diskann_100m /home/sosp/testbed

This takes about 35 hours and 44 minutes

bash

bash overall_spacev_diskann.sh

Plot the result of the baselines

bash

bash plot_overall_result.sh

Disk IOPS Limitation (Figure 7)

This takes about 5 minutes

bash

bash iops_limitation.sh

Plot the result

bash

bash plot_iops_result.sh

Stress Test (Figure 8)

This takes about 35 hours and 26 minutes

bash

bash stress_spfresh.sh

Plot the result

bash

bash plot_stress_result.sh

Data Shifting Micro-benchmark (Figure 9)

This takes about 1 hours and 10 minutes

bash

bash data_shifting.sh

Plot the result

bash

bash plot_shifting_result.sh

Parameter Study: Reassign Range (Figure 10)

This takes about 1 hours and 30 minutes

bash

bash parameter_study_range.sh

Plot the result

bash

bash plot_range_result.sh

Foreground Scalability (Figure 11)

This takes about 11 minutes

bash

bash parameter_study_balance.sh

Plot the result

bash

bash plot_balance_result.sh

File: Tools/OPQ/README.md

OPQ gpu training and inference tool

Package Requirements (tbd)

Python>=3.7
numpy>=1.18.1
faiss>=1.7.0

Parameter Sample

--data_file [input_path]\vectors.bin.0 --query_file [model_path]\query.bin --output_truth [output_path] --output_dir [output_path]\5474\cluster_unzip --task 0 --data_type float32 --k 5 --dim 1024 --B 1000000 --Q 1000 --D L2 --data_format DEFAULT --T 18 --train_samples 1000000 --quan_type opq --quan_dim 1024 --output_quantizer quantizer.bin --output_quan_vector_file dssm_vectors.bin --output_rec_vector_file vectors.bin --quan_test 1 --data_normalize 0 --query_normalize 0

Example

python3 OPQ_gpu_train_infer.py --data_file perftest_vector.bin --query_file perftest_query.bin --task 0 --data_type float32 --k 5 --dim 64 --B 1000000 --Q 1000 --D L2 --data_format DEFAULT --T 20 --train_samples 1000000 --quan_type opq --quan_dim 32 --output_quantizer quantizer.bin

File: Tools/nni-auto-tune/README.md

ANN-auto-tune using NNI

Requirements

This example requires NNI >= 2.8, python == 3.6/3.8

pip install nni

For more details, please view NNI installation

Install SPTAG

pip install -i https://test.pypi.org/simple/ sptag

Install other dependencies

pip install multiprocess

Dataset

We support muiltiple types of data for training. Including text file, binary file and ann-benchmark format hdf5 file. But the groundturth file should only be texts of index.

In many cased, parameters that works fine in sampled dataset also work in original dataset. So we also provided a preprocessing script for dataset sampling and ground truth calculation. You can use follow command to do sample and ground truth pre-calculate.

python preprocessing.py --train_file victors.bin --query_file query.bin --output_dir sampled/ --distance euclidean  --num_sample 100000

If you only need to calculate ground truth for time save in auto-tune, which we highly recommend, you can set --num_sample to -1

Quickstart

Use this command to start a NNI trial to tune SPTAG model on ann-benchmark format hdf5 sift-128-euclidean dataset.

nnictl create --config config.yml

If you wish to tune SPTAG on a binary dataset or text dataset, the input file format are as below.

DEFAULT (Binary)

Input raw data for index build and input query file for index search (suppose vector dimension is 3):

text

<4 bytes int representing num_vectors><4 bytes int representing num_dimension>
<num_vectors * num_dimension * sizeof(data type) bytes raw data>

TXT

Input raw data for index build and input query file for index search (suppose vector dimension is 3):

text

<metadata1>\t<v11>|<v12>|<v13>|
<metadata2>\t<v21>|<v22>|<v23>|
...

where each line represents a vector with its metadata and its value separated by a tab space. Each dimension of a vector is separated by | or use --delimiter to define the separator.

Truth file to calculate recall (suppose K is 2):

text

<t11> <t12>
<t21> <t22>
...

where each line represents the K nearest neighbors of a query separated by a blank space. Each neighbor is given by its vector id.

Then you can change trialCommand in config.yml to:

python main.py --train_file victors.bin --query_file query.bin --label_file truth.txt --distance euclidean

You can also specify --max_build_time or --max_memory if you have build time limit or search memory usage limit in your project. they both default to -1, which mean no limit.

NOTE: Always clear corresponding folder under results/ before starting a trial on same dataset.

Results

Install matplotlib for figure drawing

pip install matplotlib

During the trial, the results are saved as json files in results/(dataset_name). Use following command to visualize results.

plot.py --path sift-128-euclidean

The figure shows the correspondence between recall and qps. And you can see the details of each selected point in console.

The following are the results of sptag and other algorithms on different datasets

sift-128-euclidean

glove-100-angular

glove-25-angular

nytimes-256-angular

fashion-mnist-784-euclidean

2. Official Technical Reference & Guides (microsoft/microsoft.github.io)

[microsoft.github.io](https://microsoft.github.io)

Many open source projects released by Microsoft products, services and teams also have
deployments powered by GitHub Pages on this domain.

To discover Microsoft-released open source projects, learn about Microsoft's open source
approach and other information, check us out online at opensource.microsoft.com.

If we can help answer questions about the open source program at Microsoft, you can
contact opensource at microsoft com - although we are not able to provide support
for projects through this mechanism.

Microsoft GitHub resources

Default repo templates including SECURITY.MD and code of conduct files: microsoft/repo-templates
Code of Conduct (FAQ)

Microsoft open source resources

Resources for Microsoft employees

How to identify an official Microsoft organization on GitHub

Official Microsoft GitHub orgs have a professional avatar and include a web address at Microsoft.com or an associated official domain
Official Microsoft orgs are Verified on GitHub - look for the domain verification indicator on GitHub

Docker & Self-Hosted Deployment Verified OCI

1. Project Overview & Quickstart (microsoft/SPTAG) Copy Chapter

File: README.md Copy Chapter

SPTAG: A library for fast approximate nearest neighbor search

**SPTAG** Copy Chapter

What's NEW Copy Chapter

**Introduction** Copy Chapter

**How it works** Copy Chapter

**Highlights** Copy Chapter

**Build** Copy Chapter

**Requirements** Copy Section

**Fast clone** Copy Section

**Install** Copy Section

**Verify** Copy Section

**Usage** Copy Section

**References** Copy Chapter

**Contribute** Copy Chapter

**License** Copy Chapter

File: datasets/SPACEV1B/README.md Copy Chapter

SPACEV1B: A billion-Scale vector dataset for text descriptors

Introduction Copy Chapter

How to read the vectors, queries, and truth Copy Chapter

License Copy Chapter

File: docs/GettingStart.md Copy Chapter

**Quick start** Copy Chapter

**Memory SPTAG Index Build** Copy Section

**Memory SPTAG Index Search** Copy Section

**SPANN Index Build** Copy Section

**Quantizer Training and Quantizing Vectors** Copy Section

**Input File Format** Copy Section

DEFAULT (Binary)

TXT

**Meta Files Format** Copy Section

meta.bin

metaindex.bin

**Quantizer File Format** Copy Section

**Server** Copy Section

**Client** Copy Section

**Aggregator** Copy Section

**Python Support** Copy Section

**C# Support** Copy Section

File: docs/LinuxInstallation.md Copy Chapter

Setup SPTAG on Ubuntu

File: docs/Parameters.md Copy Chapter

**Parameters** Copy Chapter

**NNI for parameters tuning** Copy Chapter

File: docs/WindowsInstallation.md Copy Chapter

Requirements Copy Chapter

swig >= 3.0 Copy Section

cmake >= 3.12.0 Copy Section

boost == 1.67.0 Copy Section

Build Copy Chapter

File: Script_AE/iniFile/README.md Copy Chapter

**If want to generate these data** Copy Chapter

File: Script_AE/README.md Copy Chapter

**Reproduce All Experiment Results(Result Reproduced)**

**Dataset and Benchmark** Copy Chapter

**Additional Setup** Copy Chapter

**How to check current state** Copy Section

**SPFresh & SPANN+** Copy Section

**DiskANN** Copy Section

**Start to Run** Copy Chapter

**Motivation (Figure 1)** Copy Section

**Overall Performance (Figure 6)** Copy Section

**SPFresh**

**SPANN+**

**DiskANN**

**Plot the result of the baselines**

**Disk IOPS Limitation (Figure 7)** Copy Section

**Stress Test (Figure 8)** Copy Section

**Data Shifting Micro-benchmark (Figure 9)** Copy Section

**Parameter Study: Reassign Range (Figure 10)** Copy Section

**Foreground Scalability (Figure 11)** Copy Section

File: Tools/OPQ/README.md Copy Chapter

OPQ gpu training and inference tool

Package Requirements (tbd) Copy Chapter

Parameter Sample Copy Chapter

Example Copy Chapter

File: Tools/nni-auto-tune/README.md Copy Chapter

ANN-auto-tune using NNI

1. Project Overview & Quickstart (microsoft/SPTAG)

File: README.md

SPTAG

What's NEW

Introduction

How it works

Highlights

Build

Requirements

Fast clone

Install

Verify

Usage

References

Contribute

License

File: datasets/SPACEV1B/README.md

Introduction

How to read the vectors, queries, and truth

License

File: docs/GettingStart.md

Quick start

Memory SPTAG Index Build

Memory SPTAG Index Search

SPANN Index Build

Quantizer Training and Quantizing Vectors

Input File Format

Meta Files Format

Quantizer File Format

Server

Client

Aggregator

Python Support

C# Support

File: docs/LinuxInstallation.md

File: docs/Parameters.md

Parameters

NNI for parameters tuning

File: docs/WindowsInstallation.md

Requirements

swig >= 3.0

cmake >= 3.12.0

boost == 1.67.0

Build

File: Script_AE/iniFile/README.md

If want to generate these data

File: Script_AE/README.md

Reproduce All Experiment Results(Result Reproduced)

Dataset and Benchmark

Additional Setup

How to check current state

SPFresh & SPANN+

DiskANN

Start to Run

Motivation (Figure 1)

Overall Performance (Figure 6)

SPFresh

SPANN+

DiskANN

Plot the result of the baselines

Disk IOPS Limitation (Figure 7)

Stress Test (Figure 8)

Data Shifting Micro-benchmark (Figure 9)

Parameter Study: Reassign Range (Figure 10)

Foreground Scalability (Figure 11)

File: Tools/OPQ/README.md

Package Requirements (tbd)

Parameter Sample

Example

File: Tools/nni-auto-tune/README.md

Requirements

Dataset

Quickstart

Results

sift-128-euclidean

glove-100-angular

glove-25-angular

nytimes-256-angular

fashion-mnist-784-euclidean

2. Official Technical Reference & Guides (microsoft/microsoft.github.io)