Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The author proposed a locality-sensitive filtering approach with an asymptotically lower query time algorithm than Falconn and competitive to efficient indices like HNSW. Falconn++ keeps only the top-($\alpha B/iProbes$) points (closest to the hyperplane $r_i$) in each bucket. The closeness is defined by the threshold on the inner product distance $t = (1 − r 2 /2) 2 log D$, from the $r_i$. A limit scaling strategy is added for more balanced buckets and higher query-recall performance.
strengths_and_weaknesses: Strengths

1) Theoretical analysis is adequate and conveys the proposed approach's correctness.

2) The paper is well written. The preliminary ideas and the state of art methods are thoroughly discussed.

3) Experiments with SOTA ANN approaches: The work has compared Falconn++ with Falconnlib, HNSW, FAISS, ScANN, and coCEOs over Million scale datasets. Falconn++ beats these state-of-the-art approaches in the high recall region.

4) New heuristics have shown improvement over the proposed LSF approach.

Weakness

1) It is great to see the comment on the comparison with other LSFs[4][8].  It will be good to see the experimental comparison as well for thorough evaluation. (citations from the paper)

2) No performance evaluation in lower recall regime- especially for HNSW and ScANN; however, comparison with coCEOs covers almost the entire spectrum. ScANN is really good in the high recall region, and it is great to see that Falconn++ is very close to it and even beats it on smaller-scale datasets. However, it will be helpful to analyze how Falconn++ performs against them in the mid-recall region (0.5-0.8), as the near neighbors in mid-recall are also useful for many practical search systems. Same argument for FAISS and HNSW. 

questions: Questions:
1) Where are the significant query time improvements (empirical) coming from compared to Falconnlib? Is it due to filtered far-away points in buckets or the heuristics? 
2) I am not able to locate the metric. Everywhere it is mentioned as a recall. Is it Recallk@k where k is 20 or something else?
3) How does Falconn++ compares with Fast cross polytope LSH*?

*Kennedy, Christopher, and Rachel Ward. "Fast cross-polytope locality-sensitive hashing." arXiv preprint arXiv:1602.06922 (2016).
limitations: The authors have addressed their work's limitations and potential negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper investigated a fundamental problem of approximate nearest neighbor search on angular distance. The authors developed a practical LSF approach called Falconn++ that combines the LSF property with the LSH to achieve a lower query time complexity beyond the vanilla LSH schemes such as Falconn. Extensive experiments validated the superior performance of Falconn++.

strengths_and_weaknesses: Strengths

S1. The pattern of LSF + LSH is very interesting to me. Even though the two key components (i.e., CEO and Falconn) of Falconn++ come from existing work, they discover a promising way to combine them together and provide a comprehensive theoretical analysis.  

S2. They conducted a systematic comparison of Falconn++ with Falconn and HNSW. Extensive results justify their theoretical analysis and validate the superior performance of Falconn++.

S3. The paper is well organized and easy to follow.

Weaknesses

W1. The proposed Falconn++ contains many parameters, such as D, L, $\alpha$, iProbes, qProbes. In the experiments (Subsections 4.2 and 4.3), they config different values of L, $\alpha$, iProbes for Falconn++ when comparing with different methods even for the same datasets. Thus, it might be more comprehensive and beneficial for practitioners if they could make a discussion for the parameter settings. 

W2. The experiments might be more convincing if they could study the sensitivity of k for Falconn++. 
questions: Q1. Followed by W1, can they conduct more experiments for parameter settings? Or provide more theoretical (or empirical) analysis for the impact of the parameters. 

Q2. Followed by W2, can they compare Falconn++ with FalconnLib and HNSW for different values of k (e.g., from 1 to 100)? 

Q3. Can they discuss the possibility of extending the pattern of LSF + LSH to support the ANNS on other similarity/distance measures? 
limitations: Yes.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes an interesting extension of the special LSH scheme for angular distance (and cosine similarity) nearest neighbor search. Specifically it proposes a filtering mechanism and proves that it leads to asymptotically better retrieval times. Empirically, the approach is competitive with the graph-based retrieval algorithm HNSW for high recall values. 

