Opening book details…
Can I read CARAMEL: A Succinct Read-Only Lookup Table via Compressed Static Functions on EtoBox?
CARAMEL: A Succinct Read-Only Lookup Table via Compressed Static Functions by Coleman, Benjamin; Ramos, David Torres; Lakshman, Vihan; Luo, Chen; Shrivastava, Anshumali is a scholarly article available to read on EtoBox.
What is CARAMEL: A Succinct Read-Only Lookup Table via Compressed Static Functions about?
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 pra
- Author
- Coleman, Benjamin; Ramos, David Torres; Lakshman, Vihan; Luo, Chen; Shrivastava, Anshumali
- Published
- 2023
- Language
- EN