WikiEdge:ArXiv-2409.02852v1/abs

编辑

• 标题：Key Compression Limits for $k$-Minimum Value Sketches
• 中文标题：$k$-最小值草图的密钥压缩极限
• 发布日期：2024-09-04T16:22:58+00:00
• 作者：Charlie Dickens, Eric Bax, Alexander Saydakov
• 分类：cs.DS, cs.IT, math.IT
• 原文链接：http://arxiv.org/abs/2409.02852v1

摘要：$k$-最小值（kmv）数据草图算法存储通过对数据集中的项目进行哈希生成的$k$个最小哈希键。我们表明，基于键的排序和编码连续差异的压缩方法可以在预期存储节省中提供每个键$O(\log n)$位的节省，其中$n$是数据集中唯一值的数量。我们还表明，对于$n$个随机值的$k$个最小值，$O(\log n)$位的预期节省是任何形式压缩的最优值——该编码方法在所有编码kmv草图的方法中是近乎最优的。我们提出了一种实用的压缩方法，表明其计算效率高，并展示其在实践中的平均节省与基于熵的理论最小值相差约5%。我们验证了我们的方法优于现成的压缩方法，并展示了其在使用真实和合成数据时的实用性。