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
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: billion-scale
vector search
inverted index solution

Abstract: The in-memory algorithms for approximate nearest neighbor search (ANNS) have achieved great success for fast high-recall search, but are extremely expensive when handling very large scale database. Thus, there is an increasing request for the hybrid ANNS solutions with small memory and inexpensive solid-state drive (SSD). In this paper, we present a simple but efficient memory-disk hybrid indexing and search system, named SPANN, that follows the inverted index methodology. It stores the centroid points of the posting lists in the memory and the large posting lists in the disk. We guarantee both disk-access efficiency (low  latency) and high recall by effectively reducing the disk-access number and retrieving high-quality posting lists. In the index-building stage, we adopt a hierarchical balanced clustering algorithm to balance the length of posting lists and augment the posting list by adding the points in the closure of the corresponding clusters. In the search stage, we use a query-aware scheme to dynamically prune the access of unnecessary posting lists.  Experiment results demonstrate that SPANN is 2X faster than the state-of-the-art ANNS solution DiskANN to reach the same recall quality 90% with same memory cost in three billion-scale datasets. It can reach 90% recall@1 and recall@10 in just around one millisecond with only about 10% of original memory cost.  Code is available at: https://github.com/microsoft/SPTAG.


SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search
Qi Chen Bing 22 Haidong Wang' Mingqin Li' Chuanjie Liu
Zengzhong Li'
Mao Yang'
Jingdong Wang
Microsoft 2Peking University Tenceett "Baidu
[cheqi, haidwa, mingqli, jasol, maoyang] @micrnsoft.com
its. bingzhao pku.edu.en Sliu.chuanjie outlook.com "wangjingdong@@uullo
Abstract
The in-memory algorithms for approximate nearest neighbor search (ANNS) have achieved great success for fast high-recall search, but are extremely expensive when handling very large scale database. Thus, there is an increasing request for the hybrid ANNS solutions with small memory and inexpensive solid-state drive (SSD). In this paper, we present a simple but efficient memory-disk hybrid indexing and search system, named SPANN, that follows the inverted index methodology. It stores the centroid points of the posting lists in the memory and the large posting lists in the disk. We guarantee both disk-access efficiency (low latency) and high recall by effectively reducing the disk-access number and retrieving high- quality posting lists. In the index-building stage, we adopt a hierarchical balanced clustering algorithm to balance the length of posting lists and augment the posting list by adding the points in the closure of the corresponding clusters. In the search stage, we query-aware scheme to dynamically prune the access of unnecessary posting lists. Experiment results demonstrate that SPANN is 2x faster than the state-of-the offtth--artttt ANNS solution DiskANN reach the same recall quality 90% with same memory cost in three billion-scale datasets. It can reach 90% recall and recall @ 10 in just around one millisecond with only about 10% of original memory cost. Code is available at: hhttpa///gitae com//accroooft//PA...
billion-scale, vector search, inverted index solution
Introduction
Vector nearest neighbor search has played an important role in information retrieval area, such as multimedia search and web search, which provides relevant results by searching vectors with minimum distance to the query vector. Exact solutions for K-nearest neighbor search [49 40 not
applicable in big data scenario due to substantial computation cost and high query latency. Therefore, researchers have proposed many kinds of approximate nearest neighbor search (ANNS) algorithms in
the literature [T] 38
1O, 14
34 29
21
16 26
B3 44 37
32
19 27
[2] 39
50 20 36). However, most of the algorithms mainly focus how to do low latency and high recall search all in memory with offline pre-built indexes. When targeting to the super large scale vector search scenarios, such web search, the memory cost will become extremely expensive. There is an increasing request for the hybrid ANNS solutions that use small memory and inexpensive disk to serve the large scale datasets.
"Corresponding author.
Work done while at Microsoft.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

There are only a few approaches working on the hybrid ANNS solutions, including DiskANN 339 and HM-ANN [36]. Both of them are graph based solutions. DiskANN uses Product Quantization (PQ) 225 to compress the vectors stored in the memory while putting the navigating spread-out graph along with the full-precision vectors on the disk. When a query comes, it traverses the graph according to the distance of quantized vectors and then reranks the candidates according to distance of the full-precision vectors. HM-ANN leverages the heterogeneous memory by placing pivot points in the fast memory and navigable small world graph in the slow memory without data compression. However, it consumes more than 1.5 times larger fast memory than DiskANN. Moreover, the slow memory is still much expensive than disk. Therefore, due to the cheap serving cost, high recall and low latency advantages of DiskANN, it has become the start-of of-thee-rtt for indexing billion-scale datasets.
In this paper, we argue that the simple inverted index approach can also achieve state-of-ther art performance for large scale datasets in terms of recall, latency and memory cost. We propose SPANN, a simple but surprising efficient memory- hybrid vector indexing and search system, that follows the inverted index methodology. SPANN only stores the centroid points of the posting lists in the memory while putting the large posting lists in the disk. We guarantee both low latency and high recall by greatly reducing the number of disk accesses and improving the quality of posting lists, In the index- baiii-iiiidigg stage, we use a hierarchical balanced clustering method to balance the length of posting lists and expand the posting list by adding the points in the closure of the corresponding clusters. In the search stage, we use a query- scheme to dynamically prune the access of unnecessary posting lists. Experiment results demonstrate that SPANN is more than two times faster than the state-of-the-ar disk-bases ANNS algorithm DiskANN to reach the same recall quality 90% with same memory cost in three billion-scale datasets. It can reach 90% recall @ and recall @ 10 in just around one millisecond with only about 10% of original memory cost. SPANN has already been deployed into Microsoft Bing to support hundreds of billions scale vector search.
2 Background and Related Work
Given set of data vectors X E R= (the data set contains n vectors with m-dimensional features) and a query vector q RT, the goal of vector search is to find a vector p' from X. called nearest neighbor, such that p = arg m Dist(p. q). Similarly, we can define K K-nearest neighbors. Due to the substantial computation cost and high query latency of the exhaustive search, ANNS algorithms are designed to speedup the search for the approximiate K K-nearest neighbors in a large dataset in an acceptable amount of time. Most of the ANNS algorithms in the literature mainly focus on the fast high-recall search in the memory, including hash based methods [14 24 47 48 45 [
[51, tree based
methods [T]
33 graph based methods 21 43 32), and hybrid methods [42 12 23 22]
However, with the explosive growth of the vector scale, the memory has become the bottleneck to support large scale vector search. There are only a few approaches working on the ANNS solutions for billon-scall datasets to minimize the memory cost. They can be divided into two categories: inverted index based and graph based methods.
The inverted index based methods, such as IVFADC 26 FAISS (27] and IVFOADC+G+P () split the vector space into K Voronoi regions by KMeans clustering and only do search in a few regions that are closed to the query. To reduce the memory cost, they use vector quantization, e.g. Product Quantization (PQ) 25,, to compress the vectors and store them the memory. The inverted multi-index (IMI) 7 also uses PQ to compress vectors. It splits the feature space into multiple orthogonal subspaces and constructs a separate codebook for each subspace. The full feature space is produced as a Cartesian product of the corresponding subspaces. Multi-LOPQ uses locally optimized PQ codebook to encode the displacements in the IMI structure. GNO-IMI (8] optimizes the IMI by using non-orthogonal codebooks to produce the centroids. Although they can cut down the memory usage to less than 64GB for one billion 128 dimensional vectors, the recall @ I is very low (only around 60%) due to lossy data compression. Although they can achieve better recall by returning 10 to 100 times more candidates for further reranking, it is often not acceptable in many scenarios.
The graph based methods include DiskANN 39 and HM-ANN 36). Both of them adopt the hybrid solution. DiskANN also stores the PQ compressed vectors in the memory while storing the navigating spread-out graph along with the full- cell-preeisoon vectors on the disk. When a query comes, traverses the graph using best-first manner according to the distance of quantized vectors and then reranks
2

