Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a locality sensitive hashing scheme, applicable to approximate nearest neighbor search, using Polar codes as the sparse collection of hash values.
strength_and_weaknesses: The paper does not prove any rigorous guarantees or bounds on the proposed scheme. It's validated solely empirically.
clarity,_quality,_novelty_and_reproducibility: The writeup is clear, but hard to evaluate lacking any concrete claims that the scheme generally works, or works under certain assumptions.
summary_of_the_review: It's an interesting idea, but its validation is not convincing.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the approximate nearest neighbor search problem.  Specifically, this paper proposes a Polar Code Nearest-Neighbor (PCNN) algorithm. This algorithm uses error-correcting codes to build clusters in the latent space in high dimensionality.  Compared to classical LSH clustering, PCNN uses few hash tables to achieve the same performance. As a result, PCNN is memory efficient compared to LSH.
strength_and_weaknesses: Strength:
1. The combination of LSH and error-correction code is novel. 

2. This paper is well-organized. Figure 1 is illustrative for readers to understand the functionality of PCNN

3. Large ANNS datasets are used for empirical evaluation, making a fair comparison of PCNN with LSH

Weakness:
1. Stronger arguments is required for the motivation of applying  error-correction code in ANNS.

2. In the evaluation, the comparison of PCNN with product quantization approaches is missing.

3. For binary datasets, MinHash algorithms should also be considered as a baseline.


clarity,_quality,_novelty_and_reproducibility: The proposed PCNN algorithm is easy to follow. The paper is well-organized.
summary_of_the_review: This paper introduces the error-correction code techniques in the field of ANNS, This combination is novel since it opens a new direction for ANNS. However, both the motivation and empirical evaluation can be further improved for better quality.

Questions
1. Is there any justification for why error-correction code should be applied in ANNS? Why is error-correction code a better way to manage LSH functions?

2. Is it possible to provide theoretical guarantees on the clustering quality of PCNN?

3. In ANNS evaluation, it is inevitable to compare with state-of-the-art graph/quantization approaches for efficiency-accuracy tradeoffs. In this setting, LSH-based approaches may not be the best choice for dense vectors. I would recommend a study in high dimensional and sparse regime with a comparison to Minhash

4. Can we provide privacy guarantees for PCNN?
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Takes the idea of polar codes (and polar coding) to develop an approximate nearest neighbour scheme with some efficiency.
Investigates the application of that to search in three databases - all three containing SIFT visual descriptors but one containing text as well.
The claims and results tend to show that the method produces better recall than the competitors (principally variants of hyperplane LSH with various numbers of multiple tables; although another version of LSH using a (data dependent) hyperplane chosen using the method of Tissier et. al is also briefly investigated). 
This better performance on recall is despite using less than the sort(D) distance computations for a dataset of size D, generally required for the comparators.
strength_and_weaknesses: The strengths are that the proposal seems sound - using polar codes seems like a good thing to do and this is supported by the experiments. The paper is well written in most ways. So I believe this is a solid paper with a solid contribution and written at least welklk enough for acceptance.

As per the next section - the novelty *whilst probably enough* doesn't seem that inspirational and that insightful *on my reading* of the *current manuscript*. In that regard, perhaps the hypothesis that the cdim=d is a good choice (mentioned in the footnote 2 and elsewhere) might be the more interesting aspect to the work from my perspective - and it's a pity there isn't more light on this. That said, the paper is solid enough to be a really strong contender for publication even in the current form.

The range of data sets seems limited. I don't want to make strong point here - however it would be better to demonstrate performance on a wider variety of database types and hence potential applications - but I am mindful of the time cost and decline pressures.


clarity,_quality,_novelty_and_reproducibility: While the paper says in part that it uses a standard (freely available) python library - it does say "heavily modified" and it isn't clear to me how much of the three algorithms that make up the overall scheme, are "covered" but the library - the placing of the aforementioned comment, in the paper, suggests only for algorithm 3. However, they declare they will make the code available. That would *suggest* that the reproducibility should be somewhat assured.

The novelty appears to be clearly in the recognition that polar codes could be used in ANNS. It seems to me, from my standpoint, that unless there is missed prior art in that respect, then the novelty is sufficient. I am not all that clear on how much of an inspirational jump it is to make the connection but at the moment I am inclined to believe it is significant. (BTW on the "forced choice" questions below I can only choose "The contributions are significant, and do not exist in prior works." because all other options seem too strong in the implied deficiencies they offer). Somewhat ditto on empirical support - even though this is one area the paper could be improved, clearly.