Nearest neighbor search is a backbone of many recommender and retrieval systems. Clearly, it is important to be able to do this task well. There has been historically a competition of several approaches including LSH, randomized trees, quantization approaches, and graph-based retrieval methods with sometimes comparable outcomes. It has been a useful competition, because different methods have different strengths and applicability. In my opinion, this is an important line of research.

The paper proposes an interesting trick to index-time filtering of unpromising data points. This is possible, because the inner product between a bucket "pivot" and a query is quite close to the *SCALED* inner product between the query and data points in a bucket (BTW it's nice to point out that scaling arises from the fact that data/query are normalized but "pivot"/sampled vectors are not). Authors further show this property can be exploited both theoretically and practically to improve upon FALCON.

In terms of theory, they show it for a c-approximate nearest neighbor search. For practical purposes, one has to resort to theory-inspired heuristics. I think it's totally fine, but the paper should be clear about it. 

Empirically, the method improves upon the original FALCON and claims to be comparable to HNSW, but only in high-recall zone when the number of threads are large. Although this was not in the original version of the paper, additional experiments revealed that HNSW implementations seems to scale poorly with the number of threads, at least for the specific architecture used in the paper.

So, potentially HNSW can work better, but we don't know this for sure. This is unfortunate, but resolving this issue may require a separate paper. I personally think that the most important baseline in this work is FALCON. Plus, if the approach is more scalable (with the number of threads), this is certainly a plus.

strengths_and_weaknesses: 
1. The paper is a bit messy and many explanations are confusing. Although with some effort the paper is understandable, but the presentation can be improved substantially.
2. The centering trick is NOT NEW and it was used in FALCON when it was incorporated into ANN BENCHMARKS. Please see a reference below. 

Generally, math makes sense to me, but I did not check very fine details. In particular, I have to trust the derivation of the Eq. (3) from prior work, but I haven't checked this derivation myself.

https://github.com/erikbern/ann-benchmarks/blob/406574ef659338accb6a926a097099c1691ef8f3/ann_benchmarks/algorithms/falconn.py#L29

questions: **Some detailed comments:**

25-27, please give a clearer definition of a decision version of the problem.

34 citation is needed.

45-46 not only that but old-style random-projection LSH often performs no better than a VP-tree modified for approximate search. They are also typically outperformed by random-projection trees. If I remember correctly authors of FLANN have some comparison points.

123-124 how is it different from the original FALCON ordering of buckets in line 115? In lines 234-237 you remove the absolute value, is this actually the difference?

126 a significantly large NUMBER of vectors ??? Same issue in line 169.

127 Eq (3) can possibly be accurate for x == q, because we get zero variance. I guess it should have some error term diminishing with D.   

Also lines 128-129 We can see that, among D random vectors, if r1 is closest (or furthest) to q, then the projection values of *ALL* points in X preserves their inner product order expectation -> I feel this is a very inaccurate description. First of all, the equation doesn't say anything about expectation of *ALL* points. It does say that the distance is preserved with a high probability P for a given pair of points. If you have three points, the full order preservation is going to be only P^2, etc... for a large enough set it's going to be close to zero IMHO. However, I believe the expected number of preserved distances should be high.

135-143 This is confusing. If the filtering heuristic is used at indexing time, it is not related to multi-probing. It should improve performance of a regular single-probe LSH as well, because unlikely candidates are going to be pruned. 

173-174  If this is index-time filtering why does it depend on the query q? I think I understand what you are talking about, but some explanation won't harm. 

241 The centering approach is not new and it was in fact used in FALCON when FALCON was still present in ANN-BENCHMARK. Please, see, e.g., the code here:

https://github.com/erikbern/ann-benchmarks/blob/406574ef659338accb6a926a097099c1691ef8f3/ann_benchmarks/algorithms/falconn.py#L29



limitations: 1. negative societal impact discussion isn't really applicable.
2. authors discuss limitations of their implementation as well as limitations of approximate nearest neighbor search in general.
review_title: null

Meta-review: metareview: The paper provide a good and exciting improvement over LSH based widely used Falcon Library. All the reviewers found the contribution worthy of publication. 
confidence: Certain
Decision: Accept