Random Cycle Coding: Lossless Compression of Cluster Assignments via Bits-Back Coding

Summary

This paper proposes the random cycle coding that achieves optimal rate by bits-back coding techniques for cluster assignments. In addition, the newly proposed algorithm requires less computing resources, making it more practical.

Strengths

For the cluster assignments, this paper proposes an optimal compression coding by bits-back coding techniques. In the coding view, the result is significant due to the optimal property. The RCC algorithm needs less computing and memory costs, making it more practical.

Weaknesses

This paper borrows bits-back coding techniques and random order coding, making this paper quite incremental in the view of techniques. The difficulty in combing these two techniques is not clearly presented.

Questions

This paper stresses the application in cluster assignments. Is there any other potential application? What is the special feature in cluster assignment that is compatible with RCC?

Rating

5

Confidence

2

Soundness

3

Presentation

3

Contribution

2

Limitations

No. The limitations are not discussed explicitly.

Summary

## Summary * This paper propose an entropy coding technique named RCC, which is the first one to achieve the optimal rate for cluster assignment. Theoretical and empirical results show that the rate saving and speed up of the proposed approach over previous suboptimal work ROC is evident when the number of cluster is close to sample size.

Strengths

## Strength * The paper presents a entropy coding technique that achieve optimal rate for cluster assignment, which is a step forward the previous work on multiset.

Weaknesses

## Weakness * Despite its theoretical optimality, the bitrate saving of RCC over ROC is a bit of marginal, especially when the number of clusters are not so large compared with number of elements. For a less extreme case when number of cluster is much smaller than number of elements (~\sqrt{n}), the difference between RCC and ROC can be quite small. (See Fig 3, n=10^7, cluster = 10^7 and cluster = 10^3.5). * Similarly, the RCC approach has obviously better complexity compared with ROC, only when we have number of clusters close to number of samples. For the case when #cluster ~\sqrt{n}, the difference of temporal complexity can be less significant.

Questions

## Questions * What is the common practical #clusters compared with #samples? Is that common to have #clusters close to #samples?

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes

Summary

This paper study the problem of cluster assignments of datasets, the goal of which is encoding datasets along with their cluster information. The authors propose Random Cycle Coding method that utilizes cycle representation of permutation as indicators for cluster. The cycle is formed by a sequence of numbers and it represents a cluster of the data samples corresponding to the numbers in the cycle. It is shown that the method outperforms other baseline methods while requires less computational complexity and memory.

Strengths

The idea in employing the cycle representation of permutation to assign data to cluster is simple yet effective. The authors formalize the idea and show the effectiveness of their proposed method. The performance of the method is consistently outperforming others.

Weaknesses

Although the main idea is simple to understand, it is quite hard to grasp the underlying techniques like ANS, ROC and bit-back coding from the paper. This paper compares their method only with ROC, which I think is not sufficient.

Questions

1. What are the differences between RCC and ROC in cluster assignment problem? From my understanding, RCC stores cluster information by permutation. Then, how ROC-1 and ROC-2 store the clusterings? 2. Is ROC only existing baseline method? 3. To leveraging permutation, it seems sequential stacking is required, and parallel stacking or decoding is not allowed. If it is, are there any problems or disadvantages caused by not using parallel operations? 4. When extremely many data samples are stored, it seems that retrieving a cluster information for a data sample requires decoding every data sample if the sample is stacked first. Is this correct?

Rating

6

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

N/A

Summary

This paper proposes a coding scheme for lossless compression of cluster assignments. The proposed coding scheme is based on random order coding (ROC) with bits-back coding. Analysis and experiments show that it outperforms two variants of ROC in complexity and compression rate.

Strengths

The presentation and research methodology presented in this paper are good, and a comparison with baseline methods is included. Examples are provided for clear explanation.

Weaknesses

After carefully reading this work, I believe it is out of the scope of NeurIPS. This work applies the Random Order Coding (ROC) with bits-back coding for encoding clustering assignments. The main contribution is on the way to adapt the ROC to clustering assignment encoding, which does not include any discussion or consideration on the topics listed on NeurIPS 2024 Call For Paper. Additionally, the paper does not provide any literature on clustering assignment compression. I am not a database researcher, but is the clustering assignment a significant overhead in practice? According to the author, "the number of bits used to store the vector embedding ranges from 4 to 16 bytes, while ids are typically stored as 8-byte integers" It is very unexpected that, in practice, the id takes up more than half of the storage. Could the author provide more references or elaborate more on this?

Questions

See weakness

Rating

5

Confidence

3

Soundness

2

Presentation

2

Contribution

1

Limitations

See weakness

Summary

The paper introduces Random Cycle Coding (RCC), a method for lossless compression of cluster assignments in data sets. RCC encodes data sequentially, representing cluster assignments as cycles in permutations, which eliminates the need for artificial labels. The method is shown to achieve the Shannon bound in bit savings, and scales quasi-linearly with the largest cluster size. Empirical results show optimal byte savings across a range of cluster sizes for multiple datasets.

Strengths

1. The proposed algorithm for encoding cluster assignments is novel and elegantly leverages the properties of clusterings and permutations to achieve theoretically optimal compression. 2. The approach also shows significant savings in experiments including on vector databases which can translate into gains across all machine learning approaches that rely on retrieval from vector databases.

Weaknesses

Some of the technical details are not clearly explained (see question below) and overall, the details of the approach may be difficult to follow for audiences not familiar with the relevant source coding literature. I would recommend adding an example to illustrate how Algorithm 1 works end-to-end and why it works, either in the main paper or in the appendix, to remedy this.

Questions

1. Why does the encode + decode time for RCC in Fig. 2 decrease as 'k' increases? 2. If the elements in each cycle are sorted (line 188) then how can the original order of the elements be recovered? If it cannot be recovered, then is this approach only limited to settings where the ordering of database elements is not important? 3. How is the centroid to cluster mapping information stored? I believe it will be needed to identify the clusters in which to search for the k nearest neighbors in the second stage of FAISS right?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Response to rebuttal

Thank you for addressing my concerns. As I had already recommended accepting the paper, I will keep my score.

Thank the authors for the rebuttal.

The rebuttal addresses my major concerns and I raise the score accordingly.