Approximate Nearest Neighbor Search through Modern Error-Correcting Codes
Authors: Noam Touitou
Nissim Halabi
Venue: ICLR 2023 poster (2023)
Keywords: Similarity Search
Nearest-Neighbor Search
Polar Codes
Locality-Sensitive Hashing
LSH

Abstract: A locality-sensitive hash (or LSH) is a function that can efficiently map dataset points into a latent space while preserving pairwise distances. Such LSH functions have been used in approximate nearest-neighbor search (ANNS) in the following classic way, which we call classic hash clustering (CHC): first, the dataset points are hashed into a low-dimensional binary space using the LSH function; then, the points are clustered by these hash values. Upon receiving a query, its nearest neighbors are sought within its hash-cluster and nearby hash-clusters (i.e., multi-probe). However, CHC mandates a low-dimensional latent space for the LSH function, which distorts distances from the (high-dimensional) original real space; this results in inferior recall. This is often mitigated through using multiple hash tables at additional storage and memory costs.

In this paper, we introduce a better way of using LSH functions for ANNS. Our method, called the Polar Code Nearest-Neighbor (PCNN) algorithm, uses modern error-correcting codes (specifically polar codes) to maintain a manageable number of clusters inside a high-dimensional latent space. Allowing the LSH function to embed into this high-dimensional latent space results in higher recall, as the embedding faithfully captures distances in the original space. The crux of PCNN is using polar codes for probing: we present a multi-probe scheme for PCNN which uses efficient list-decoding methods for polar codes, with time complexity independent of the dataset size. Fixing the choice of LSH, experiment results demonstrate significant performance gains of PCNN over CHC; in particular, PCNN with a single table outperforms CHC with multiple tables, obviating the need for large memory and storage.

Published as a conference paper at ICLR 2023
APPROXIMATE NEAREST NEIGHBOR
SEARCH
THROUGH MODERN ERROR-CORRECTING CODES
Noam Touitou
Nissim Halabi
Amazon noamt w com
niss i & @mhhgmail.com
ABSTRACT
A socality-sensitii hash (or LSH) is function that can efficiently map dataset points into a latent space while preserving pairwise distances. Such LSH functions have been used in approximate nearest-neighhor search (ANNS) in the following classic way, which we call classic hash clustering (CHC): first, the dataset points are hashed into a low-dimensional binary space using the LSH function; then, the points are clustered by these hash values. Upon receiving a query, its nearest neighbors are sought within its hash-cluster and nearby hash-clusters (i.e., multi- probe). However, CHC mandates a low- low-dimensional latent space for the LSH function, which distorts distances from the (nigh-dimensional) original real space; this results in inferior recall. This is often mitigated through using multiple hash tables at additional storage and memory costs.
In this paper, we introduce a better way of using LSH functions for ANNS. Our method, called the Polar Code Nearest-Neighbor (PCNN) algorithm, modern error-correcting codes (specifically polar codes) to maintain a manageable number of clusters inside high-dimensional latent space. Allowing the LSS function embed into this high-dimensional latent space results in higher recall, as the em- bedding faithfully captures distances in the original space. The crux of PCNN is using polar codes for probing: we present a muuli--probe scheme for PCNN which uses efficient list-decoiing methods for polar codes, with time complexity inde- pendent of the dataset size. Fixing the choice of LSH, experiment results demon- strate significant performance gains of PCNN over CHC; in particular, PCNN with single table outperforms CHC with multiple tables, obviating the need for large memory and storage.
INTRODUCTION
In similarity search, one is first given dataset D of points, then a set of query points from the same space. For each query, the goal is to find the closest point (or points) in D to that query, according to some given metric. The simplest way to find these nearest neighbors of query is to calculate the distance of the query from each point in the dataset D; however, when the dataset D large, this linear cost in the dataset's 's size is prohibitive. Thus, upon query, one would like to consider only small subset of D. Since these non- coneuuhaustive algorithms do not consider all points in the dataset, we are interested in approximate similarity search, with the following relaxations:
We allow an approximation ratio, i.c., the algorithm is allowed to return neighbors whose distance the query is most some factor a > times the distance of the nearest neighbor to the query Since the algorithm does not explore all points, it can sometimes return a result which is not within the desired distance; the fraction of results which are within the desired range is called the recall of the algorithm.
Clustering Methods. A common technique for approximate similarity search is to divide the dataset D into clusters. Then, upon receiving query, the algorithm would only search the points of D that appear in the clusters which are closest to the query. (If the clusters are represented by points in the original space, the distance to the query is well defined. Otherwise, a different metrie is needed.) Algorithms based on such clustering are often used in practice, since they allow storing different clusters on different machines (i.e., sharding) for efficient distributed processing of queries.
For similarity measures, which should be maximized, we would instead be interested in < 1.

---

