Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

The 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.

Reference:

[a] Liudmila Prokhorenkova and Aleksandr Shekhovtsov. Graph-based Nearest Neighbor Search: From Practice to Theory. ICML2020.

Suggestions:
1.	In 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.
2.	There 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.
3.	The term “posting list” appears in Line 48 for the first time but are implicitly defined in Section 3. The definition should be moved earlier.
4.	For 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.

Detailed comments:
-	Typos: Line 121: “hybrid solution that solve”
-	Line 269: “random choose”
-	Line 276: “how many centroids we need to generate?”
-	Figure 10 and 11: “Different number of …”
-	Line 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.”
-	Line 339: “Only use …, we can …”

UPDATES AFTER REBUTTAL:

Thanks! 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.
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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). 
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.

Despite the above strengths, the paper needs to fix a few issues to justify the claimed contributions adequately. Please see the following: 

(1)	The 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. 

(2)	The 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.  

(3)	The 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).

[comments after author response]
I have increased my rating from 5 to 6. 

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_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: SPANN is a hybrid disk/RAM vector indexing method. 

SPANN 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. 

The indexing-time tricks are intended to balance the bucket sizes and reduce assignment ambiguity with some level of multiple storage. 

At search time, the number of buckets to visit is tuned based on the distance of the query to the centroids. 

There is also a section about a distributed version of the method. 
main_review: Strengths 

S1 The paper is very practical and has lots of interesting insights. 

S2 results clearly outperform the state of the art. 

S3 an attempt to normalize vector serving cost between disk-based and memory-only methods. 

Weaknesses 

W1 very engineering-oriented, no methodological insights 

W2 The fairness of the VQ comparison is discussible

S2 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

S3/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. 

W1 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.

There are a few questions that are left after reading the paper: 

1. since the number of inverted lists to visit depends on the query, how much variation is there in the query time? 

2. 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?

3. 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.



limitations_and_societal_impact: -
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.



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.

1. 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.
 
2. 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.

3. 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.

4. 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.  

5. 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.

6. 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.

7. 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?

8. 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?

[1] Pyramid: A General Framework for Distributed Similarity Search on Large-scale Datasets
limitations_and_societal_impact: Yes
review_title: null

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)