CARAMEL: A Succinct Read-Only Lookup Table via Compressed Static Functions
This addresses the need for efficient compression in data processing systems like NLP and recommendation systems, though it is incremental as it builds on static function techniques.
The paper tackles the problem of compressing large lookup tables for fast random access by introducing CARAMEL, a space-efficient representation for immutable key-value data with multi-set values, achieving 1.25-16x compression on real-world tasks and outperforming existing techniques.
Lookup tables are a fundamental structure in many data processing and systems applications. Examples include tokenized text in NLP, quantized embedding collections in recommendation systems, integer sketches for streaming data, and hash-based string representations in genomics. With the increasing size of web-scale data, such applications often require compression techniques that support fast random $O(1)$ lookup of individual parameters directly on the compressed data (i.e. without blockwise decompression in RAM). While the community has proposd a number of succinct data structures that support queries over compressed representations, these approaches do not fully leverage the low-entropy structure prevalent in real-world workloads to reduce space. Inspired by recent advances in static function construction techniques, we propose a space-efficient representation of immutable key-value data, called CARAMEL, specifically designed for the case where the values are multi-sets. By carefully combining multiple compressed static functions, CARAMEL occupies space proportional to the data entropy with low memory overheads and minimal lookup costs. We demonstrate 1.25-16x compression on practical lookup tasks drawn from real-world systems, improving upon established techniques, including a production-grade read-only database widely used for development within Amazon.com.