---

100
1114 (1.09992%%)
90
112. 90.488)
01.70%
70
60
Figure I: Example of boundary vector miss- ing due to partial search. If we search yel- low point, we will search green posting list first since the centroid of green posting list closer to the yellow point although there some boundary points (colored red) in the blue posting list that are much closer.
recali
100%
0
20
40
60
80
100
120
140
#visited postings
Figure 2: Different queries require different num- ber of posting lists for search. To recall top one result on SIFTIM dataset, we find 80% of queries only need to search 6 posting lists, while 99% of queries need to search 114 posting lists.
the candidates according to distance of the full-precision vectors. Similarly, it uses the lossy data compression which will influence the recall quality even though full-precision vector reranking can help retrieve graph traverse and candidate reranking. HM-ANN leverages the heterogeneous memory by placing pivot points promoted by the bottom-up phase in the fast memory and navigable small world graph in the slow memory without data compression. However, it will lead to more than 1.5 times larger fast memory consumption. Moreover, the slow memory is still much expensive than disk and may be available in some platforms. The theoretical analysis of the limits and the benefits of the graph based methods are given in 35
missing candidates back. The high-cost random disk accesses limit the number of
3 SPANN
In this paper, we propose SPANN, a simple but efficient vector indexing and search system, that follows the inverted index methodology. Different from previous inverted index based methods that leverage the lossy data compression to reduce the memory cost, SPANN adopts a simple memory-disk hybrid solution.
Xw). Index structure: The data vectors are divided into N posting lists (X X2, ,2....,,).... X1
X2 J... U X x The centroids of these posting lists, C1, C2, .2, CN, are stored in the memory as the fast coarse- grained index that point the location of the corresponding posting lists in the disk.
Partial search: When query q comes, we find the K closest centroids, {cal, C22. .... ciK). K N, and load the vectors in the posting lists X "*, Xix that correspond to the closest K centroids into memory for further fine-grained search.
3.1 Challenges
Posting length limitation: Since all the posting lists stored in the disk, in order reduce the disk accesses, we need to bound the length of each posting list so that it can be loaded into memory in only few disk reads. This requires lists but also balance the length of posting lists. This is very difficult due to the substantial high clustering cost and the balance partition problem itself. The imbalanced posting lists will lead to high variance of query latency especially when posting lists are stored in the disk.
not only partition the data into large number of posting
Boundary issue: The nearest neighbor vectors of a query may locate in the boundary of multiple posting lists. Since we only search a small number of relevant posting lists, some true neighbors of that located in other posting lists will be missing (lllustrated in Figure IT. If red points are only represented by the centroid of blue posting list, they will be missing in the nearest neighbor search of yellow point.
For convenience, X to denote both the matrix and the vector set.

---

Diverse search difficulty: We find that different queries may have different search difficulty. Some queries only need be searched in one or two posting lists while some queries require be searched in large number of posting lists (lllustrated in Figure 2) If we search the same number of posting lists for all queries, it will result either low recall or long latency.
All of the above challenges are the reasons why all of previous inverted index approaches adopt lossy data compression solution that stores all the compressed vectors and the posting lists in the memory.
3.2 Key techniques to address the challenges
In this paper, introduce three key techniques that solve the above challenges to enable the memory- disk hybrid solution. In the index-building stage, we firstly limit the length of the posting lists to effectively reduce the number of disk accesses for each posting list in the online search. Then we improves the quality of the posting list by expanding the points in the closure of the corresponding posting lists. This increases the recall probability of the vectors located posting lists. In the search stage, we propose a query-aware scheme to dynamically prune the access of unnecessary posting lists to ensure both high recall and low latency. The detail design of each technique will be introduced in the following sections.
the boundary of the
3.2.1 Posting length limitation
Limiting the length of posting lists means we need to partition the data vectors X into a large number of posting lists X1, X2. .x. Balancing the length of posting lists means we need to minimize the variance of the posting length Σ |X| /
To address the posting length balance problem, we can leverage the multi-constrain balanced clustering algorithm [30) to partition the vectors evenly into multiple posting lists:
N
X
N
min
X - HCI H.C
hu
(I)N), s.t.
1a=1. 11
(1)
1=1
1=1
2=1
where C E Nx is the centroids, H {0, 13 X|xN represents the cluster assignment, E is the number of vectors assigned to the i-th cluster (i.e. Xx() and À is trade-off hyper parameter between clustering and balance constraints.
1= hy
However, we find that when the vector number [ and the partition number N are very large, directly using multi-constraint balanced clustering algorithm cannot work due to the difficulty of large N-partition balanced clustering problem and the extremely high clustering cost. Therefore, we introduce a hierarchical multi-constraint balanced clustering technique (Figure 3 not only reduce the clustering time complexity from [(X] * m * N) to O(X] m * * Logs (ogx=NV) (N)) (k is a small constant) but also balance the length of posting lists. We cluster the vectors into a small number (i.e. k) of clusters iteratively until each posting list contains limit number of vectors. By using this technique, can greatly reduce not only the length of each posting list (disk accesses) but also the index build cost.
Moreover, since the number of centroids is very large, finding the nearest posting lists for query needs to consume large computation cost. In order to make the navigating computation more meaningful, we replace the centroid with the vector that is closest to the centroid represent each posting list. Then the wasted navigating computation is transformed to the distance computation for a subset of real candidates.
What's 's more, in order to quickly find a small number of nearest posting lists for a query, we create memory SPTAG [12 (MIT license) index for all the vectors that represent the centorids of the posting lists. SPTAG constructs space partition trees and a relative neighborhood graph as the vector index which can speedup the nearest centroids search to sub-millisecond response time.
3.2.2 Posting list expansion
To deal with boundary issue, we need to increase the visibility for those vectors that are located in the boundary of the posting lists. One simple way to assign each vector to multiple close clusters. However, it will increase the posting size significantly leading to the heavy disk reads. Therefore, we

---

Figure 3: Hierarchical balanced
Figure 4: Closure clustering
Figure 5: Representative replica-
clustering: iteratively balanced
signment: assign boundary vec-
tion: use RNG rule to reduce the similarity of two close posting lists. The orange point will be assigned to blue and grey post- ing lists although it is closer to yellow list than grey list.
partition the vectors in a large
tors (green points) to multiple closest clusters its distances
cluster (yellow cluster) into a small number of small clusters
to these clusters nearly the
(green clusters) until each clus- ter only contains limit number of vectors (blue clusters).
same (blue and yellow clusters).
introduce a closure multi-cluster assignment solution for boundary vectors on the final clustering step assign vector to multiple closest clusters instead of only the closest one if the distance between the vector and these clusters are nearly the same (Figure 4 gives an example):
Xi - Dist(x, Cit) S (1+ e1) x Dist ca).
(2)
Dist(x, ca) & Dist(x, C;2) S S Dist(x, c.k)
This means we only duplicate the boundary vectors. For those vectors which are very close to the centroid of cluster, they still keep one copy. By doing we effectively limit the capacity increase due to closure cluster assignment while increasing the recall probability of these boundary vectors: they will be recalled if any of their closest posting lists is searched.
Since each posting list is small and we use closure assignment which will result some posting lists that are very close to each other contain the same duplicated vectors (For example, the green vectors belong to both yellow and blue clusters). Too many duplicated vectors in the close posting lists will also waste the high-cost disk reads. Therefore, we further optimize the closure clustering assignment by using RNG rule [41] to choose multiple representative clusters for the assignment of an boundary vector in order to reduce the similarity of two close posting lists (Figure 5). RNG rule can be simply defined as we will skip the cluster ij for vector x if Dist(C,j, x) > Dist(C.j-1, Cty). The insight is two close posting lists are more likely to be both recalled by the navigating index. Instead of storing similar vectors in close posting lists, it would be better to store different vectors to increase the number of seen vectors in the online search. From the vector side, it is better to be represented by posting lists located in different directions (blue and grey posting lists in the example) than just being represented by posting lists located in the same direction (blue and yellow posting lists).
3.2.3 Query-aware dynamic pruning
In the index-seards stage, to process different queries effectively with different resource budget, we introduce the query-aware dynamic pruning technique to reduce the number of posting lists to be searched according to the distance between query and centroids. Instead of searching closest K posting lists for all queries, dynamically decide posting list to be searched only if the distance between its centroid and query is almost the same as the distance between query and the closest centroid:
search
Xij
Dist(q, cqy) S (1 E2) Dist(q, ca)), Dist c.) & Dist 222 S ... S Disti(q. c.k)
+
By further reducing those unnecessary posting lists in the closest K posting lists, we can significantly reduce the query lateney while still preserving the high recall by leveraging the resource more reasonably and effectively.
4 Experiment
In this section we first present the experimental comparison of SPANN with the current state-of-the-ar ANNS algorithms. Then we conduct the ablation studies to further analyze the contribution of each
5

---

technique. Finally, we setup an experiment to demonstrate the scalability of SPANN solution in the distributed search scenario.
4.1 Experiment setup
We conduct all the experiments on 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-O. The datasets we use are as follows:
SIFTIM dataset 3 the most commonly used dataset generated from images for evaluating the performance of memory-basee based ANNS algorithms, which contains one million of 128- dimensional float SIFT descriptors as the base set and 10,000 query descriptors as the test set.
2. SIFTIB dataset [3 is classical dataset for evaluating the performance of ANNS algorithms that support large scale vector search, which contains one billion of 128ddimensional byte vectors as the base set and 10,000 query vectors as the test set.
3. DEEPIB dataset S is dataset learned from deep image classification model which contains one billion of 96-dimensional float vectors as the base set and 10,000 query vectors as the test set.
4. SPACEVIB dataset (O-UAA license) is a dataset from commercial search engine which derives from production data. It represents another different content encoding deep natural language encoding. It contains one billion of 100-dimensional byte vectors as a base set and 29,316 query vectors the test set.
The comparison metrics to demonstrate the performance are:
1. Recall: We compare the R vector ids returned by ANNS with the ground truth vector ids to calculate the recall R. Since there exist multiple data vectors sharing the same distance with the query vector, we also replace some of the ground truth vector ids with the vector ids that sharing the same distance to the query vector in the recall calculation.
2. Latency: We use the query response time in milliseconds as the query latency.
3. VQ (Vector-Query): The product of the number of vectors and the number of queries per second machine serving capacity of the search engine which takes both query latency and memory cost into consideration. The higher VQ the system has, the less resource cost it consumes. Here use the number of vectors per KB x the number of queries per second as the VQ capacity.
serve (which is introduced in GRIP [50)). It demonstrates the
4.2 SPANN on single machine
In this section, demonstrate that inverted index based SPANN solution also achieve the state- of-the-art performance in terms of recall, latency and memory cost. We first compare SPANN with the state-of-the-arr billion-scale disk-based ANNS algorithms on three billion-scale datasets. Then we conduct an experiment on SIFTIM M dataset to compare the VQ capacity with the start-of-the-art all-in-memory ANNS algorithms. For all the experiments in this section,
the following hyper- parameters for SPANN: 1) use at most 8 closure replicas for each vector in the closure clustering assignment: 2) limit the max posting list size 12KB for byte vectors and 48KB for float vectors: 3) set E for posting list expansion to 10.0, and set E2 for query-awan dynamic pruning with recall @ and recall@ 10 0.6 and 7.0, respectively. We increase the maximum number of posting lists be searched in order to get the different recall quality.
4.2.1 Comparison with state-of-the-art billion-scale disk-based ANNS algorithms
We choose the state-of-the oft disk-based ANNS algorithms that can support billion-scale datasets as our comparison targets. we do not compare with HM-ANN (36] since it is not open sourced and the required PMM hardware may not be available some platforms. Therefore, we compare SPANN only with the state-of-the-art billion-scale disk-based ANNS algorithm DiskANN. We use the default hyper parameters for DiskANN (same as the paper for SIFTIB and SPACEV1R and the pre-build index provided by 2 for DEEPIB).