Overall, the clarity of the paper and the quality seem good to me. That said, I find the main part a bit slow and repetitive and suspect it would be improved by making it tighter and space saving so that more of the appendices could be fitted into the main paper.
summary_of_the_review: It seems to me the gains are sufficient to be of interest to people (working in or reliant on ANNS). It seems to me the idea is sound, and if not already published, should be. The paper is written well enough. These three things - to me - are completing for acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors investigate a problem in clustering by locality-sensitive hashing for similarity search. They introduce a new method called the Polar Code Nearest Neighbor (PCNN) method that uses the polar codes to maintain a number of clusters in a high-dimensional embedding space. By utilizing the list-decoding method, they propose a multi-probe scheme for PCNN to efficiently determine the closest clusters to the query. Extensive experiments confirm the superior performance of PCNN over the classic hash clustering (CHC).

strength_and_weaknesses: The paper has the following strengths:

S1. This paper is well-motivated. Vanilla methods often embed the original data points into a low-dimensional latent space, which usually distorts the distance for many pairs of data points. Thus, considering a high-dimensional latent space might be promising. 

S2. The experimental analysis is extensive. The experimental results demonstrate the superiority of the proposed approach compared with CHC. Other interesting experiments related to the impact of $\alpha$ and \textsf{sizenn}, robustness and extension to different LSH functions are also included in the supplementary material.

The paper has the following weaknesses:

W1. Even though I like the motivation, the authors only directly leverage the polar codes and the list decoding method for multi-probing, which makes the novelty somehow limited.

W2. They indeed embed the data point in a high-dimensional latent space (i.e., \textsf{cdim} bits), but the closest clusters they aim to find for the query are represented in a low-dimensional space (i.e., \textsf{nbit} bits). Can you provide more insights into the benefits of the high-dimensional latent space?

W3. I think the \textsf{ndis} is a good measurement if we want to ignore the benefits from the implementation level; it could be better if the author could also contain the embedding cost. For example, for the hyperplane LSH by Charikar (2002), as both distance cost and a single LSH function cost are O(d), each LSH function can be included and considered once \textsf{ndis}.

W4. The experiments provide many results about different \textsf{cdim} values. As \textsf{nbit} is also a vital parameter for PCNN, Can the authors also provide some more results about the impacts of different \textsf{nbit} values?

W5. They provide pre-processing time and query time complexities for PCNN. To make a complete analysis. It will be nice to provide space analysis. It would also be nice to extend the experimental analysis with a scalability study to examine how the \textsf{ndis} evolves as the size of the input data increases.


clarity,_quality,_novelty_and_reproducibility: This paper is well-written, and the figure makes the techniques easy to follow. 

A minor issue with the clarity is that readers might not be familiar with the Polar code and the list-decoding methods. They might shorten the experimental setup (e.g., simplify the datasets and provide more details in the supplementary material) to make room for moving the background of the Polar code and the list-decoding methods to the main paper.
summary_of_the_review: In summary, the authors did a good job by leveraging the Polar code and the list-decoding method for similarity search, but I still have some concerns about its effectiveness and some issues in the experiments. Thus, I initially give a borderline acceptance.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: All reviewers consider the use of polar codes to be an interesting idea, and no reviewer provides any objection to the claim of novelty.

Two reviewers ask for further theoretical analysis.   The rebuttal argues that such an analysis is not available for nearby multiprobe techniques, so would be difficult here.  In AC/Reviewer discussion it was agreed that such analysis might well prove to be future work for these or other authors, and so its absence should not preclude publication of the paper.  

The claim, in the rebuttal, that product quantization should be orthogonal to the novelty of this work, was considered plausible, but it would greatly improve the paper to include experiments that test that hypothesis.  Particuarly given the discussion of empricial vs theoretical contribution, it would be appropriate to empirically confirm this claim.

Other reviewers' questions were adequately answered in rebuttal.
justification_for_why_not_higher_score: Nearest neighbor search is an important component of many real-world machine learning systems, so advances in its efficiency have potentially wide impact.  On the other hand, the paper's improvements are presented primarily over related baselines, so its efficacy in industrial-strength systems (cf SPANN/Faiss) remains to be seen.
justification_for_why_not_lower_score: All reviewers consider the use of polar codes to be an interesting idea, and no reviewer provides any objection to the claim of novelty.
Decision: Accept: poster