Optimal spherical codes for locality-sensitive hashing

The writing is so bad with many missings or minor errors, or unclear-ness.

1. Graph-based methods and vector quantization methods are widely used for vector search now and show significantly better performance than LSH. The authors state that “Whereas graph-based techniques perform very well in low dimensions, their performance is suboptimal in higher dimensions, and cannot be used in distributed settings.” This is NOT true! The HNSW paper shows that proximity graph works quite well for high dimension vectors, and the Pyramid paper uses proximity graph for distributed vector search. Also, the FAISS library uses many variants of PQ and the IVF index for vector search. I am not convinced of the practical impact of this paper unless the authors show that the proposed LSH achieves better time-recall curve than graph and quantization methods. Note that time-recall curve is a standard method to evaluate the performance of ANNS, and examples can be found in the HNSW paper. [1] Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (HNSW) [2] Pyramid: A general framework for distributed similarity search on large-scale datasets (Pyramid) [3] Product Quantization for Nearest Neighbor Search (PQ)

2. Experiments are very limited. (1) Nowadays, million or even billion scale datasets are common for vector search (check the Pyramid paper) but the authors use a datasets of 10,000, which are extremely small. (2) The proposed method needs to check every vector in the dataset to compute Hamming distance, which is infeasible for very large datasets. (3) Pls use standard time-recall curve to compare the performance of the authors in the main experiments. The influence of m/d can be used as a micro experiment to check the influence of parameters.

3. I think the paper is not ready for publication is its current state and would benefit from substantial revision for another conference. For instance, there are multiple missing references even in the introduction. Some statements are not logical or scientific due to the lack of checking. For example, “LSH…, where the imperative is to swiftly identify similar items without sacrificing accuracy.”, well, LSH actually sacrifices accuracy to identify similar items swiftly; “To balance between accuracy and query time, we can make sure the centroids used for the space partitioning are maximally separated”, balance is a vague term, and how does maximal separation leads to such balance?; “Existing LSH has …(ii) limited use cases”, what exactly are the use cases your proposed method can handle and existing LSH cannot?; “These methods however are limited for use with a specific hash length or embedding size”, why is the case? To my knowledge, at least random projection allows to handle arbitrarily long embeddings and flexibly set the length of the embeddings.

4. How does the method handle more general cases, i.e., when dataset vectors are not on the unit sphere? The optimization objective in (1) is different from the max-min objective of OSC. What is the relation of the solution produced by Algorithm 1 w.r.t. the solution of OSC? Can you show that it is a good approximation?

W1. Dependency on Optimal Spherical Codes: The efficacy of OSC-LSH is tied to the quality of the spherical codes. However, as pointed out by the authors, the identification of the optimal spherical codes is computationally prohibitive, especially when $d$ (and $m$) is large. In cases where optimal codes are hard to find, this method might not offer significant improvements.

W2. Ambiguity in Distortion Definition: The paper frequently references the concept of "distortion" when discussing the benefits of using Optimal Spherical Codes (OSC) in LSH. However, a clear and concise definition of distortion is missing, making it difficult to fully understand and evaluate the proposed method's effectiveness. While Figure 1 shows the minimum distance in a self-comparison context, it doesn't provide a comprehensive view of the distortion in the mapping process from the input space to the output space.

W3. Concern of the Optimization Objective: Under the assumption that all data points are normalized, the Euclidean distance between any $c_i$ and $c_j$ is inversely proportional to their inner product. Thus, it is problematic to directly replace Euclidean distance in Equation (1) with the inner product in Equation (2). Is there any typo in Equation (2), e.g., removing the "$-$" or maximizing $L$?

W4. Unconvincing Empirical Results.

W4.1. Lack of End-to-End Comparison: While the paper compares the new approach with RP-LSH and FlyHash, it would be beneficial to see the end-to-end comparisons with other state-of-the-art ANN search methods, such as FAISS and HNSW.

W4.2. Scalability Concerns: Although the authors claim they have improved the efficiency issue, the paper doesn't delve deep into the scalability of the proposed method, especially when dealing with extremely large datasets.

W5. Poor Presentation: This paper seems to be written in a hurry way. For example, there exist many "???" and empty "()." The two Algorithms are isolated from the main paper, and no explanation is provided. In the experiments, they claim to use five datasets, but I failed to find the results on CIFAR10.

1. On the datasets they consider, there is not a marked improvement over the baselines.
2. It seems that they are performing an optimization procedure for computing the code vectors, but not actually using any data - it seems like if you are going through the trouble to optimize the code vectors then it might help to actually use the data (so that the code vectors chosen can reflect the actual underlying data distribution).