用循环编码无损压缩聚类结果，省存省算还更高效
Random Cycle Coding: Lossless Compression of Cluster Assignments via Bits-Back Coding
- 按顺序编码数据，用排列循环传递聚类归属信息
- 实验显示每元素最多省2字节，向量库可节省70%存储
- 无需训练，适合大规模向量数据库的相似搜索场景
我们提出一种最优的任意数据集聚类分配编码方法——随机循环编码（RCC）。RCC 逐个编码数据，并将分配信息以编码元素顺序定义的排列循环形式传输。该方法无需训练，最坏情况下的复杂度与最大簇大小呈准线性关系。我们刻画了比特率与簇大小及元素数量的关系，表明 RCC 在所有条件下均优于以往方法，且计算与内存开销更小。实验显示，应用于向量数据库时，RCC 可实现每元素最高节省 2 字节，同时消除为向量分配整数 ID 的需求，使相似搜索应用中的向量数据库系统存储开销降低高达 70%。
原文摘要 · Abstract (English)
We present an optimal method for encoding cluster assignments of arbitrary data sets. Our method, Random Cycle Coding (RCC), encodes data sequentially and sends assignment information as cycles of the permutation defined by the order of encoded elements. RCC does not require any training and its worst-case complexity scales quasi-linearly with the size of the largest cluster. We characterize the achievable bit rates as a function of cluster sizes and number of elements, showing RCC consistently outperforms previous methods while requiring less compute and memory resources. Experiments show RCC can save up to 2 bytes per element when applied to vector databases, and removes the need for assigning integer ids to identify vectors, translating to savings of up to 70% in vector database systems for similarity search applications.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。