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%。我們驗證了我們的方法優於現成的壓縮方法，並展示了其在使用真實和合成數據時的實用性。