Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: In this paper, the authors presented an algorithm coined Flinters to Identify Near-Neighbor Groups (FLINNG) to solve the approximate near neighbor search problem. Given a dataset $D$, FLINNG is capable of constructing an {\it index} which, when given a {\it query} $y$, outputs a set of points $x_i \in D$ with high similarity to $y$.

The near neighbor search is a problem with extensive research and a wide range of applications, including recommendation systems, social networks, computer vision, and genome sequencing. While the problem is particularly well-understood in low dimensions, with efficient algorithms to identify exact k-neighbors, but large-scale applications on big datas with high dimentionality often challenges existing algorithms and data structures.

The authors address this need by showing that FLINNG is an index with efficient construction time, query time, simple structure, and low memory requirement. FLINNG utilizes many previously developed techniques, most notably a reduction from approximate near neighbor search to approximate set membership, and solving the latter using distance-sensitive Bloom filters, with a lower bound on the true positive rate and a upper bound on the false positive rate.

To construct the index, FLINNG randomly distributes all data points in $D$ evenly among $B$ groups, and repeats $R$ times to create $R$ such independent instances. For each of the $B \cdot R$ groups created this way, FLINNG constructs a classifier using distance-sensitive Bloom Filters with appropriate error guarantees, which solves the approximate set membership problem on this group.

When a query on point $y$ arrives, FLINNG queries each of the $B \cdot R$ classifiers on whether the corresponding group contains a near neighbor of $y$. If the classifier of a group returns an affirmative result, that group is likely to contain a near neighbor of $y$, and is considered a {\it candidate group}. FLINNG then first takes the union of all candidate groups within the same instance, then eliminates noises and amplifies accuracy exponentially by taking the intersection of the unions across all $R$ instances. The resulting intersection is returned as the near neighbor set of $y$.

The authors show that FLINNG can be highly efficient due to the properties of distance-sensitive bloom filters, which allows queries to have constant memory allocation and sublinear time complexity. An implementation is designed and compared with other status-quo near neighbor search algorithms like FLASH, HNSW, and FAISS, on the PromethION data set. These experiments show that indices constructed with FLINNG exhibit a 2x to 10x speed up in queries, as well as decreased index size and construction time.

main_review: 
Overall, I believe that the article is well-written, well-thought, and of significance. The authors explained in detail the background, prior work, and significance of the problem and their solution, and provided theoretical and empirical evidence of the effectiveness. Although the main body of the article only stated the important theorems and lemmas vital to the analysis, a full proof is indeed provided in the appendix, complementing and completing the authors' argument.

2.1 Originality

The authors did a great job outlining the prior works done on the near neighbor search problem, with adequate citations. FLINNG utilizes the idea of group testing, which differs from a lot of status quo algorithms based on locality sensitive hashing, sample compression, or graph-based methods. Although there are prior works which apply group testing to near neighbor search, these methods are limited in feasiblity and effectiveness. The authors utilized distance-sensitive Bloom filters to circumvent the aforementioned limitations, resulting in an algorithm that performs better than its predecessors.

2.2 Quality

The work is technically sound to my best knowledge. The authors claimed that FLINNG is an algorithm that solves the approximate near neighbor search problem efficiently and effectively, and is comparable and competitive against all the status quo algorithms on near neighbor search. The authors then indeed supported these claims by theoretical analysis as well as empirical data. Theoretically, the overall structure of their analysis is sound, and their results are supportive of their claim: FLINNG can support queries with sublinear time complexity, and the error rate is exponentially small. Following these analysis, the authors provided experimental results, comparing the runtime and accuracy of FLINNG to other status quo algorithms including FLASH, FAISS, and HNSW. Their results show that FLINNG obtains a significant speed up and a decrease in data structure size compared to other algorithms. To my best knowledge, the authors' analysis and experimental setup is correct and sound. While the authors did not discuss the weaknesses of their algorithms except a brief argument in the conclusion, I am unable to identify any characteristic that requires any lengthy analysis.

2.3 Clarity

The article is clearly written with reasonable structure. The authors separated the theorem and lemma statements and the actual analysis, putting the outline of the analysis in the main article, while delaying the proofs to the appendix. This is a common practice, but it is arguable that structuring the proof, perhaps an abridged version under the statements, can better faciliate understanding.