---

2000
SRIER
57.5
04
92-
60.0
03
87.5
85.6
Talency mma
stuncy Snol
Idancy (ms)
1.0
200
-78-1h
-Swen
92-
67.5
65.0
62.5
72
50.5
92
875
85.0
(stency (m8)
starcy 7na)
Litency (mo)
(a)
(b)
(c)
Figure 6: SPANN vs. DiskANN on (a) SIFTIB, (b) SPACEVIB, and (c) DEEPIB.
We carefully adjust the navigating memory index size of SPANN by choosing suitable number of posting lists (about 10-12% of total vector number) to ensure both the algorithms consume the same amount of memory (about 32GB for SIFTIB and SPACEVIB datasets and 60GB for DEEPIB dataset). Figure ( demonstaats the performance for SIFTIB dataset. From the results, we find SPANN significantly outperforms DiskANN in both recall @ and recall @ 10 especially in the low query latency budget (less than 4ms). Especially, SPANN is more than two times faster than DisKANN to reach the 95% recall@1 1 and recall 10.
The performance results for SPACEVIB and DEEPIB datasets are shown in Figure 6(b) and [(c) also demonstrates that SPANN outperforms DiskANN in both recall 1 and recall @ 10 when query latency budget small (less than 4ms). Especially, DisKANN cannot achieve good recall quality (90%) in less than 4ms in SPACEVIB 1B dataset, while SPANN can obtain a recall of 90% in just around Ims. For DEEPIB dataset, SPANN can also be more than two times faster than DiskANN to reach the good recall quality (90%).
4.2.2 Comparison with state-of-the-art all-in-meoory ANNS algorithms
Then conduct experiment SIFTIM dataset to compare the VQ capacity with the start-of- the-art all-inymemory ANNS algorithms, NSG [19], HNSW (32), SCANN 22],, NGT-ONNG (23). NGT-PANNG [22 and N2 4. These algorithms have presented state-of-the-ad performance in the onn-benchmarks []. We choose VQ capacity instead of latency as the comparison metric since these algorithms use much more memory to trade for low latency. However, memory is an expensive resource which has become the bottleneck for those algorithms to support large scale datasets. Therefore, should take both memory and latency into consideration in the performance comparison. We take the SIFTIM M dataset as an example due to the memory bottleneck of our test machine. We believe that the observation
be generalized billion scale datasets.
Most of these algorithms are graph based algorithms. For NSG, we get the pre-built index from [5] and run the performance test with varying SEARCH L from to 256 which controls the quality of the search results. For HNSW (nmslib), SCANN, NGT-ONNG, NGT-PANNG and N2 we use the hyper parameters they provided in the ann-benchmarks || that achieve the best performance for the SIFTIM dataset.
Figure 7 and 8 demonstrate the VQ capacity and query latency of all the algorithms on recall I and recall@ (0. We can see from the result that SPANN achieves the best VQ capacity consistently across almost all the recall levels. This means although SPANN cannot achieve as low latency as the all-in-memory ANNS algorithms due to the high-cost disk accesses during the search, can obtain the best serving capacity in the large scale vector search scenario.
7

---

ROME
2.50
NET OWEE
2.2
SCAM
2000
1000
239
Figure 7: VQ of different ANNS indices
Figure 8: Latency of different ANNS indices
$7.3
Eo de
L00 (100
20% cerssis
05.
Fm))
Figure 9: Different numbers of centroids
Figure 10: Different types of centroid selection
4.2.3 Ablation studies
In this section, we conduct set of experiments to do the ablation studies on each of our techniques in the SIFTIM dataset.
Hierarchical balanced clustering There are three fast ways to partition the vectors on a single machine into a large number of posting lists: 1) randomly choose set of points as the posting list centroids; 2) using hierarchical KMeans clustering (HC) to select centroids; 3) using hierarchical balanced clustering (HBC) to generate 16% points as the centroids using these three ways.
of centroids. We compare the index quality by generating
Figure TO shows the recall and latency performance of these three centroid selection algorithms. For both recall@ @ and recall 10, we can see HBC centroid selection is better than random and HC selections, which demonstrates that balance posting length is very important for inverted index based methods. Moreover, HBC is very fast which clusters one million points into 160K clusters in only around 50 seconds with 64 threads. The whole SPANN index be built in around 2 minutes.
Moreover, how many centroids are needed? Small number of centroids can reduce the navigating memory index size. However, large number of centroids usually means better performance. Therefore, we need make reasonable trade-off between the memory usage and the performance. Figure compares the performance of different numbers of centroids. From the result, we can see that the performance will increase significantly with the growth the centroid number when the centroid number is small. However, when the number of centroids becomes large enough (16%), the per- formance will not increase any more. Therefore, we can choose 16% points as the centroids to achieve both good search performance and small memory usage.
Closure clustering assignment To use closure clustering assignment, we need to assign vector to multiple closed clusters to increase its recall probability during the search. Then at most how many closure replicas we need to duplicate for a vector to ensure the performance? Too small replicas cannot help to retrieve those boundary vectors back. However, too many replicas will increase the posting size greatly which will also affect the performance. Figure T demonstraasss the performance of different numbers of replicas for closure clustering assignment. From the result, we can see that using more than one replicas improves the performance significantly. However, when the number of replicas is larger than 8, the performance cannot be improved any more. Therefore, choose 8 replicas for all of our experiments.
aware dynamic pruning In order to process different queries effectively during the online search, we introduce the query-aware dynamic pruning technique further reduce the number of posting lists to be searched by pruning those unnecessary posting lists in the closest K posting lists. We compare the performance with and without query-aware dynamic pruning in the Figure 12 From the result, we can see that with query-aware dynamic pruning, we can further reduce the query latency without recall drop especially when the latency budget is small. Note that, this technique can reduce not only the query latency but also the resource usage for query.
8

---

100
100 1920
Mey
Figure 11: Different numbers of closure replicas
Figure 12: W/O query-aware dynamic pruning
BHAM
curniny
Figure 13: Data size and query access distribu- tion across different machines
Figure 14: Comparison of recall, latency and
#machines dispatched in the end-to-end test
4.3 Extension of SPANN to distributed search scenario
Compared to the graph base approaches, the additional advantage for inverted index based SPANN approach is that the partial search on the nearest posting lists idea can be easily extended to the distributed search scenario, which can handle super large scale vector search with high efficiency and low serving cost. The approach Pyramid [15] demonstrates the power of balanced partition and partial search approach
distributed scenario. To demonstrate the scalability of SPANN distributed search scenario, we partition the data vectors X evenly into M partitions
(X,. X2. XM) by using the multi-constraint balanced clustering and closure clustering assignment techniques in the distributed index build stage, where M is the number of machines. In the online search stage, also adopt the query-awart dynamic pruning technique to reduce the number of dispatched machines, which effectively limits the total epu and IO cost for query.
The only challenge for us is that there may have some hot-spot machines. Therefore, we need to balance not only the data size but also the query access in each machine to avoid the hot spots. To address the hot-spot challenge, we partition the vectors into multiple small partitions (larger than machine number) and then use best-fit bin-packing algorithm [17 to pack the small partitions into large bins (the number of bins equals to number of machines) according to the history query access distribution. By doing so, can effectively balance not only the data size but also the queries processed on each machine.
We compare the optimized SPANN solution with traditional random partition and all dispatch solution demonstrate the effectiveness of workload reduction and scalability of SPANN in distributed search scenario. We conduct the experiments below based on the SPACEV 1B dataset and use about 100,000 query accesses history from production as the test workload. 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 the online search evaluation.
4.3.1 Workload reduction and scalability
Figure 13 shows the number of vectors and the number of test query accesses in each machine when partitioning all the base vectors into 8, 16, and 32 partitions. From the result, we can see that SPANN distributes all the data and query accesses evenly into different machines. Although it increases the number of vectors in each machine by 20% due to closure assignment, significantly reduces the query accesses in each machine compared to the random partition solution. Moreover, SPANN can continually reduce the query accesses in each machine by using more machines while random partition cannot. This means we can always add more machines to support more queries per second, which demonstrates good scalability of our system. The reason why we can achieve good scalability is that we effectively bound the number of machines to do the search for each query.

---

4.3.2 Analysis
Then we analyze how each technique affects the performance. We use 32 partitions case to do the ablation study. We build SPANN single machine index for each partition and use the 29,316 query vectors with ground truth as the test workload. Figure 14 demonstrates the recall, latency and the average number of machines to dispatch in the end-to-end distributed search scenario. The left figure shows that SPANN can achieve almost the best recall in each latency budget. In the right figure, we can see that random partition solution needs to dispatch the query to all 32 machines for search. Using multi-constraints balanced clustering technique of dispatched machines to 9. By adding closure assignment, we can further reduce the number of dispatched machines to 8. When all the techniques applied (including query-aware dynamic pruning in the online search), we can finally reduce the number of dispatched machines to 6.3. This means we can save about 80.3% of computation and IO cost for a query. Meanwhile, by reducing the number of machines to search for a query, we can further reduce the query latency since we reduce the number of candidates for final aggregation.
significantly reduce the number
Conclusion
In this paper, we introduce SPANN, a simple but surprising efficient inverted index based ANNS system, which achieves state-of-the-art performance for large scale datasets in terms of recall, latency and memory cost. Different from previous inverted index based methods that use lossy data compression address the memory bottleneck, SPANN adopts simple memory-de -ink hybrid solution which only stores the centroids of the posting lists in the memory. We guarantee both low latency and high recall by greatly reducing the number of disk accesses and improving the quality of posting lists. Experiment results show SPANN can not only establish the new state-of-the-art performance for billion scale datasets but also achieve good scalability when extended to distributed search scenario. This demonstrates the ability of hierarchical SPANN to support super large scale vector search with high efficiency and low serving cost.
6
Acknowledgements
We would like to thank Ben Karsin and Murat Guney from Nvidia to help us further speedup the SPANN index build with GPU, which runs more than five times faster than CPU version.
References
[1] [n.d.]. Benchmarking nearest neighbors. http:://ann-bencheee com/
[2] [n.d.]. Billion-scale ANNS Benchmarks. http:///bggamm-beencmaaakss
[3] [n.d.]. Datasets for approximate nearest neighbor search. |attp://corpus- irisa
fr/
[4] [n.d.]. Lightweight approximate Nearest Neighbor algorithm (N2). https://github..co com/ kakao/n2
[5] [n.d.]. NSG Navigating Spread-out Graph For Approximate Nearest Neighbor Search, https //github www www.//2JL.earrnnnnnnee
[6] [n.d.]. SPACEVIB: A billion-Scale vector dataset for text descriptors. https://github. com/
mi /icrrott//PPP//reeee/a/rraaaatst
[7] Artem Babenko and Victor Lempitsky. 2014. The inverted multi-index. IEEE transactions on pattem analysis and machine intelligence 37, 6 (2014), 1247-1260.
[8] Artem Babenko and Victor Lempitsky. 2016. Efficient indexing of billion-scale datasets of deep descriptors. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2055-2063.
10

---

[9] Dmitry Baranchuk, Artem Babenko, and Yury Malkov. 2018. Revisiting the inverted indices for billion-scale approximate nearest neighbors. In Proceedings of the European Conference on Computer Vision (ECCV). 202-216.
[10] Jeffrey S Beis and David G Lowe. 1997. Shape indexing using approximate nearest-neighbour search in high-dimensional spaces. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 1000-1006.
[11] Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9 (1975), 509-517.
[12] Qi Chen, Haidong Wang, Mingqin Li, Gang Ren, Scarlett Li, Jeffery Zhu, Jason Li, Chuanjie Liu, Lintao Zhang, and Jingdong Wang. 2018 SPTAG: A library for fast approximate nearest neighbor search. httpss: htttps///gitubb wtccchuw..oommmoo com/Microsooft/SPTA
[13] Sanjoy Dasgupta and Yoav Freund. 2008 Random projection trees and low dimensional manifolds. Proceedings of the 40th Annual ACM Symposium Theory of Computing (2008), 537-546.
[14] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. 2004. Locality-sensitive Hashing Scheme Based on P-stable Distributions. Proceedings of the Twentieth Annual Symposium Computational Geometry (SCG). 252-262.
[15] Shiyuan Deng, Xiao Yan, KW Ng Kelvin, Chenyu Jiang, and James Cheng. 2019. Pyramid: A General Framework for Distributed Similarity Search on Large-scale Datasets. In Proceedings of the IEEE International Conference on Big Data (Big Data). IEEE, 1066-1071.
[16] Wei Dong, Moses Charikar, and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures. In Proceedings of the 20th International Conference on World Wide Web (WWW). 577-586.
[17] György Dósa and Jiff Sgall. 2014. Optimal analysis of Best Fit bin packing. In International Colloquium on Automata, Languages, and Programming. 429-441.
[18] Jerome H. Freidman, Jon Louis Bentley, and Raphael Ari Finkel. 1977. An Algorithm for Finding Best Matches in Logarithmic Expected Time. ACM Trans. Math. Software 3, 3 (1977), 209-226.
[19] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graphs. PVLDB 12, 5.5 (2019), 461 4774
[20] Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simeha, Felix Chern, and Sanjiv Kumar. 2020. Accelerating Large-Scale Inference with Anisotropic Vector Quantization. In Proceedings of the 37th International Conference on Machine Learning (ICML). 3887-3896.
[21] Kiana Hajebi, Yasin Abbasi- Yadkori, Hossein Shahbazi, and Hong Zhang. 2011. 1. Fast Approx- imate dearest-Neighbor Search with k-Nearest Neighbor Graph. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI). 1312-1317.
[22] Masajiro Iwasaki. 2016. Pruned bi-directed k-nearest neighbor graph for proximity search. In International Conference on Similarity Search and Applications. Springer, 20-33.
[23] Masajiro Iwasaki and Daisuke Miyazaki. 2018. Optimization of indexing based on k-nearest neighbor graph for proximity search in high-dimensional data. arXiv preprint arXiv: 1eXiv:18/00000 181007335 (2018).
[24] P. Jain, B. Kulis, and K. Grauman. 2008. Fast image search for learned metrics. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition (CVPR). 1-8.
[25] Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence 33, (2010), 117-128.
11

