microsoft/SPTAG — 5.0k★ trên GitHub (C++). 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.
Tóm tắt dựng từ metadata GitHub của chính dự án — chưa có bài review TopGit. Trang sẽ tự động cập nhật khi bài review đầy đủ được xuất bản.
VÌ SAO CHƯA CÓ REVIEW
TopGit viết bài đầy đủ cho repo có nhiều sao nhất và được yêu cầu nhiều nhất. Trang này là snapshot trong thời gian chờ — xem README gốc ở tab READ ME.
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
cd ThirdParty/spdk
./scripts/pkgdep.sh
CC=gcc-9 ./configure
CC=gcc-9 make -j
Compile isal-l_crypto
cd ThirdParty/isal-l_crypto
./autogen.sh
./configure
make -j
Build RocksDB
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
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:
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:
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:
@inproceedings{xu2023spfresh,
title={SPFresh: Incremental In-Place Update for Billion-Scale Vector Search},
author={Xu, Yuming and Liang, Hengyu and Li, Jin and Xu, Shuotao and Chen, Qi and Zhang, Qianxi and Li, Cheng and Yang, Ziyue and Yang, Fan and Yang, Yuqing and others},
booktitle={Proceedings of the 29th Symposium on Operating Systems Principles},
pages={545--561},
year={2023}
}
@inproceedings{zhang2023vbase,
title={$\{$VBASE$\}$: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity},
author={Zhang, Qianxi and Xu, Shuotao and Chen, Qi and Sui, Guoxin and Xie, Jiadong and Cai, Zhizhen and Chen, Yaoqi and He, Yinxuan and Yang, Yuqing and Yang, Fan and others},
booktitle={17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23)},
year={2023}
}
@inproceedings{ChenW21,
author = {Qi Chen and
Bing Zhao and
Haidong Wang and
Mingqin Li and
Chuanjie Liu and
Zengzhong Li and
Mao Yang and
Jingdong Wang},
title = {SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search},
booktitle = {35th Conference on Neural Information Processing Systems (NeurIPS 2021)},
year = {2021}
}
@manual{ChenW18,
author = {Qi Chen and
Haidong Wang and
Mingqin Li and
Gang Ren and
Scarlett Li and
Jeffery Zhu and
Jason Li and
Chuanjie Liu and
Lintao Zhang and
Jingdong Wang},
title = {SPTAG: A library for fast approximate nearest neighbor search},
url = {https://github.com/Microsoft/SPTAG},
year = {2018}
}
@inproceedings{WangL12,
author = {Jingdong Wang and
Shipeng Li},
title = {Query-driven iterated neighborhood graph search for large scale indexing},
booktitle = {ACM Multimedia 2012},
pages = {179--188},
year = {2012}
}
@inproceedings{WangWZTGL12,
author = {Jing Wang and
Jingdong Wang and
Gang Zeng and
Zhuowen Tu and
Rui Gan and
Shipeng Li},
title = {Scalable k-NN graph construction for visual descriptors},
booktitle = {CVPR 2012},
pages = {1106--1113},
year = {2012}
}
@article{WangWJLZZH14,
author = {Jingdong Wang and
Naiyan Wang and
You Jia and
Jian Li and
Gang Zeng and
Hongbin Zha and
Xian{-}Sheng Hua},
title = {Trinary-Projection Trees for Approximate Nearest Neighbor Search},
journal = {{IEEE} Trans. Pattern Anal. Mach. Intell.},
volume = {36},
number = {2},
pages = {388--403},
year = {2014
}
Contribute
This project welcomes contributions and suggestions from all the users.
We use GitHub issues for tracking suggestions and bugs.
Trang TopGit này là một snapshot — tab "Readme" hiển thị nguyên văn README của repo (đã bỏ link, giữ ảnh). Repo GitHub ở github.com/microsoft/SPTAG là nguồn chính thức.
microsoft/SPTAG có bao nhiêu sao?
microsoft/SPTAG có 5.0k sao GitHub — tải lại trang để xem số mới nhất, hoặc xem trực tiếp github.com/microsoft/SPTAG. TopGit phản chiếu số sao của GitHub nhưng không cam kết đến từng phút.
microsoft/SPTAG có phải mã nguồn mở không?
Có — microsoft/SPTAG phát hành theo license MIT, nghĩa là mã nguồn mở để đọc, fork và (tùy license) tái sử dụng. Mã: github.com/microsoft/SPTAG.
microsoft/SPTAG còn đang phát triển không?
Commit gần nhất trên microsoft/SPTAG là 4 tháng trước (theo timestamp GitHub). Repo có 625 fork — một chỉ báo về mức độ quan tâm của cộng đồng.
microsoft/SPTAG là gì?
microsoft/SPTAG (microsoft/SPTAG) là dự án C++ trên GitHub. Theo mô tả gốc: 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.
Đọc đầy đủ README ở tab phía trên.
Vẫn đang phân vân về SPTAG?
Một cú bấm sẽ gửi câu hỏi kèm trang này cho AI — xem AI nói gì về SPTAG.