Another critique is that many of the article's stated lemmas and theorems involves many variables and complicated mathematical expressions. While this complexity is justified by itself, there may be a lack of explanation around these statements to compensate for the complexity. This is especially relevant when the details of the proof are delayed to a later section. As a result, I find the lemmas and statements hard to comprehend without scrutiny. It would be better if the authors can append a sentence or two after statements with complex mathematical expressions, Theorem 2, 3, and 4 in the article, for example, to briefly explain the significance and meaning of these statements.

2.4 Significance

It is clear both from the authors' narration and the implications of their results that this article is of significance. Near neighbor search is a problem with many applications in various fields, and any improvement to methods solving the problem will imply more efficient and effective algorithms for all such fields. The authors clearly stated the improvements of FLINNG over other status quo algorithms and supported their claims with sound arguments, both theoretical and empirical. Their algorithms are also quite simplistic in nature, and although I am not experienced enough to immediately identify any potential extensions, no doubt future researchers can build upon this article for further improvements to near neighbor search or other significant problems.


limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Near Neighbor Search (NNS) is one of the most fundamental problems in machine learning. This paper proposes an efficient NNS method for high-dimensional data by transforming the original problem into a group testing problem. The authors provide a detailed theoretical analysis of the distance-sensitive Bloom Filters for group testing to demonstrate how the query time and the quality are bounded with proper parameters settings. Experiments validate the performance of FLINNG.
main_review: 1. I appreciate the idea of using group testing to shortlist the nearest neighbour candidate and use repetition to remove false positives. 

2. FLINNG enjoys a provable bound for query time and quality.

3. This work provides a detailed theoretical analysis to guide parameter settings in the experiments.

4. The paper is easy to follow, and Figure 1 is clear to show the general workflow of the proposed method.

limitations_and_societal_impact: Overall, I like this paper. However, I still have some questions about this paper, and some limitations justify my current rating.

1. The $\gamma$-stable query condition is a relatively strong requirement for the query. As pointed out by the authors, FLINNG works better for genomes data such as RefSeqG and RefSeqP that have ultra-high dimensions. However, for other ultra-high dimensional datasets such as Webspam and URL, the performance of FLASH is better than that of FLINNG, which might be due to this strong query condition. This limit this work to be applied to other applications. Or could you further analyse whether there is any mathematical condition to indicate a dataset as suitable for this method? You can assume the query and data are from the same distribution.

2. For the $m$ hash tables used for the distance-sensitive Bloom filter, the bound of the hash code $h(x)$ is not clearly explained. Since the FLINNG structure is an inverted index (as indicated in Section 6) from hash code to cell, the range of $h(x)$ would greatly affect the space requirement of the index structure. This may need to explain more clearly.

3. The hash functions and distance metrics used for each dataset are not specified. For example, the authors only mentioned some of the datasets are compressed via MinHash, but they did not specify the LSH for the distance-sensitive Bloom filter. I suppose MinHash and Jaccard similarity is applied for the sparse datasets, but what about the dense dataset YFCC100M? And FAISS do not support Jaccard similarity.

4. In the experiments, some necessary information is missing. 
(1) The index construction time comparison with FAISS lack details such as whether the GPU support of FAISS is enabled. Also, since there are plenty of parameter combinations, what exactly is the trade-off between search performance and index constructions. 
(2) The number of queries is not specified for each dataset. For query time, since FAISS can support batch queries so whether the comparison is under maximum query batch size or just one query at a time would greatly affect the query efficiency. 

5. The paper presentation can be further improved. For example, In Section 5, some of the references are clearly wrong and get mixed up with the proof in Appendix, e.g., In Lemma 2 (Line 258), they claim "Under the assumptions in Lemma 2..." Additionally, there is a reference to Figure 4 in the Appendix but Figure 4 is missing.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper tackles the problem of near-neighbor (and nearest-neighbor) search in high-dimensional spaces. The authors propose to use group-testing on top of distance-sensitive Bloom filters: to simplify, the returned set is the intersection of the union of small sets, each of these small sets being a hash bucket that the query falls into. The authors derive the theoretical properties of their method FLINNG (sublinear query time), and show the superiority of their method compared to the state of the art (FAISS, HNSW, FLINNG) through extensive experiments on genome, URL and embedding data.
main_review: The paper is interesting and well-written, and tackles an important problem. 
The construction of the algorithm is smooth to follow at a high-level, even though the meat resides in being able to construct a classifier with given true and false positive rates: to do this in a reasonable time, the authors have to assume gamma-stability which is a strong hypothesis. I was very positively surprised by the very strong empirical performance of the algorithm. I wonder if it is biased compared to other methods that operate on embeddings, because the datasets considered are mostly long sequences which means very high-dimensional data. 
I have a couple of questions for the authors:
- Did you try other embedding datasets that YFCC100M, like Deep1B or BigANN1B?
- How do you go from near- to nearest-neighbor search? In the paper, you mention running Algorithm 3 with various thresholds but Algorithm 3 doesn’t seem to take a threshold as input.
- What setting of FAISS did you use? FAISS is a library implementing multiple quantization-based algorithms, I am assuming this is IMI (Inverted Multi Index)?

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper develops a new algorithm for approximate near neighbor search by combining ideas from group testing and bloom filters. The proposed algorithm called FLINNG casts the problem of finding the near neighbor of a query point in a high-dimensional dataset, as the problem of finding a few number of "positive" groups in a group testing problem where each group captures the absence or presence of at least one near neighbor of the query in a small random subset of data points. The paper provides theoretical justifications of the sublinear query time of the algorithm in number of data points and provides empirical evidence on real-world data sets which demonstrates comparable to superior near neighbor query performance compared to some to some baseline algorithms.
main_review: The paper provides a novel method for the approximate near neighbor problem. The main advantages is that the query time (under some data-dependent assumptions) is sublunar (and therefore fast) and also the implementation is easy and in particular alleviates the need for clustering scheme or graph algorithms. However, the simplicity is highly conditioned on the data-dependent assumption. Therefore, the main limitation is on the gamma-stability requirement of the algorithms which states that the query point should be much more similar to a small subset of size |K| of the data points and be sufficiently far from the rest. This is needed to do the analysis since such data-dependent criteria ensures some notion of sparsity both in the group testing and Bloom filtering stage. My detailed comments are as follows:

Theoretical comparisons. A comparison table containing the theoretical bounds in terms of (at least) the query time and (ideally) the memory and indexing time can be shown to compare FLINNG with other baseline algorithms (including the LSH). This will strengthen the paper and clarify the theoretical contributions. Is there any other sublinear time near neighbor algorithm that employs the stability condition in its bound?

Utility of gamma-stable condition. To ensure the sublinearity claim gamma needs to be smaller than ½ in equation (7); enforcing this condition in Definition 3 yields the condition that s_{|K|+1} < 1/s_{|K|}. For large values of s_{|K|} this will results in very small values for s_{|K|+1}. To convince the utility of the gamma-stable condition it would be helpful to plot the empirical distribution of gamma (if obtainable) for practical values of |K| (e.g., |K| \in {5,10,50,100}) in a few (maybe small) datasets. This is important since the sublinearity bound highly depends on that. Data that are highly clustered clearly pass the condition; an empirical analysis of the datasets listed in the paper can validate that for the real-world datasets in the paper. Also is there any faster way to check if the stability condition is satisfied for a dataset?

Disparity across datasets.  It would be helpful if the authors can explain conditions under which HNSW can significantly outperform FLINNG, see e.g., Figure 5 in the appendix (Webspam Top-1 NN and RL10@10).

Lemma 1. In lemma 1 does increasing R decrease the lower bound for true positive rate? 

Index characteristic. It would be important to add the Index characteristic of Table 2 for other data sets to the appendix.

F-score. Since both precision and recall are critical in these tasks is it possible to add the time against F1 score in Figure 3?

Small typos: line 271: “to achieve good practical”

limitations_and_societal_impact: Yes.
review_title: null

Meta-review: The submission was deemed significant, well-executed, and that it will have impact. While some reviewers had some reservations, the author rebuttals addressed the concerns.
Decision: Accept (Spotlight)