---

[26] Hervé Jégou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg. 2011. Searching in one billion vectors: re-rank with souree coding. In Proceedings of the IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP). 861-864.
[27] Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data (2019).
[28] Yannis Kalantidis and Yannis Avrithis. 2014. Locally optimized product quantization for approximate nearest neighbor search. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2321-2328
[29] Brian Kulis and Trevor Darrell. 2009. Learning to Hash with Binary Reconstructive Embeddings. In Advances in Neural Information Processing Systems, Vol. 22. 1042-1050.
[30] Hongfu Liu, Ziming Huang, Qi Chen, Minggin Li, Yun Fu, and Lintao Zhang. 2018. Fast Clus- tering with Flexible Balance Constraints. In Proceedings of the IEEE International Conference on Big Data (Big Data). IEEE, 743-750
[31] Ting Liu, Andrew Moore, Alexander Gray, and Ke Yang. 2004. investigation of practical approximate nearest neighbor algorithms. Advances in Neural Information Processing Systems, 825-832.
[32] Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence 42, 4 (2018), 824 836..
[33] Marius Muja and David G. Lowe. 2014. Scalable Nearest Neighbour Algorithms for High Dimensional Data. IEEE Transactions on Pattern Analysis and Machine Intelligence 36, 11 (2014), 2240.
[34] David Nister and Henrik Stewenius. 2006. Scalable recognition with vocabulary tree. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Vol. 2. 2161-2168.
[35] Liudmila Prokhorenkova and Aleksandr Shekhovtsov. 2020. Graph-based nearest neighbor search: From practice to theory. In Proceedings of the International Conference on Machine Learning (ICML). 7803-7813
[36] Jie Ren, Minjia Zhang, and Dong Li. 2020. HM-ANN: Efficient Billion-Point Nearest Neighbor Search on Heterogencous Memory. In In Proceedings of the 34th International Conference on Neural Information Processing Systems, Vol. 33.
[37] Anshumali Shrivastava and Ping Li. 2014. Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS). In Proceedings of the 27th International Conference on Neural Information Processing Systems, Vol. 2. 2321-2329.
[38] Robert F. Sproull. 1991. Refinements to nearest-neighbor searching in k-dimensional trees. Algorithmica 6, 1-6 (1991), 579-589.
[39] Suhas Jayaram Subramanya, Rohan Kadekodi, Ravishankar Krishaswamy, and Harsha Vardhan Simhadri. 2019. Diskann: Fast accurate billion-point nearest neighbor search a single node. In Proceedings of the 33rd International Conference on Neural Information Processing Systems. 13766-13776.
[40] Eric Sadit Tellez, Guillermo Ruiz, and Edgar Chavez. 2016. Singleton indexes for nearest neighbor search. Information Systems 60 (2016), 50-68.
[41] Godfried T Toussaint. 1980. The relative neighbourhood graph of a finite planar Pattern recognition 12, (1980), 261-268.
[42] Jingdong Wang and Shipeng L.. 2012. Query-driven iterated neighborhood graph search for large scale indexing. In Proceedings of the 20th ACM international conference on Multimedia. ACM, 179-188.
12

---

[43] Jing Wang, Jingdong Wang, Gang Zeng. Zhuowen Tu, Rui Gan, and Shipeng Li. 2012. Scalable k-nn graph construction for visual descriptors. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 1106-1113.
[44] Jingdong Wang, Naiyan Wang, You Jia, Jian Li, Gang Zeng, Hongbin Zha, and Xian Sheng Hua. 2014. Trinary-projection trees for approximate nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence 36, (2014), 388-403.
[45] Jingdong Wang and Ting Zhang. 2019. Composite Quantization. IEEE Transactions Pattern Analysis and Machine Intelligence 41, 6 (2019), 1308-1322.
[46] Jingdong Wang, Ting Zhang, Jingkuan Song, Nicu Sebe, and Heng Tao Shen. 2018. A Survey on Learning Hash. IEEE Transactions on Pattern Analysis and Machine Intelligence 40, (2018), 769-790.
[47] Yair Weiss, Antonio Torralba, and Rob Fergus. 2009. Spectral hashing. In Advances in neural information processing systems. 1753-1760.
[48] Hao Xu, Jingdong Wang, Zhu Li, Gang Zeng, Shipeng Li, and Nenghai Yu. 2011. Complemen- tary hashing for approximate nearest neighbor search. In Proceedings the IEEE International Conference on Computer Vision (ICCV). 1631-1638.
[49] Peter N Yianilo.. 1993. Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces. Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium Discrete Algorithms (1993), 311 311-321.
[50] Minjia Zhang and Yuxiong He. 2019. Grip: Multi-store capacity-optimized high-performance nearest neighbor search for vector search engine. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management. 1673-1682.
[51] Ting Zhang, Chao Du, and Jingdong Wang. 2014. Composite Quantization for Approximate Nearest Neighbor Search. In Proceedings of the 31th International Conference on Machine Learning (ICML), Vol. 32. 838-846.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
13