Published as a conference paper at ICLR 2023
In light of these benefits of clustering methods, we would like to study them in our approximate setting. However, existing clustering methods have some drawbacks in this setting, which motivate the algorithm presented in this paper. We now explore two popular clustering methods and describe their drawbacks.
Clustering by Training Cluster Centers. In this method, introduced by Sivie & Zisserman (003))
cluster centers are trained on the dataset (or some sample of the dataset) using a clustering algorithm (namely k- k-means), and each dataset point is mapped to cluster (c.g., by the nearest cluster center). Upon query, the clusters corresponding to the closest cluster centers are searched. This common algorithm is part of the popular Faiss library (Johnson et al. (02T) as the default inverted-file (IVF) method; we henceforth refer to this method as IVF. Since the cluster centers are unstructured, finding these closest centers requires a number of distance computations which is linear in the number of centers. The total number of distance computations (for both centers and dataset points) is therefore always at least the square root of the dataset's size. Thus, while popular in general, this method is less appropriate for an approximate regime in a large dataset, as we would like to get high recall using a much smaller computational cost, independent of the dataset size.
Clustering by Locality-Sensitive Hashing. Another such clustering method uses Locality- Sensitive Hashing, or LSH (Indyk & Motwani 1998). In this method, a locality-sensitive hash
h _R {0, 1] rbbil is used to map the dataset to hash codes (nbit-bit strings). Each such hash-code identifies a cluster which contains the dataset points in the hash-code's ' preimage. Upon receiving a query g. the hashcode h(g) is calculated, and closest points are search only within the clusters iden- tified with the closest hashcodes to h44) (Ly et al. 2007). We refer to this simple method, which is used in most classic LSH papers, as Classic Hash Clustering, or CHC for short. Note that the choice of the LSH function / is independent from the operation of CHC, and should be chosen such that distances in the embedding space approximate distances in the original space; two possible choices (which we also consider in this paper) are hyperplane LSH (Charikar 2002) and the data-dependent autoencoder LSH (Tissier et al. 2019).
The fact that CHC uses L.H functions provides some advantages. First, the closest clusters to a query can be found without calculating its distance every cluster, this makes CHC more suitable for the approximate regime than IVF. Second, the index in CHC can be easily augmented with additional dataset points in an online fashion, as the clustering is not trained on the dataset. In addition, CHC usually has a low memory/storage footprint. However, using CHC does not usually achieve high recall; this is usually alleviated by using multiple tables (i.e., multiple clusterings), at significant memory and storage costs.
Why does CHC achieve low recall? A possible explanation could be that the distances between the dataset/query points in nigh-dimensional space ER are not faithfully captured by the hashing to the space f0. } Iibi This is since the hash-code space must be din-dimessoonal, as memory and running time restrictions make it infeasible to large nbit. For example, if one chooses nbit = 40 (and thus 240 clusters) for a dataset of a billion points, 99.9% of the clusters would be empty; Thus, nbii must remain small, and usually does not exceed 32. However, this severely limits the granularity of distances, as Hamming distances in this low-dimensional binary space only take on one of 32 non- zero values. This lack of granularity appears in all LSH functions (including data-dependent functions). In addition, using low number of embedding bits could yield a high variance the distance of any embedded pair of points. For example, consider hyperplane LSH: in this method, the expected relative Hamming distance of the hash-codes is equal to the relative angular distance between the original points (Charikar 20002, but the bits of the hashcode are generated independently. Thus, the deviations from the expectation are very significant when the number of bits is low, as mandated by CHC. These drawbacks of CHC thus call for different technique, which is able to simultaneously utilize distance information from a nigh-dimensional binary embedding, as well as preserve a reasonable number of clusters.
property of every low-dimensional embedding. and thus
Our Contributions. In this paper, we present a generalization of CHC which uses modern error- correcting codes (ECCs); we call this method the Polar Code Nearest Neighbor algorithm (or PCNN). PCNN encapsulates any LSH method H, similar to CHC, but yields superior performance. CHC uses H to embed into nibt-dimensiooal binary space for some low nbit (c.g.. nbit 30); PCNN instead uses H to embed into odim-dimensional binary space, for some cdim > nbit (e.g., cdim 512). Then, the embedded dataset in PCNN is clustered, such that the set of clusters forms a nbit-ddiensioonal subspace inside the larger cdim-dimensional embedding space. Upon query, the
2

---

Published as a conference paper at ICLR 2023
probing procedure is performed in the high-dimensional embedding space. As later discuss, CHC is a special case of PCNN in which nbit = cdim.
By separating the dimension of the embedding space cdim from the dimension of clusters nbti, PCNN addresses the previously-diseuseed shortcoming of CHC, i.e., the low dimensionality of the resulting embedding which leads to distortion of distances. PCNN performs probing on large, cdim-dimensional space, in which distances between embedded points better approximate the dis- lances in the original space. At the same time, PCNN maintains the same number of clusters as CHC (i.e., 2 In addition, PCNN enjoys the benefits of CHC: has an index which is small and easily extensible, as well as an efficient probing method whose running time does not depend on the number of clusters.
Polar codes and List Decoding. The crux of our algorithm is the choice of cluster centers in this nigh-dimensional binary space: these centers chosen to allow efficient mapping from binary point to the closest centers, for the sake of multi-probe error-correcting codes, namely the modern polar codes: choosing the centers be the codewords of a polar code allows us to use list-deooding, an ECC technique which efficiently maps from a binary word the closest nprb codewords, for any parameter nprb. Specifically, list decoding to the nprb closest codewords (i.e., multi-probe in PCNN to find the nprb closest clusters) runs in time (nprrb cdim log nbit); this is nearly optimal, as nprb cdim is the representation size in bits of the nprb closest cluster centers themselves (See Appendix for detailed complexity comparison.)
This is where we use recent advances in
Evaluation. We evaluate PCNN empirically on real-valued real-world datasets, and establish that it performs significantly better than standard (multi-probe) CHC. As PCNN can be used to encapsulate any LSH method, chose to evaluate PCNN against CHC on two very different LSH methods: the first is the classic hyperplane method (Charikar 2002).. and the second is a data-dependent method based the output of autoencoder (Tissier et al., 2019). Moreover, we also show that PCNN outperforms CHC with multiple tables, while having a memory and storage footprint identical to that of single-table CHC. This implies that PCNN is strong alternative to using CHC with multiple tables.
We also evaluate PCNN on binary datasets, where both PCNN and CHC run directly on the dataset points (and thus a real-to-binan binary LSH not needed). The baseline here is provided by the IndexBi- MaryMultHHash class from Faiss (Johnson et al., 2021). The results mirror those for real datasets, showing a clear advantage to PCNN.
In summary, in this paper, we give the following contributions:
We present the PCNN algorithm as a new clustering method for approximate nearest-neighbor search. The PCNN algorithm uses error-correcting codes specifically polar codes to index according to a high-dimensional binary embedding while keeping the number of clusters low. We provide multi-probe scheme for PCNN, which is based on efficient list-decoding algorithms for polar codes.
We evaluate PCNN vs. multi multi-probe CHC baseline, and show robust performance gains. Source code of the PCNN algorithm and the evaluations presented in the paper can be found on https//ggitub..co//mmm////// http:///aaaaaaaaaaneeeeeeniiniie
2
RELATED WORK
ANNS is fundamental to applications in many domains with various specifications' trade-offs, in- cluding preprocess and search time complexity, search quality, memory size, scalability with dataset size and data dimension, robustness to query workloads and dataset updatability, and more (Li et al. 2020 Aumüller et al., 2020). Two main categories of ANNS are graph- methods and inverted index clustering based methods. Graph-based algorithms such as (Hierarchical) Navigable Small World graphs (Malkov et al.) 2012; 2014| Malkov & Yashunin 2200)), NSG (Fu et al. 2019), and DiskANN (Jayaram Subramanya al. 2019) achieve good performance in non-distributed setting.
This paper focuses on clustering methods for ANNS, in which their support for sharding makes them commonly used in practice for billion scale updatable datasets with high query workloads. As outlined in Section] [ clustering methods for ANNS may divided into two popular types: trainable
As noted later in the paper, a good choice for cdim is the original real dimension d. In this regime, the cost. of the binary emhedding (dddiim) (ccdim") dominates the cost of the list decoding.
3

---

Published as a conference paper at ICLR 2023
(a)
(b)
(c)
(d)
(c)
Figure I: A visual illustration of the PCNN algorithm (Algorithms I using the cdim- dimensional binary cube sketched by a grid of 2adim points. Sub-figures (a)-(c) deal with initial- ization and preprocessing and sub-figures (d)-(e) deal with querying. (a) Embedding of the dataset vectors in D by I2 +
(green solid). (b) 2 polar [odim, nbifj -code codewords C S {0, 1 cdim (purple solid) whose nbit-bits identifiers comprise the index entries. (c) Partition M of the dataset D, comprised of 2 partitions. The partitions correspond to Voronoi cells (rectan- gles) induced by the codewords C and computed by LISTDEC with E (d) Extracted nprb cluster IDs of focus for query q. Retrieved by LISTDEC of h(g) (red solid) with & = nprb, using time proportional to nprb that does not depend on |C), (e) Find the nearest vectors to q with respect to the subset of D contained in the extracted nprb clusters of focus.
(data dependent) and structured (data independent). The main line of works for trainable clustering methods follows from SSivic & Zisserman (2003) through the popular Faiss library (Johnson et al,, 202I] to state-of-the-art algorithms such SPANN (Chen al. [02I). Yet, the time complexity of these algorithms remains dependent in the dataset size (at least square-root in the case of Faiss/IVF and loga-itgaii in the case of SPANN). Modern machine learning techniques (such as neural networks) are also studied lately (e.g., (Kraska et al.) 20188) [Wang et al. 22018) Dong et al.) (2020), dealing with space partitioning of the dataset. However, the need to search for closest clusters (for multi-probe) still remains dependent in the dataset size.
Locality-sensitive hash functions have much previous work; see for example Wang et al. (2014); Jafari et al. (2021); Charikar (2002); [Andoni et al. (2015); Terasawa & Tanaka (2007): Laarhoven (2017). Often, such LSH functions are used for clustering using CHC (and possibly using multi- probe or multiple tables). Another popular use binarization for efficient distance computations (e.g., for speeding up exhaustive search). Notably, recent works LSH introduced sparse high- dimensional hash codes for similarity search inspired by the fly's olfactory circuit Dasgupta et al.) (017)) (Sharma& & Navlakha (2018); [Ryali et al.] (2020). However, these hash codes lack multi- probe technique in high dimensions which is necessary for high recall, and result to recursively reduce to low dimensions for multi-probe.
THE PCNN ALGORITHM
The main idea of the PCNN algorithm is to embed the real-valued dataset D C Rd from the orig- inal real-valued space into high-dimensional binary space (0, 1} 1ccdim but only allow some much- smaller subset C C {0, 1} cdim to be cluster identifiers, where |C| = 2nbbt for nbit < cdim. The index comprises the cluster identifiers of all points in the dataset. Upon receiving query q E Rdd the algorithm would embed g into {0, 1} adim find the closest cluster identifiers in C, and search within those clusters. In such a setting, cdim would be chosen as large enough to faithfully capture dis- tances in the original real space (as discussed the introduction for, e.g., hyperplane LSH (Charikar) 2.0Z). while CI would be chosen through memory and running-time considerations. For example, for a dataset C IR 128 such that [D] = 224 one could choose cdim 128 and nbit = 24.
In implementing this algorithm, a technical problem arises: upon receiving a query, how does one efficiently find the closest clusters in C to that query? We solve this problem using error-correctng codes.
Error- Ceroo-Correeting Codes (ECCs) and Polar Codes. A linear, error-correcting [N, -code is subspace C of dimension K in {0, 1)xh By and large, good code C' should satisfy two properties. First, the words in (called the codewords) should be spaced, such that the distance between any two such words is large. Second, the code should have an algorithm for efficient decoding, i.e.,
4

---

Published as a conference paper at ICLR 2023
mapping from arbitrary word in 10.1)* to the closest codeword in C' (in Hamming distance). Another, more advanced property is efficient list decoding. which is mapping from such a word to the closest nprb codewords in C, for some parameter nprb. Note that good codes require careful design. For example, random linear codes have good distance properties, but do not admit efficient decoding algorithms (specifically, decoding such codes is NP hard (Berlekamp et al., (1788). Unlike classical crror-correcting codes, modern ciror-correcting codes have a structure that mimics random linear codes, but admit efficient probabilisticc decoding (Richardson & Urbanke 2008
A recent family of such modern codes is polar codes, introduced by Arikan (2009). These codes support every choice of N and K, which allows for added flexibility. In addition. Tal & Vardy (2015) gave an efficient list-decoding algorithm for polar codes; this is useful for designing a multi-probe scheme for our algorithm. Thanks to their performance guarantees and ease of implementation, these codes have become prevalent in recent years (c.g., as part of the 5G cellular standards), and efficient implementations for polar codes exist in both hardware and software (Cassagne et al.] [019a] b). These properties prompted us to choose polar codes for similarity search. More details about polar codes and the (list)ddecdding process can be found in Appendix [A]
The PCNN Algorithm. To summarize, we describe the PCNN algorithm on a d-dimensional dataset D of n points. This algorithm is parameterized by the parameters cdim and nbii, as well as nprb (the number of clusters to probe upon query). The PCNN algorithm contains 2 main parts: (i) Initial- ization and preprocessing (Algorithm I for generating the index of the PCNN clustering method, and (ii) querying for the sizenn nearest neighbors to q within nprb clusters of focus (Algorithm 2 Figure I provides a visual illustration of the PCNN algorithm; for presentation purposes we depict the domm-dimesioona binary cube as a grid of 2adim points.
During initialization (see Algorithm 1. a code mask E {0, 1] 1j is generated, where ||r||| nbti, which represents the polar [cdim, nbit] -code to be used in the algorithm. This mask is generated through a genie-aided process (Arikan 2009). During the preprocessing of the dataset, we cluster the dataset points according to the nearest codeword to their binary embedding. Specifically, an empty partition M of the dataset points into 2nbbt clusters is created (where each cluster identifier is nbit-bit string). Then, each dataset point is embedded into odim-diieensionll binary space using odim
(or any other LSH function). Next, the function LISTDEC (see Algorithm 3 is called on the binary dataset point with the argument& E = 1, to obtain the single closest codeword to that binary point. (LISTDEC runs list decoding with slightly-larger list size l' > f, then takes the closest l codewords; see Appendix A for more details.) Since there are only 2nbit codewords, the algorithm extracts a nbit-bit cluster identifier a for e; this identifier is subset of bits from c, namely those bits whose indices get a value of 1 in the mask r (this identifier is unique; see Appendix AA.. The dataset point is then added to the cluster Ma in the partition M. The total running time of this preprocessing procedure is thus n (O(embedding cost) + O(diim log nbit)).
hyperplane LSH h Rd + {0, 1] j
Upon receiving a query (Algorithm [), the algorithm first retrieves nprb cluster IDs of focus, and then searches within for the sizenn nearest neighbors to q. Algorithm 2 embeds the query into cdim-dimensional binary space (using the same embedding h used in Algorithm D) then calls the function LISTDEC with the argument é = nprb to obtain the nprb closest codewords c", . to the binary dataset point. The cluster identifiers of these points are then extracted as before, which yields nprb clusters of focus in M to be probed. The algorithm then goes over all points in the chosen nprb clusters, calculates the distance of the query to each such dataset point in chosen cluster, and finds the closest sizenn points to the query. These distance com- parisons take place in the original real space for maximum accuracy (although quantization meth- ods, such as product quantization, could be applied as well). The running time for a query is thus Oeembedding cost) + O(prrb -diim- -log nbii) (plus, of course, the cost of the distance comparisons within each cluster).
Figure visualizes the process of extracting nprb 4 cluster IDs of nbit = 8 bits from a query in I The query is embedded to a binary space with cdim = 16, list-decoding with & = nprb = applied on the embedded vector, where cluster IDs are extracted according to a code mask r 0000001 100111111 (indicated by the red bits).
PCNN as Generalization of CHC. Note that PCNN is in fact generalization of CHC: choosing cdim nbit would imply C {0, 1) cdim
i..., every word is codeword. In addition, the cluster
5

---

Published as a conference paper at ICLR 2023
Algorithm PCNN:
Initialization and Prepro-
Algorithm PCNN: Upon Query
cessing
UPONQUERY(q, sizzen))
Parometers:
Let <- h(q).
nbit - the dimension of the hinary cluster identifier.
fget the closest nprb codewords to b.}
cdim the length of codeword. nprb the number clusters to probe upon query. INITIALIZATION:
Let c² ...., c...,,c.Pbb- -pb- Let S be an empty list of (distance, point) pairs.
LISTDEC(b, nprb).
for E (0..... nprr nprb 1] do
Denote c¹ (có. cmdm-1)
Generate polar code mask r E (0, 10.11 with exactly nbit 1-valued entries. Generate binary LSH embedding R {0, 1]
fextract the nbit-bit cluster identifier for cf.)
Let a + (c) j
for P Ma do
Set 6p d(q. Add (6p, P) to S.
Initialize the index M (Ma) (M, con- tain empty sets.
end for end for Choose and return the sizenn entries in S with the smallest distance.
PREPROCESSING(D)):
for P do
4 (p))
(get the closest codeword to b.]
Let
=
(co, Cod
Algorithm 3 PCNN: List Decoding Wrapper
LISTDEC(b, 1).
LISTDEC(b,
fextract the niit-bbt cluster identifier c.}
{ {This function returns the & closest codewords in C to b {0, ) (with high prohability). For more details, see Appendix A
Let a + (cs (
fadd the dataset point to the cluster.}
Add p to Ma
Define l" +- f(e) 2 L. for f as defined Ap- pendix A
end for
Use the list-decoding algorithm of Hashemi et al. (2016) on b with list size E' to obtain a set S of code- words, where
f".
Return the & nearest codewords to b in S.
0.52 -0.07 -0.1 0.13..13-.22 -0.25-00---00------ -0.57 0.39 0.00 -0.1
Query
Emibedding
List Desoding
11000100001100
Exahedded query
Cluster ID Extraction
00011110000000
21001010
101000000
11101000
1101011 10000010
11100020
1110010100000000
0100LOJ0
Nearost Codewords
Exctracted Closter
Figure 2: Obtaining cluster IDs by PCNN upon query.
ID of a codeword would be the entire codeword, and the closest codewords to a binary-embedded query q would exactly be those words generated by bit flips in the multi-probe scheme of CHC.
4 EXPERIMENTS
In this section, we empirically evaluate the PCNN algorithm.
4.1 DATASETS
We consider three representative real-world datasets for evaluation as follows 3
1. BIGANN: SIFT deseriptors applied to images (Dataset 2010).
The datasets and queries are taken from the Billion-Scale Approximate Nearest Neighhor Search Challenge in 21 (Competition 202T)

---

Published as a conference paper at ICLR 2023
Dataset Name
#Datasee/HQuery
Dim.
Distance
Normalized
YandexTTI
10M/5K
200
Cosine
Yes
YandexDeep
10M/5K
96
Euclidean
Yes
BIGANN
10M/5K
128
Euclidean
No
Table 1: Evaluation datasets: main characteristics.
2. Yandex-Deepl B (endexDeep)): image descriptor dataset consisting of the projected and normal-
ized outputs from the last fully-connected layer the GoogLeNet model (Babenko & Lempitsky
2016), which was pretrained on the Imagenet classification task (Babenko & Lempitsky] (2016).
3. Yandex Text-to-Image-IB IB YanddeXTT]) A cross cross-model dataset (text and visual) where the dataset consists of image embeddings and the queries are textual embeddings (Dataset 2021).
Table summarizzs the main characteristics of each dataset. All datasets consist of 10M points, and use 5K queries for evaluation. For YandexDeep and BIGANN we use Euclidean distance, while for YandexT7I we use cosine distance (Appendix C explores the effect of approximate cosine distance on cosine similarity).
4.2 EVALUATION METRICS
Upon a query for the sizenn nearest neighbors of some point g, an algorithm's 's output S consists of sizenn points in the dataset. Denote the distance function of the chosen dataset by d(:--), and define 6/ to be the distance of the i'th closest dataset point to For some approximation factor (When a is known, we 2 1, define the a-recall of the algorithm to be (r
sometimes refer to a-recall simply as recall.)
The measure we use for the cost of a query the number of distance calculations made by the algorithm, denoted by ndis. Indeed, since the algorithms we consider are clustering- their main cost comparing the query to the subset of the dataset the chosen clusters; the number of distance calculations captures this cost. In this work, we therefore measure the cost and performance of an algorithm by the pair (ndis, recall). Varying the number clusters probed by the algorithm, denoted nprb, controls this performance pair: increasing nprb would probe more points (increase ndis) but obtain better results (increase recall).
4.3 BASELINES
We compare PCNN to CHC for similarity search. Both clustering methods use an underlying LSH function; for our experiments, we use the classic hyperplane LSH, introduced by Charikar (2002). for both PCNN and CHC. Another choice of LSH is autoencoder LSH (Tissier et al.) 2019);; consider this data-dependent LSH in Appendix B.6 For the (randomly-chosen) hyperplane LSH, average over 30 different random seeds to reduce undue variance (see Appendix B.3 for more this variance).
Note that in our setting of ANNS, high recall on the evaluated datasets that contain 107 points is achieved by both PCNN and LSH using significantly less than / v distance computations; thus, k-means-based clustering methods (such as IndexIVFFlat in Faiss (Johnson et al. (021)) are not competitive this regime, as they require least /ID distance computations for dataset D.
4.4 EXPERIMENTAL RESULTS
Having described the main ingredients of our experiments, we describe the experiments themselves. Due to space constraints refer to Appendix B for further details some experimental results outlined herein. The outline of the performance gains of PCNN over CHC is the following. this section, we demonstrate the following results.
1. The performance PCNN improves as cdim grows, thus outperforming CHC (which is the special case of PCNN in which nbit cdim). The improvements plateau when cdim d.

---

Published as a conference paper at ICLR 2023
PCME oth
POWs
6.00
distancc comoutadions oer avory
dizznnce compurat ond per ouzry
distance compurations per currs
(a)
(b)
(c)
Figure 3: recall/ndis performance comparison for sizenn 1 (using nbit 28 and hyperplane
LSH) for three datasets: (a) YandexDeep, a 1.4; (b) BIGANN, 1.4; (c) YandexTTI, 0 2.
2. PCNN with large cdim and single table (ntable = 1) outperforms CHC with multiple tables (e.g., ntable = 8).
3. The performance gains of PCNN over CHC extend to binary datasets.
In addition, in Appendix B we establish the following useful robustness properties.
1. The performance gains hold for multiple choices of approximation factor and nearest neighbor size sizenn. (See Appendices [.I and [.2)
An efficient approximate hyperplane embedding, using random sign flips and Hadamard trans- form (Andoni et al. 2013), can be used for PCNN with negligible performance loss. (See Ap-
pendix(B.5])
3. The variance of PCNN performance curves upon different instantiations of binary embedding (by seeds) is lower than that of CHC. (See Appendix [B.3)
The superiority of PCNN over CHC remains when choosing the best trialed instantiation per operating point (i.c., performance of convex frontier). (See Appendix (B.4)
5. The performance gains PCNN over CHC extend to different LSH functions, specifically a
trainable autoencoder LSH of Tissier et al. (2019). (See Appendix [B6).
Performance Gains. With the hyperplane LSH Charikar (2002) as the underlying hashing method, we compared PCNN with various choices of cdim to CHC, over the three considered datasets; see Figure 3 Each curve in Figure 3 shows the average recall/ndis of an algorithm for focus
various choices of nprb, and averaged over 30 different random seeds. In this experiment, on sizenn = (i.e., single nearest neighbor). For the approximation ratio, we chose & = 1.4 for L2 datasets (BIGANN, YandexDeep) and 2 for the cosine-distance dataset (Yandex7TI). (Because cosine distance is proportional to L. squared, these approximation ratios are roughly equivalent.) As we later discuss, similar results are also obtained for different choices of a and sizenn.
Figure 3 shows marked improvement as cdim grows, which eventually plateaus at cdim 128 for BIGANN and YandexDeep, and at cdim = 256 for YandexT77. Since this seems to correspond to the real dimensionality of these datasets, we conjecture that choosing cdim to be roughly the dimension of the dataset is appropriate.
Multi-Table LSH. A common tool for increasing recall for CHC is using multiple tables, i.c., in- dexing the dataset according to ntable different binary embeddings of nbit bits, and probing clusters from all ntable resulting partitions upon query (Indyk & Motwani, 1998 Gionis al. 1999). This method comes with additional costs over standard (single-table) CHC, notably its increased memory and disk usage, increased running time, and the need for deduplication.
In Figure 4a we compare multi-table CHC to PCNN. Additionally, we consider multi-table PCNN, in which ntable difffrrnnt embeddings to cdim bits are used to create ntable tables (similar to CHC), to see if it offers improved performance over single-table PCNN. We consider the YandexDeep dataset, with sizenn = 1 and a = 1.4 (as before). All algorithms use nbit = 28, and their performance averaged over 30 different random seeds. It can be observed that single-table PCNN with cdim = 512 outperforms CHC with 8 tables; this is notable, PCNN uses an index which is 8 times smaller. addition, PCNN with cdim 512 does not benefit from additional tables. The fact that CHC improves with additional tables and PCNN does not might imply that the only benefit of multi-table CHC is in using additional embedding bits; this is the case, it could be supplanted by PCNN with single table and large-enough cdim.
8

---

Published as a conference paper at ICLR 2023
1.0
1.0
0.7
0.7
0.6
0.6
PCNN: ntable=], cdmm-52
0.5
PCWP: clmme322, maskee
0.5
Se: mahie1
FaissSi: nabie-?
0.4
LSI rtademm
0.4
mahieed
USe roaseew
FaissSit mabiee
Faiss.Sh SH: nabiem16
101 dislance compulation query
X2?
10t
10' dislance computations query
127
10f
(b)
Figure 4: Comparison of multiple table usage for sizenn = 1 and a = 1.4, using nbit = 28. (a) On YandexDeep, using hyperplane LSH. (b) on binary dataset obtained by embedding YandexDeep to binary space of dimension 512.
Binary Datasets. The PCNN algorithm can also operate on binary datasets (i.e., without need for binary embedding). To test PCNN on such dataset, we use hyperplane embedding on the YandexDeep dataset to create 512-dimensional binary dataset, then run PCNN and the baseline on this binary dataset. Note that this is different from the previous experiments, in which real dataset was embedded into binary by PCNN/CHC; indeed, in this experiment the distance comparisons of the algorithms, well as the ground truths for the queries, are all in the binary space. In binary datasets, the natural LSH technique is simply to take the first nbit bits of the dataset/query point as its hash-code; The IndexBinaryMulttin
(IBMH) class of Faiss (Johnson al. 2021 implements CHC using this LSH technique. Thus, we use IBMH as our baseline for binary datasets. IBMH also supports multiple tables, through using the ntable nbit first bits hash-codes for the ntable tables.
For binary datasets, we again find that PCNN outperforms CHC: datasets and show that single-table PCNN performs as well as CHC with multiple tables. To mitigate any effects from the (deterministic) choice of hash-code bits by IBMH, we again average our results over 30 different random seeds; here, the seeds are used for creating the dataset rather than by the algorithms. It can be observed in Figure 4b that single-table PCNN performs as well as IBMH with 16 tables. (Note that the vertices in the curves representing IBMH are sparse, the parameter controlling the number of probed clusters in IBMH is quite coarse.)
we replicate the results for real
5 CONCLUSIONS
In this paper, we addressed a problem in clustering methods for similarity search. Choosing the cluster centers to be unstructured, in k-means IVF, leads to high cost in finding clusters at query time. However, structured cluster centers, as used in CHC, are limited to low-dimensional embed- ded spaces, which distorts the metric space and hurts recall. We bridged the algorithmic gap in designing structured cluster centers in high-dimensional spaces using polar codes. These codes al- low for manageable number of clusters to exist in high-dimensional space, and provide efficient multi-probe through list decoding. Indeed, the ample previous work done on these codes for more classic applications (c.g., forward error correction communications) provides us with efficient list- decoding procedures, easily implementable in software or hardware. Through experiments, we' ve demonstrated the benefit of this high- nigh-diimnsional embedding space, establishing (in particular) that CHC with multiple tables is superseded by PCNN with a single table, saving memory and storage.
For future work, various refinements and generalizations of PCNN for similarity search could be considered. For example, one could use polar codes with different granularity (controlled by the parameter nbit while preserving the same cdim), such that areas in the embedded space which dense with the dataset would have a finer clustering. This refinement is motivated by mimicking unstructured clustering by hierarchies of structured clustering methods (Wang al. 2018).

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
We would like to thank Iftah Gamzu, Marina Haikin, Gal Levi, Alexander Lorbert and Uri Sharir for helpful discussions and feedback that helped improve the paper.
REFERENCES
Nir Ailon and Bernard Chazelle. The fast Wwchoson--innennnnn transform and approximate nearest neighbors. SIAM J. Comput., 39(1):002-322 2009.
Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, llya P Razenshteyn, and Ludwig Schmidt. Practical and optimal LSH for angular distance. In Annual Conference on Neural Information Processing Systems (NeurIPS'I5) 15), pp. 1225-1233, 2015.
Erdal Arikan. Channel polarization: a method for constructing capacity-achieving codes for sym- metric binary-input memoryless channels. IEEE Trans. Inf. Theory, 55(7):3051-30733 2009.
Martin Aumüller, Erik Bernhadssoon, and Alexander Faithfull. ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems, 87, 2020.
Artem Babenko and Victor Lempitsky. Efficient indexing of billion-scale datasets of deep descrip- tors. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2055- 2063, 2016.
Elwyn R. Berlekamp, Robert J. McEliece, and Henk C. A. van Tilborg. On the inherent intractability of certain coding problems (corresp.). IEEE Transactions on Information Theory, 24(3):384-36,, 1978.
A. Cassagne, O. Hartmann, M. Léonardon, K. He, C. Leroux, R. Tajan, O. Aumage, D. Barthou, T. Tonnellier, V. Pignoly, B. Le Gal, and C. Jégo. AFF3CT: A Fast Forward Error Correction Toolbox! Elsevier SoftwareX, 10, 2019a. doi:
A. Cassagne, O. Hartmann, M. Léonardon, K. He, C. Leroux, R. Tajan, O. Aumage, D. Barthou, T. Tonnellier, V. Pignoly, B. Le Gal, and C. Jégo. Aff3ct: A fast forward error correction toolbox! Elsevier SoftwareX, 10:100345, October 2019b. ISSN 2352-7110. doi: https://doi.
2019. 100345. URL http://wwwwwccceeeceeeeee..tt wtt.e//co.cceeeneeeeeeeeeeeeeeee
atticleepp1//2255711119000
Moses S Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing (STOC'02), STOC '02, pp- 380-388, New York, NY, USA, 2002. Association for Computing Machinery.
Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zhiyong Zheng, Mao Yang, and Jingdong Wang. SPANN: Highly billion-scale scale approximate nearest neighborhood search. In Annual Conference on Neural Information Processing Systems (Neur volume 34, 2021.
NeurlPS Competition. Billion-Scale ANNS Benchmarks. https://big ann http:/bii-aan---beehhmheett ben.hmarcc.h....eee
com/ 2021. Accessed: 2022-09-27.
Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós. Fast locality-sensitivy hashing. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD' pp. 1073-1081, 2011.
Sanjoy Dasgupta, Charles F. Stevens, and Saket Navlakha. A neural algorithm for fundamental computing problem. Science, 358(6364);733-796 2017.
SIFT Dataset. Datasets for approximate nearest neighbor search. lttp://corpus-texiee.
Tris sa. fr/, 2010. Accessed: 2022-09-27.
Yandex TTI Dataset. Benchmarks for billion-scale similarity search. attps://research 2021. URL Tttts::/resaarc..ancc... com/
datasets/biganns Accessed: 2022-09-27.
10

---

Published as a conference paper at ICLR 2023
Yihe Dong, Piotr Indyk, Ilya P. Razenshteyn, and Tal Wagner. Learning space partitions for nearest neighbor search. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https: //tpp//eepee....e/////
net feot/forum? dd=
Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the navigating spreading-out graph. Proc. VLDB Endow., (2(5):461-474 Jan. 2019.
Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity search in high dimensions via hash- ing. In 25th International Conference Very Large Data Bases (VLDB (99),, volume 99, pp- 518-529, 1999.
Seyyed Ali Hashemi, Carlo Condo, and Warren J. Gross. Simplified peccessive-cancellttion list decoding of polar codes. 2016 IEEE International Symposium on Information Theory (ISIT), pp. 815-819. IEEE, 2016.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing (STOC'98), pp. 604-613, 1998.
Omid Jafari, Preeti Maurya, Parth Nagarkar, Khandker Mushfiqul Islam, and Chidambaram Crushev. A survey on locality sensitive hashing algorithms and their applications. CoRR, abs/2102.08942, 2021.
Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. DiskANN: Fast accurate billion-point nearest neighbor search on a single node. In Annual Conference on Neural Information Processing Systems (NeurIPS' 19), volume 32, pp. 1377 1-3781,, 2019.
Jeff Johnson, Matthijs Douze, and Hervé Jégou, Billion-scale similarity search with GPUs. JEEE Transactions Big Data, 7(3):535-547, 2021.
Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD '1, pp. 489-504, 2018
Thijs Laarhoven. Hypercube L.S for approximate near neighbors. In 42nd International Symposium on Mathematical Foundations of Computer Science MFCS' 17, volume 83 of LIPIcs, pp. 7:1-7:20, 2017.
Wen Li, Ying Zhang, Yifang Sun, Wei Wang. Mingjic Li, Wenjie Zhang, and Xuemin Lin. Approx- imate nearest neighbor search on high dimensional data experiments, analyses, and improve- ment. IEEE Transactions on Knowledge and Data Engineering, 32(3):1455-1488 2020.
Qin Lv. William Josephson, Zhe Wang, Moses Charikar, and Kai Li. Multi-probe LSH: efficient indexing for nigh-dimensional similarity search. In 33rd International Conference on Very Large Data Bases (VLDB' 07), pp. 950-966 (00-961,222 2007.
Yury Malkov, Alexander Ponomarenko. Andrey Logvinow, and Vladimir Krylov. Scalable dis- tributed algorithm for approximate nearest neighbor search problem in high dimensional general metric spaces. In Similarity Search and Applications (SISAP' 12), volume 7404 of LNCS, pp-
142,147,90 2012.
Yury Malkov, Alexander Ponomarenko. Andrey Logvinov, and Vladimir Krylov. Approximate near- est neighbor algorithm based on navigable small world graphs. Information Systems, 45:61-68, 2014.
Yury A. Malkov and Dmitry A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4):824-83) 836, 2020.
Kai Niu and Kai Chen. CRC-aided decoding of polar codes. IEEE Communications Letters, 16(10): 1668-1671, 2012.
11

---

Published as a conference paper at ICLR 2023
Tom Richardson and Ruediger Urbanke. Modern coding theory. Cambridge university press, 2008.
Chaitanya Ryali, John Hopfield, Leopold Grinberg, and Dmitry Krotov. Bio-inspired hashing for unsupervised similarity search. In Proceedings of the 37th International Conference on Machine Learning (ICML'20), volume 119 of Proceedings of Machine Learning Research, pp. 1295-83305 2020.
Hamid Saber and lan Marsland. An incremental redundancy hybrid ARQ scheme via puncturing and extending of polar codes. IEEE Transactions on Communications, 63(11):3964-3973, 2015.
Jaiyam Sharma and Saket Navlakha. Improving similarity search with high-dimensional locality- sensitive hashing. CoRR,
2018.
Sivic and Zisserman. Video Google: a text retrieval approach to object matching in videos. In Proceedings Ninth IEEE International Conference on Computer Vision (ICCV'03), pp. 1470- 1477 vol.2, 2003.
Ido Tal and Alexander Vardy. List decoding of polar codes. IEEE Transactions Information Theory, 61(5):2213-2225 2015.
Kengo Terasawa and Yuzuru Tanaka. Spherical LSH for approximate nearest neighbor search on unit hypersphere. In Algorithms and Data Structures, 10th International Workshop WADS'07, volume 4619 of Lecture Notes in Computer Science, pp. 27-38. Springer, 2007.
Julien Tissier, Christophe Gravier, and Amaury Habrard. Near-lossless binarization of word embed- dings. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI' 33(01):7104- 7111, Jul. 2019.
Jingdong Wang, Heng Tao Shen, Jingkuan Song, and Jianqiu Ji. Hashing for similarity search: A survey. CoRR, 110111408.222222 2014.
Jingdong Wang, Ting Zhang, jingkuan song, Nicu Sebe, and Heng Tao Shen. A survey on learning to hash. IEEE Transactions on Puttern Analysis and Machine Intelligence, 40(4):769-790, 2018.
Runxin Wang and Rongke Liu. A novel puncturing scheme for polar codes. IEEE Communications Letters, 18(12):0081-208 2014.
Liang Zhang, Zhaoyang Zhang, Xianbin Wang, Qilian Yu, and Yan Chen. On the puncturing patterns for punctured polar codes. In 20/4 IEEE International Symposium on Information Theory (ISIT),
pp. 121-125, 2014.
A POLAR CODES AND LIST-DECODING
This section explains the decoding process used in PCNN in more detail, and also provides a gentle introduction to polar codes.
Simple Introduction to Polar Codes. We now describe polar codes and their decoding pro- cess. For ease of introduction we assume that the code dimension cdim = 2 for some inte- ger t, though this can be relaxed to any code dimension using code shortening/puncturing tech- niques (see, e.g., Zhang et al. (0014;; Wang & Liu (2014;; Saber & Marsland (2015): Niu & Chen 2012)). A polar code of rate (cdim, nbit) defined by mask r (ro. Pedim ). which is cdim-dimensional binary vector in which exactly nbit entries equal 1. To encode a message word
(ma,... mmbit-1) of nbit bits, one performs the following actions:
1. Create the binary pre-coded word e = (Co. ... 1), such that
T
C;
my i is the j nonzero coordinate in
2. Apply the polar transform to obtain the codeword c (Co, **. Codim-1) 1).
12

---

Published as a conference paper at ICLR 2023
codeword
message
Figure 5: Illustration of the decoding tree for polar code.
The polar transform f {0, 1] odim + {0. 1) cdim in the above process can be described succinetly in
the following way: if = f(e) where for every index E [cdim]. let = (503) 32... .r-1) be the
binary representation of i. Define L(i) == {1 }} (the bits in i's representation which are equal to 1). The polar transform is defined such that
ej-
(TGG)M)))
The above encoding process maps a nnbi-bbit message word into a cdim-bit code word, and can be shown to be linear. Thus, the image C' of this encoding is a innit-diiensaee sott-dmmensioal subspace of {0, 1) adim
Code Mask Generation. The correct choice of mask r is crucial for the error-correctigg properties of the polar code. good mask depends on the structure of the noise one aims to correct using the code. To generate a mask, use an iterative process called genie-aided generation (Arikan) 2009): in this process, one subjects a codeword to the expected noise channel and studies which indices would be best for placing data bits (and which indices should be frozen). Since the points aim to decode using PCNN are given in binary form, we chose to generate our masks using noise from Binary Symmetric Channel (BSC), i.e., random bit flips.
The process for generating a mask for pair (cdim, nbit) is only performed once, and is quite cheap computationally (in our case, involves decoding se 10" points). Moreover, since the mask is data- independent, masks can be reused globally across projects.
(List) Decoding. Together with the introduction of polar codes, Arikan (2009) introduced the first decoding algorithm for polar codes, based successive cancelation (SC). This algorithm is very efficient, and runs time (cdim log cdim), i.e., nearly linear the dimension of the codeword.
Tal & Vardy (2015) gave the first list-decoding algorithm, which returns nprb candidates for the closest codewords the query, with time complexity O(nprb cdim log cdim) (i.e., the list size contributes linearly to running time). This list-decoding algorithm was made more computationally efficient by Hashemi et al. (2016). through pruning branches in the decoding tree; this algorithm achieves an improved decoding complexity of O(prrb cdim log nbit). This improved algorithm the algorithm we use for PCNN. In our implementation, we use heavily-modified the wrthon-polar-coding library der the MIT license.
modified version of htwp://wwwwwellloooooooolloaraaa polar- polar-coding), distributed un-
To give some intuition for these decoding algorithms. Figure shows the binary decoding tree used for encoding and decoding polar code in which cdim 16 and nbit 8. The leaves of the tree represent the precoded word, where leaves corresponding to frozen coordinates in blue contain zeros and the remaining (unfrozen) leaves contain message bits. Each leaf in this tree contains one
13

---

Published as a conference paper at ICLR 2023
message bit, except for the blue coordinates which are frozen (i.e., the mask value there is 0) and thus contain zeros. The root of this tree contains cdim bits, and represents the codeword. Each the 2(logcdim) cdim) internal nodes of height h in this tree contains an array of 2 bits, which calculated from the arrays of its two children. Roughly speaking, the SC decoding algorithm of[Arikan| (2009) performs a DFS traversal of this tree, filling all bit arrays. The time complexity determined by the number of bits in those arrays, which is (cdim log cdim). The list decoding algorithm of Tal & Vardy (2015) also performs a DFS traversal of this tree, but maintains the nprb best results seen so far, which costs time (nprr cdim log cdim). Finally, the simplified list decoding algorithm of (Hashemi et al. (011)) prunes those nodes in the tree whose leaves are either all frozen or all unfrozer the remaining nodes are inside the gray outline. Note that for low-rate codes (i.e., nbit << cdim) such as those used in PCNN, pruning such nodes yields a significant performance gain.
Note that these decoding and list-decoding algorithms are not exact, and sometimes return subopti- mal results. However, we mitigate this in PCNN by increasing the list size of the algorithm beyond the desired list size. That is, to obtain the closest nprb codewords, we would use the algorithm of Hashemi et al. (2016) with list size ((pprb)= 2 nprb, and only take the nprb best results. We have empirically found the following rule to nearly perfectly recover the closest codewords to the query:
16
nprb 1
32
nprb S 16
((prrb =
2nprb
16 < nprb S 256
nprb
nprb >> 256
This rule is thus used in PCNN.
Extraction of Cluster IDs. In PCNN, after list-decoding a dataset point (during index creation) or a query (upon receiving one), we obtain the nprb closest codewords, each representing cluster. While we could use the codewords themselves as cluster identifiers, this would be inefficient in terms of memory and storage, as each codeword has cdim bits and there are only 2nbil such codewords. Instead, we would like to extract from each codeword a niit-bit cluster identifier which identifies the codeword uniquely. Given a codeword c = (Co. , Codim), we extract the nbit-bit cluster identifier xcc) through applying the code mask r to
x<c) == (c))
We provide proof that these identifiers are indeed unique.
Proposition 1. Let C be [cdim, nbil) polar code, be its mask, and let x be defined as in Equa- tion Let C1, C2 E C' be two codewords. Then,
= = x(c;)=x((s) x((2)
Proof. The left-implies-righh direction is trivial (the cluster ID of codeword is contained in the codeword), it remains to show the other direction. Assume that C₁ * C2. Since the encoding process of polar code, as given in Equation ( injective, the distinct codewords C₁ C2 were generated from two distinct nbit-bit message words m, (ml. ... , .mint) and m2 (mā- Moreover, each bit in each codeword a linear combination (i.e., xor) of some subset of its message word. Denoting by ff the encoding, and defining a := a<(c)) and a s(C²), it holds that a1, a2 are created from my, my through the linear transform o f.
m
we show that the linear map g == x oo f is injective, the proof is complete, as
C1 + C2 = mi * m = a # a2
Claim:
The linear map g is injective.
We prove this claim through claiming that the image of g (denoted im(g)), which is contained in {0, 1)* kt has full dimension (i.e., equal nbii). Indeed, this is not the case, then the perpendicular
Moor accurately, the list-decoding algorithm of Hashemi et al. 2016) also prunes nodes with only single unfrozen leaf (repetition nodes).
14

---

Published as a conference paper at ICLR 2023
1.0
0.8
recall
0.6
FCNN cam-5522. 2-12
PCNK clm=551. 2514 2:14 PCNN 6-1-512.==16
0.4
LSH. 8-16
0.3
PCNN 0-2--
LSH a=2.0
02
distance computations per query
Figure 6: Comparison of PCNN and LSH for varying Approximation Factor 1.4, on YandexDeep dataset (with sizenn = 1, using nbit 28 and hyperplane LSH).
space im(g)* contains nonzero word - equivalently, there exists subset * S [ [nbit] such that
v (Ao, (nbit-1) im(g) a2 0.
Suppose, for contradiction, that there exists such a nonempty set S. Now, for every j E [nbit) define ł to be the j'th one-valued bit in the mask
For an index i [odim], denote by L(i) the of one-valued bits in i's binary representation (as in the definition of polar codes in Equation (T).
Now, fix S to be some index such that its location in the codeword is minimal according to L, i.e., Vjí E (V)) L(i,) & ). Now, from the definition of S, it must be that c; = ① )'ES( G However, recalling that for every index it holds that c; DVILOSL(Y) ev, we have that ei, goes into the xor of Ct, but not into the xor of c2 for any j' E S (this uses the minimality w.r.t. L). But since ei, can take both zero and one, Equation cannot hold for every cluster ID a. This completes the proof.
B ADDITIONAL EXPERIMENTS
B. CHOICE OF APPROXIMATION FACTOR
The performance gains present for any choice of approximation factor a. In Figure 6 PCNN (solid curves) and LSH (dashed curves) are compared on YandexDeep dataset for a E (1.2, 1.6, 2.0). observed that PCNN outperforms LSH on every choice of approximation factor a.
B.2 CHOICE OF NEAREST NEIGHIBR SIZE
The performance gains are consistent for multiple choices of sizenn, the number nearest- neighbors output. Figure comparison between PCNN (solid curves) and LSH (dashed curves) on YandexDeep dataset for sizenn E 51,1 It is observed that PCNN outperforms LSH for any choice of sizenn.
B.3 ROBUSTNESS TO EMBEDDING RANDOMNESS
The performance of LSH can be greatly impacted by the choice of random embedding. We jecture that this is due to the low number of embedding bits; thus, reasonable to assume that this variance in performance would be lower for PCNN, it uses more embedding bits. To test
15

---

Published as a conference paper at ICLR 2023
1.0
0.8
recall
0.6
cdim=512, LSHt size mn-1
0.4
PCNN cdim-512, re-10
0.3
PCNN. cdim-512, size, mo-50
LSH: size ma-50
distance computations per query
Figure 7: Comparison of PCNN and LSH for varying Number of Neighbors sizenn E {1, 10) on YandexDeep (with a = 1.4, using nbit = 28 and hyperplane LSH).
SP at 61
probing parameter Hlg
(b)
Figure 8: Variance comparison for 30 different random seeds on YandexDeep (with sizenn 1,a 1.4 and using nbit 28 and hyperplane I.SH) for (a) CHC, (b) PCNN with cdim 1024. Sub- Figure (c) shows the standard deviations from (a) and (b) per choice of nprb.
this conjecture, we ran both LSH and PCNN with 30 different random seeds. We considered the YandexDeep dataset, sizenn 1 and 1.4, and ran both LSH and PCNN with nbit 28. For PCNN, we chose cdim 1024. The resulting measurement can be seen in Figure 8 Figures Sa and [b] show the performance for LSH and PCNN respectively, while Figure [c) shows the standard deviations of both algorithms for every choice of nprb. A reduced variance in the performance of PCNN versus LSH is clearly observed.
B.4 CONVEX FRONTIER
Our previous experiments averaged performance over the random seed of the algorithm. In standard usage, where one chooses an arbitrary random seed, this method seems reasonable. However, one could imagine trying optimize for the best random seed (which, mentioned above, would greatly impact the performance of CHC). A natural question would be whether the higher variance of CHC compared to PCNN would make the best seed choice for CHC better than the best seed choice for PCNN. We answer this in the negative: PCNN still outperforms CHC in this case.
To consider this seed-optimization regime, we repeat previous experiments where instead of averag- ing over seeds, we take only the vertices of the convex hull of the algorithm's results (over all seeds). We then prune the vertex set by taking its Pareto frontier (i.e., subset of points such that point in the subset is worse in both recall and ndis than another vertex). Figure 9 shoows the choice of this convex frontier from the runs of an algorithm with 30 different seeds (in this figure, the frontier is dominated by a single seed, but this need not always be the case). Figure compares the convex frontiers of the various algorithms.
16

---

Published as a conference paper at ICLR 2023
1.0
0.8
recall
0.6
0.4
0.3
02
distance computations per query
Figure 9: Illustration of a convex frontier of CHC (solid blue curve) that corresponds to 30 curves (dashed yellow curves) obtained by using different seeds as used in the case of Figure Sa
100
recall
PCMN: cdim-12
KNN:: rlables1 wim=5112
PCNN: udnm66
3.5
cdim=128
LSH mtable=1
FCN: cdmm-256
0.0
3.8
1SH: itable=2
PCNN: cdim-512
1SMt. ntablees
3.4
cdim=1024
1SHt maable-8
LS4
107
127
distance computations per query
computations per query
(a)
(b)
Figure 10: Reproducing the results of Figures 3a and 4a using convex-frontier instead of seed aver- aging.
B.5 APPROXIMATE HYPERPLANE LSH
As previously stated, the results above regarding the choice of cdim seem to indicate that should be roughly on par with the original real dimension d. However, in hyperplane LSH choosing cdim implies multiplication by a x d matrix with normally-distribne which would take (dd)) time. However, there exists an efficient alternative for this multiplication; this alternative involves repeatedly flipping entry signs at random, then applying Hadamard trans- form. After a constant number of iterations, this process has been seen approximate the original matrix multiplication, while taking only O(d d) time (Andoni et al. 2015). (Such approximate transform of Ailon Chazelle (0009), and
entries upon embedding vector,
embeddings are based on the fast Sechnnsnn-Lnndrrsfin were also considered by, e.g., Dasgupta et al. (201T).)
We test this method for PCNN, and observe that 4 iterations of this process (sign flip + Hadamard transform) are sufficient for identical performance to hyperplane LSH. Figure []] shows the results of this experiment.
17

---

Published as a conference paper at ICLR 2023
1.0
0.8
recall
0.6
0.5
0.4
PCNY emb classchp, cdim=512
PCNV emb classeshpp emb, (tt.-ttrss.... c1im=
classsssssspp emb c1m
0.3
PCNY emb clasamahp, emb jters-s, cdim=512
-3-- LSH emb classhhp
102
distance computations per query
Figure 11: Comparison of PCNN with hyperplane embedding Hadamard- embedding (with hyperplane LSH for comparison). The dataset is YandexDeep, with sizenn = and a = 1.4.
B.6 AUTOENCODER LSH
PCNN general method which can encapsulate any LSH function to obtain an algorithm for nearest-neighbor search. Thus far, we have focused on hyperplane LSH as concrete, classic ex- ample for such an LSH function. However, other LSH functions can also used by PCNN; this subsection focuses exploring one such LSH function, namely the data-dependent autoencoder LSH introduced by Tissier al. (2019).
In this subsection, we explore the performance gains of PCNN over CHC, where both techniques encapsulate the autoencoder LSH method. We implemented the autoencoder architecture of Tissier ett al. (2019) in pytorch lightning, and trained it on the YandexDeep dataset. For this, we used regularization parameter Xreg (as defined by Tissier et al. (2019). and ran the Adam optimizer with a learning rate of 0.001 and a batch size of 128. For every value of cdim, we trained an autoencoder in this way which has representation layer of size cdim.
First, we compare CHC with PCNN with various choices of cdim; we do this for the YandexDeep dataset, similar presented performance gains in Section 4.4 for hyperplane LSH. The choice of problem parameters the same as for hyperplane LSH, i.e., sizenn = and a = 1.4, as is the parameter nbit 28. The results, given in Fig. 12 show a dramatic difference. This is since a larger representation allows for a better autoencoder, and PCNN provides access to these larger representations.
Next, repeat the experiment of Section 4.4 for Multi-Table LSH with autoencoder L.H.. This experiment is again on the YandexDeep dataset, with problem parameters sizenn = 1 and a = 1.4, as well as nbit 28. The results are given in Fig. [3 and show similar results to those seen for hyperplane LSH. The main difference is that using multiple tables improves the performance of PCNN even in large cdim (i.e., 512); we attribute this to the slower plateau of performance w.r.t. cdim that the autoencoder LSH exhibits in comparison to hyperplane LSH.
C APPROXIMATION FACTOR FOR COSINE SIMILARITY
In the case of YandexTTI dataset we use cosine distance, defined as one minus the cosine similar- ity. While maximizing cosine similarity and minimizing cosine distance are equivalent, using an approximation factor for cosine distance could yield little intuition regarding the minimal value of the corresponding cosine similarity. This due to the fact that when emanating from approximation factor 1 defined for cosine distance, the corresponding approximation factor for cosine similar- ity does not remain constant and depend on the value the reference cosine similarity. Formally, let ed, and cd2 denote similarities, respectively. holds that cd2 & a - edj and only if cs2 2 (a - (a - 1)/cs1) css- 2 the effect of choosing different a for different cosine similarity values. The values in
cosine distances, and let CS1 and cs2 denote the corresponding cosine
18

---

Published as a conference paper at ICLR 2023
1.0
PCNN: cdim=32
PCNN: cdim-128
PCNN: cdim=256
0.8
cdim-512
PCNN: cdim-1024
0.7
LSH
recall
0.5
0.4
0.2
10'
10a
10*
distance computations per query
Figure 12: recall/ndis performance comparison for sizenn 1, = 1.4 for YandexDeep (using
nbit and autoencoder LSH)..
1.0
0.9
0.8
0.7
recall
0.5
PCVN: ntable-1, cdim-512
0.4
PCNN: ntable-2 cdin-512
stable=1
LSH: mable=2
0.3
LSft: mablend
stable-8
0.2
102
10a
10"
distance computations per query
Figure 13: recall/ndis performance comparison for sizenn 1, 1.4 for YandexDeep (using
nbit = and autoencoder LSH).
the left column correspond to values of cs1 (e.g., reference cosine similarity values) while the values in the body of the table correspond values cs2 (minimum allowed cosine similarity value by approximation ratio) with different a per column. For example, if the optimal reference cosine sim- ilarity equals 0.97, than approximation factor similarity of at least 0.955 is valid (that is, an effective approximation ratio of 0.984 w.r.t cosine similarity).
1.5 for cosine distance implies that any cosine
Table 2: Examples of changes to cosine similarity through approximation factor a for cosine dis- tance.
1.2
1.5
2.0
2.5
3.0
CS1
0.7
0.64
0.55
0.4
0.25
0.1
0.8
0.76
0.7
0.6
0.5
0.4
0.9
0.88
0.85
0.8
0.75
0.95
0.94
0.925
0.9
0.875
0.85
0.97
0.964
0.955
0.94
0.925
0.91
19

---

Published as a conference paper at ICLR 2023
D COMPLEXITY DISCUSSION
Time complexity of PCNN versus CHC. both the hyperplane and autoencoder LSH methods with nbit-bit hashcodes, CHC would have preprocessing time complexity of n. Oembbedding cost + nbit) and query complexity of Ofembedding cost + nprb nbit). (Not in- cluded in this is the cost of training the autoencoder model, which varies depending on the training parameters.) In order to compare PCNN to CHC, we must pick a regime for cdim; for hyperplane LSH, for example, our experiments show that picking cdim x d optimizes performance, and thus in the following comparison we assume cdim = d. In addition, we should consider the cost of binary embedding: embedding to dimension of doin takes ((dbin -d) time in standard hyperplane embed- ding. We also consider the complexity of an approximate embedding based on Hadamard transform and random sign flips, identical to that in Andoni et al. (2015); this approximate embedding takes O(dsin + d) log( doin + d)) time.
Table summarrizs the running time complexities of both PCNN and CHC. Overall, for both PCNN and CHC, the cluster ID extraction upon query is not significant terms of running time; in both cases, the determining component in rumning time is the distance comparisons between the query and the dataset points (ndis, as defined in Section 4.2
Table 3: Comparison of the time complexity of PCNN and CHC. Time complexity is compared for preprocessing and for extraction of nprb cluster IDs (CIDs) probe upon a query. (Note that this table does not refer to the main cost of querying, which is searching within clusters; this is evaluated empirically in Section
without embedding
hyperplane embed- ding
w.
w. approx. embedking
PCNN
preprocess
O(n d log d)
O(n d²)
O(n d log d)
extract CIDs
O(nprb d log
Old nprb d log d)
Onprb log d)
preprocess
O O[prrb nbit)
O(n d nbit)
O(n d log
CHC
extract CIDs
Old nbbt nprb nbit)
O log d nprb nbit)
20


Reviews:
[{"review_id": "n9DeAWRx1gc", "reviewer": "Reviewer_96rD", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "summary_of_the_review": "It's an interesting idea, but its validation is not convincing.", "strength_and_weaknesses": "The paper does not prove any rigorous guarantees or bounds on the proposed scheme. It's validated solely empirically.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "g5iIL2A9CKo", "reviewer": "Reviewer_8eNv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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).\n", "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.  ", "strength_and_weaknesses": "The paper has the following strengths:\n\nS1. 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. \n\nS2. 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.\n\nThe paper has the following weaknesses:\n\nW1. 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.\n\nW2. 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?\n\nW3. 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}.\n\nW4. 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?\n\nW5. 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.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ciSuaQ-zmA", "reviewer": "Reviewer_FYov", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Takes the idea of polar codes (and polar coding) to develop an approximate nearest neighbour scheme with some efficiency.\nInvestigates the application of that to search in three databases - all three containing SIFT visual descriptors but one containing text as well.\nThe 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). \nThis 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.", "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.", "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.\n\nAs 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.\n\nThe 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.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "KmhQi-RZGSG", "reviewer": "Reviewer_sMa7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.\n\nQuestions\n1. 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?\n\n2. Is it possible to provide theoretical guarantees on the clustering quality of PCNN?\n\n3. 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\n\n4. Can we provide privacy guarantees for PCNN?", "strength_and_weaknesses": "Strength:\n1. The combination of LSH and error-correction code is novel. \n\n2. This paper is well-organized. Figure 1 is illustrative for readers to understand the functionality of PCNN\n\n3. Large ANNS datasets are used for empirical evaluation, making a fair comparison of PCNN with LSH\n\nWeakness:\n1. Stronger arguments is required for the motivation of applying  error-correction code in ANNS.\n\n2. In the evaluation, the comparison of PCNN with product quantization approaches is missing.\n\n3. For binary datasets, MinHash algorithms should also be considered as a baseline.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster