SPANN: Highly-efficient Billion-scale Approximate Nearest Neighborhood Search
Authors: Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, Jingdong Wang
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiment results demonstrate that SPANN is 2 faster than the state-of-the-art ANNS solution Disk ANN to reach the same recall quality 90% with same memory cost in three billion-scale datasets. In this section we first present the experimental comparison of SPANN with the current state-of-the-art ANNS algorithms. Then we conduct the ablation studies to further analyze the contribution of each technique. Finally, we setup an experiment to demonstrate the scalability of SPANN solution in the distributed search scenario. |
| Researcher Affiliation | Collaboration | 1Microsoft 2Peking University 3Tencent 4Baidu |
| Pseudocode | No | The paper does not include a clearly labeled pseudocode or algorithm block. |
| Open Source Code | Yes | Code is available at: https://github.com/microsoft/SPTAG. |
| Open Datasets | Yes | SIFT1M dataset [3] is the most commonly used dataset generated from images for evaluating the performance of memory-based ANNS algorithms. SIFT1B dataset [3] is a classical dataset for evaluating the performance of ANNS algorithms that support large scale vector search. DEEP1B dataset [8] is a dataset learned from deep image classification model. SPACEV1B dataset [6](O-UDA license) is a dataset from commercial search engine which derives from production data. |
| Dataset Splits | Yes | The workload is evenly split into three sets: train, valid and test. The train set is used in offline distributed index build, and the test set is used in the online search evaluation. |
| Hardware Specification | Yes | We conduct all the experiments on a workstation machine with Ubuntu 16.04.6 LTS, which is equipped with two Intel Xeon 8171M CPU (2600 MHz frequency and 52 CPU cores), 128GB memory and 2.6TB SSD organized in RAID-0. |
| Software Dependencies | No | The paper mentions SPTAG [12] (MIT license) and general operating system (Ubuntu 16.04.6 LTS), but does not provide specific version numbers for software libraries, frameworks, or programming languages used in the experiments. |
| Experiment Setup | Yes | For all the experiments in this section, we use the following hyperparameters for SPANN: 1) use at most 8 closure replicas for each vector in the closure clustering assignment; 2) limit the max posting list size to 12KB for byte vectors and 48KB for float vectors; 3) set ϵ1 for posting list expansion to 10.0, and set ϵ2 for query-aware dynamic pruning with recall@1 and recall@10 to 0.6 and 7.0 , respectively. |