---

(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [Yes]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "t0Tvjj-UYRe", "reviewer": "Reviewer_tJVR", "summary": "In this paper, the authors study the approximate nearest neighbor search (ANNS) problem and develop an inverted index based algorithm using both memory and disk in the searching to reduce the required amount of memory. The proposed algorithm first partitions the vectors into clusters and then stores in the memory the centroid of each cluster and the disk address of the vectors belonging to the cluster, or called posting lists. To limit the length of posting lists (the number of vectors in a cluster), the algorithm performs the clustering with an additional constraint of balancing the length of each posting list, as suggested in [27]. But the algorithm performs the clustering in a hierarchical way so that the computational cost can be improved. It further replaces a centroid by the closest vector and another index [10] to speed up the search. It also assigns boundary vectors, those close to multiple clusters, to the multi-clusters to reduce the number of posting lists accessed. An RNG rule [37] that assigns a vector to clusters at different directions is employed to avoid generation of similar clusters. Finally, during the query, only posting lists that are sufficiently close to the query compared to the closest posting list will be searched. Experimental evaluations have been conducted on two datasets of one billion to demonstrate the superior performance.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem of large-scale ANNS using small memory consumption is of significance in the machine learning community. The authors achieve to show that the inverted index approach can be helpful in designing a low-memory ANNS algorithm. They carefully employ/use multiple ideas to adapt the inverted index method to the memory-disk hybrid setting and save the memory cost. Each of the ideas is clearly explained with an illustrating figure, making the paper easy to follow. Experimental results validate to some degree that the developed algorithm is memory-efficient while keeping high recall and small latency. The algorithm can be easily extended to the distributed setting to further improve the scalability.\n\nThe ideas are simple and straightforward/standard. The authors make use of multiple existing ideas and the biggest contribution to me is to show that inverted index can be adapted in the low-memory/hybrid setting. This is not too surprising because usually only a few posting lists are accessed when processing a query, well suited to the low-memory setting. The theoretical understanding of the inverted index based algorithm is still lack, unlike graph-based algorithms [a]. Although I believe this paper will be eventually published, the authors will need to test the algorithm in more and diverse large-scale datasets (instead of only two datasets). This is because different datasets have different characteristics and an algorithm can have quite different performance in different datasets. Including more datasets enables us to better understand the behavior of the algorithm in datasets from different domains in practice. The writing of the experimental parts needs to be enhanced. See detailed comments.\n\nReference:\n\n[a] Liudmila Prokhorenkova and Aleksandr Shekhovtsov. Graph-based Nearest Neighbor Search: From Practice to Theory. ICML2020.\n\nSuggestions:\n1.\tIn the ablation study for the pruning idea (Fig. 12), tuning the eps parameter, which controls the allowed distance between the query and a centroid, can give more information than only with or without pruning.\n2.\tThere appears to be some space left, e.g., Fig. 14 can be compressed into half-spacing. Discussing the different types of ANNS algorithms including graph-based algorithms, inverted index algorithms and LSH algorithms can provide readers better context.\n3.\tThe term “posting list” appears in Line 48 for the first time but are implicitly defined in Section 3. The definition should be moved earlier.\n4.\tFor comparisons with all-in-memory algorithms, it’s best to provide the latency in addition to the VQ capacity. Although the authors acknowledge that SPANN has higher latency, it is not unknown how much higher.  The loss in latency can be important for choosing an indexing algorithm in practice.\n\nDetailed comments:\n-\tTypos: Line 121: “hybrid solution that solve”\n-\tLine 269: “random choose”\n-\tLine 276: “how many centroids we need to generate?”\n-\tFigure 10 and 11: “Different number of …”\n-\tLine 319: The logic of the sentence below is weird and it does not make sense to me. “In order to make the result reproducible, we conduct the experiments below based on the SPACEV1B dataset.”\n-\tLine 339: “Only use …, we can …”\n\nUPDATES AFTER REBUTTAL:\n\nThanks! In the rebuttal, the authors have addressed my concerns adequately. The authors will need to make it clear that the proposal algorithm works best for the large-data only, because as shown in the tables in the rebuttal, the latency is about 3 ~ 6 times slower than that of other state-of-the-art in-memory algorithms for the same recall. I would like to see more datasets from different domains tested and the authors promised to include them in the final version. I have updated my score from 5 to 6.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "24"}, "extra_text": {}}, {"review_id": "pEL_jMLv4xO", "reviewer": "Reviewer_hs5r", "summary": "The paper claims the following contributions. (1) It proposes a new disk-based algorithm (called SPANN) for billion-scale approximate nearest neighbor search on a single machine. (2) SPANN adopts two techniques. One is hierarchical balanced clustering for index building and the other is query-aware schema for search. (3) SPANN is two times faster than a state-of-the-art solution (called DiskANN). ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper studied a practical problem that aims at improving billion-scale Approximate Nearest Neighbor Search (ANNS). The adopted hierarchical balanced clustering technique is insightful. By copying the same vector into multiple posting lists, the proposed SPANN algorithm achieves faster query processing (see Figure 4 and 5 and Ablation Study). Experiments demonstrate that SPANN is about 2 times faster than the state-of-the-art DiskANN in query processing.\n\nDespite the above strengths, the paper needs to fix a few issues to justify the claimed contributions adequately. Please see the following: \n\n(1)\tThe paper claims that SPANN is faster than the state-of-the-art DiskANN. The claim is valid in terms of query processing time and according to Figure 6, query processing time of SPANN is about half of DiskANN when the recall is the same. However, the claim does not adequately support that SPANN is better than DiskANN because SPANN may use larger index size than DiskANN. It is trivial to improve DiskANN query processing time by using multiple indexes, which is a common practice for ANNS algorithms such as Locality Sensitive Hashing and Vector Quantization. The paper did not present index size in the results so it is still early to conclude that SPANN is better than DiskANN. \n\n(2)\tThe paper claims a 2x faster performance improvement. The improvement seems marginal and there could be little statistical significance. It will be good if the paper can achieve a more significant improvement (e.g. 5x) on some datasets or include statistical significance tests on all datasets.  \n\n(3)\tThe paper did not claim technical contributions in the paper. Instead, the paper said it adopted or used existing techniques, i.e. hierarchical balanced clustering and query-aware schema. If the contribution is combining different techniques, the paper may add more techniques (e.g. 3 techniques). If the contribution is developing new techniques, the paper may justify how the proposed techniques differ from related papers (i.e. DiskANN, HNSW, and NSG).\n\n[comments after author response]\nI have increased my rating from 5 to 6. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper studies the approximate nearest neighbor search problem which has been studied for decades. It seemed the paper does not introduce negative societal impact.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "oGBVdx3408d", "reviewer": "Reviewer_2vRb", "summary": "This paper proposes SPANN, which uses the inverted index to conduct large-scale nearest neighbor search on SSD. The centroids are kept in memory and indexed by a neighborhood graph for fast access. The lists of vectors associated with the centroids are stored on disk. Optimizations include (1) hierarchical balanced clustering to balance and limit the sizes of the lists; (2) assigning vectors on cluster boundaries to multiple clusters; (3) adjusting the number of lists to check according to each query. Experiment results show that SPANN significantly outperforms DiskANN, a state-of-the-art SSD-based solution, and is effective for distributed search.\n\n\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I like that the optimizations are reasonable, and the performance of SPANN is good. I think the experiment design and presentation clarity can be significantly improved.\n\n1. In Eq. (2) and Eq. (3), do the two \\epsilon take the same value? How do you set or tune them? Assigning a vector to at most 8 clusters and checking at most L lists for a query are only worst-case controls and do not tell exactly how \\epsilon is configured.\n \n2. In Section 4.2.2, when comparing with state-of-the-art ANN algorithms, SPANN stores only the centroids or all data in memory? For this experiment, it is OK to report the VQ capacity but recall-time curve must be reported as it is most widely recognized performance metric for similarity search.\n\n3. Please report the index construction cost of SPANN on SIFT1B and SPAVEC1B. I am curious to which degree replicating vectors across clusters blow up the index size.\n\n4. Comparing with randomly sampled clusters in Figure 9 and random partition in Figure 13 and 14 are not reasonable as the random baselines apparently will not work well. To show the benefits of hierarchical balanced clustering, you may compare with hierarchical k-means without cluster size control.  \n\n5. For distributed similarity search, [1] has shown that clustering-based data partitioning can reduce the number of accessed machines for each query and should be discussed. For distributed similarity search, please report a recall-time performance comparison with the baselines to show the end-to-end performance benefits of SPANN.\n\n6. According to Figure 11 and Figure 12, it seems that the main performance gain of SPANN comes from multiple cluster assignment while the benefit of dynamic pruning is marginal.\n\n7. Both HNSW[29] and N2[30] refers to HNSW (an archive version and a journal version), and they are treated as two different algorithms in the experiments. What are the differences between them?\n\n8. Presentation can be significantly improved. “nearest neighborhood search” should be “nearest neighbor search”. “In order to make the result reproducible, we conduct the experiments below based on the SPACEV1B dataset.” Why experiments on SIFT1B will not be reproducible?\n\n[1] Pyramid: A General Framework for Distributed Similarity Search on Large-scale Datasets", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "23IC2P55eSi", "reviewer": "Reviewer_nUdz", "summary": "SPANN is a hybrid disk/RAM vector indexing method. \n\nSPANN uses a hierarchical clustering (with some tricks) to split the dataset into buckets that are stored uncompressed on disk. At search time, the buckets corresponding to the nearest centroids to the query (again with some tricks) are visited to retrieve the nearest neighbors. \n\nThe indexing-time tricks are intended to balance the bucket sizes and reduce assignment ambiguity with some level of multiple storage. \n\nAt search time, the number of buckets to visit is tuned based on the distance of the query to the centroids. \n\nThere is also a section about a distributed version of the method. ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths \n\nS1 The paper is very practical and has lots of interesting insights. \n\nS2 results clearly outperform the state of the art. \n\nS3 an attempt to normalize vector serving cost between disk-based and memory-only methods. \n\nWeaknesses \n\nW1 very engineering-oriented, no methodological insights \n\nW2 The fairness of the VQ comparison is discussible\n\nS2 There are not so many hybrid RAM/disk indexing methods. DiskANN is one of them and is a good comparison point. It may be worthwhile to compare the index building times, which tends to be slow for DiskANN\n\nS3/W2. The VQ comparison measure between disk-based and memory-only methods is very interesting. However, the paper misses a self-contained description on how it works exactly. The SIFT1M dataset is so small that it easily fits in the 128G RAM of the test machine, including with graph structure overheads. So it seems that the disk capacity and RAM are wasted, meaning that a smaller machine could be used. \n\nW1 Especially the section about the distributed setting is largely orthogonal to the method, it could be applied similarly to other inverted-list based techniques. Including it makes that the paper looks more like a \"systems\" paper than a NeurIPS research paper.\n\nThere are a few questions that are left after reading the paper: \n\n1. since the number of inverted lists to visit depends on the query, how much variation is there in the query time? \n\n2. the authors mention that each vector is duplicated at most 8 times, but what is total number of duplicated vectors that need to be stored?\n\n3. since the search from different inverted lists can yield several times the same vector, some over-retrieval and deduplication needs to be applied. It may be useful to discuss that.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"ethical_concerns": "-", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents an empirically efficient algorithm for disk-scale similarity search. The algorithm offers significant (2x or higher) improvements over the state of the art. The reviewers’ opinion was that the techniques used in the algorithm were relatively standard, but they were carefully engineered and put together to obtain a practical software artifact. One concern was that the experiments have been performed on only two data sets, but the authors promised further experiments in the final version of the paper. 
Decision: Accept (Spotlight)