CARAMEL: A Succinct Read-Only Lookup Table via Compressed Static Functions

Efficient data structures for storing key-value pairs are indispensable components for countless modern systems, spanning a diverse array of applications including recommender systems, search engines, genomics, and natural language processing. With the ballooning volume of web-scale data, practitioners maintain an intense interest in building caches with a lower memory footprint and faster query times. Inspired by the observation that many applications involve static data collections that need not support real-time insertions or deletions, which allows for more aggressive compression strategies, we focus on developing a read-only data structure with space close to the information-theoretic lower bound while supporting constant-time lookups directly on the compressed representation.

In this work, we design such a representation using compressed static functions and call our data structure CARAMEL (Compressed Array Representation And More Efficient Lookups). A static function is a mapping $f:K\to V$ from a static, known set of hashable keys $K$ to encodable values $V$ such as strings and integers. A compressed static function (CSF) is a static function that can represent $f$ in space proportional to the entropy of $V$ and can evaluate $f$ in $O(1)$ time (dietzfelbinger2008succinct, ). While CSFs were historically a purely theoretical curiosity, recent advances in practical construction techniques allow near-optimal sized CSFs to be developed for millions of parameters (8416577, ; genuzio2016fast, ; genuzio2020fast, ).

However, prior work on utilizing CSFs in practical applications largely focus on storing a single value for a given key (genuzio2016fast, ; shibuya2022space, ). In this paper, we study the problem of how to efficiently build a CSF structure for a multiset of values. This setting arises in a number of real-world application. For example, search and recommendation systems often cache the most popular query-result pairs to reduce the throughput demands on machine learning models and improve the average latency (Luo2022, ). In large-scale production serving systems, this table can contain millions of keys each with hundreds of values and consumes the majority of the server memory budget (guo2020accelerating, ; nigam2019semantic, ). Furthermore, common NLP and genomics tokenization processes yield massive arrays of integer tokens (shu2018compressing, ; chen2018learning, ; ondov2016mash, ). To that end, we propose a novel data structure based on arrays of multiple CSFs to address these data-intensive applications. By carefully designing our data structure to support multiple CSFs with minimal overhead, we find that we can achieve further compression than simply using a single static function and validate our approach across a myriad of real-world static retrieval tasks.

With this goal in mind, we consider the following problem. Given a static set of pairs consisting of a key $k$ and a list of values $A=\left\{(k_{i},[v_{i1},v_{i2},\dots,v_{im}])\right\}_{i=1}^{n}$, we wish to construct a small data structure $S$ that can return an individual value $v_{ij}$ in constant time and hence the entire list in time $O(m)$. Standard file compression methods that employ methods such as run-length encoding, delta coding, specialized codecs and other techniques (witten1999managing, ; scholer2002compression, ; williams1999compressing, ; thompson2022github, )are insufficient for this task because they do not allow queries directly on the compressed representation. Moreover, existing succinct data structures do not fully leverage the underlying structure of the data to achieve lower space. In summary, our ideal data representation should satisfy three requirements:
1) Lossless Compression: $S$ must represent $A$ with no error, and $S$ should be much smaller than $A$. Ideally, $S$ is of similar size to that obtained via standard compression methods.
2) Random Access: The cost to obtain a value from $S$ should scale $O(1)$ with $n$ and be fast in practice. Ideally, the lookup time should be comparable to the latency of a hash table.
3) Fast Construction: The time and computation needed to construct $S$ should not exceed practical limitations. For example, a standard workstation should be able to compress an input with a million keys in a few minutes.

In this section, we introduce the tools needed for our proposed data structure, beginning with compressed static functions. A CSF, first formally introduced by (belazzougui2013compressed, ), is a function satisfying the following definition. Constructing such functions is the subject of considerable research in the theory community (porat2009optimal, ; dietzfelbinger2008succinct, ; hreinsson2009storing, ; belazzougui2013compressed, ; botelho2013practical, ).

It should be noted that the values $V$ are a multiset because the elements are not necessarily unique. For example, we may require that $f(k_{1})=f(k_{2})$. When combined with the fact that CSFs are static, the non-uniqueness of values will permit us to attain good compression by developing an optimal instantaneous code for the values of $V$. To quantify the space needed by the CSF, we introduce the concept of empirical entropy.

Compressed static functions aim to represent $f(k)$ in $O(NH_{0}(V))$ space (belazzougui2013compressed, ). Several different construction methods are possible. The simplest method is to use an $O(N)$-space bijection from $K$ to the integers $\{1,...N\}$ to index into an array of encoded values (e.g. using a minimal perfect hash function and Huffman coding). However, this technique requires substantial overhead in the form of the bijection and pointers to the array. Recent work demonstrates substantial improvements by directly computing the encodings of the values.

CSFs via Linear Systems: The fundamental insight of (8416577, ) is that a CSF may be constructed via a binary linear system. To illustrate this construction technique, suppose we wish to construct a CSF for the set of key-value pairs $\{(k_{1},v_{1}),(k_{2},v_{2}),...(k_{N},v_{N})\}$. We begin by hashing each key using three universal (random) hash functions, resulting in three integers $(h_{1}(k),h_{2}(k),h_{3}(k))$ for each key. We also apply an instantaneous code to obtain a binary encoding $e(v)$ for each value. This process gives rise to a linear system that, when solved, yields a CSF.

For a concrete example, let’s write out a portion of the linear system for the keys $k_{1},k_{2},$ and $k_{N}$. Suppose that the hash functions output values in the range $[1,8]$ and that $k_{1}$ maps to $(5,7,8)$, $k_{2}$ to $(1,4,2)$ and $k_{N}$ to $(3,6,8)$. Furthermore, suppose that we have the encodings $\{e(v_{1})=1,e(v_{2})=001,...e(v_{N})=1\}$. We consider the following linear system on the binary space $\mathbf{Z}/2\mathbf{Z}$, where addition and multiplication are replaced by the OR and XOR operations, respectively.

In the solution vector, we use the notation $e(v_{j})_{i}$ to denote the $i$th bit of the instaneous encoding for the value $v_{j}$. The positions of the 1’s in the matrix are decided by the hash functions of the corresponding key $(h_{1}(k),h_{2}(k),h_{3}(k))$, offset by the position of the corresponding bit of the encoding $e(v(k))$. For example, the first row in the matrix corresponds to $k_{1}$, as $v_{1}$ has a 1-bit encoding. The next three rows are responsible for the 3-bit encoding of $v_{2}$. Thus, there is one linear equation for each bit of each encoded value. The solution $\mathbf{g}$ of this system, if it exists, can serve as a lookup table to compute $f(k)$. To obtain the first bit of $e(f(k))$, we access the bits of $\mathbf{g}$ at the locations identified by the hash values of $k$ and compute the XOR. To obtain the subsequent bits of the encoding, we shift the locations to the right. Because $e$ is an instantaneous code, the process finishes as soon as we read a valid symbol.

The probability that the system is solvable depends on the length of $\mathbf{g}$ and is governed by the satisfiability of $s$-XORSAT instances (where $s$ is the number of hash functions used) (dubois20023, ). The major contribution of (8416577, ; genuzio2016fast, ; genuzio2020fast, ) is to make these large systems practically solvable.

Sources of Overhead: When the code lengths from Theorem 2.3 exactly match the inverse frequencies of the values, the sum of code lengths becomes exactly $NH_{0}(V)$, leading to an overhead of $\delta_{s}$ (roughly 8.9% for $s=3$). However, this is not the case in practice - we observe a much larger per-key overhead. There are two reasons for this: code length mismatch and codebook storage. While Huffman codes have an expected per-key overhead within 1 bit of the Shannon bound ($H_{0}$), the encoding only hits the bound with equality when frequencies decay in inverse powers of two. Also, the codebook requires storage of $V$, which can be expensive when $V$ consists of long strings or integers.

Bloom Filter Heuristics: A particularly bad situation is when one value occurs more than 50% of the time. When this happens, prefix codes incur an overhead of at least $N/2$ bits (since one bit is needed for each value). This observation has led genomics practitioners to adopt a filtering approach wherein a Bloom filter (shibuya2022space, ) is used to identify keys with non-dominating values, reducing the load on the CSF and improving the overhead. The filter parameters are based on a complex learned heuristic that predicts the size of the CSF. To the best of our knowledge, this is the only other work that applies CSFs to practical real-world problems. Unfortunately, we found that their filtering method actually introduces substantial overhead, making it worse than using the CSF, likely because the heuristics are specifically tuned for their $k$-mer count table application. We conduct a precise analysis of pre-filtering methods and give an information-theoretic bound on the combined space of the CSF and the filter that provides optimal hyperparameters.

In this section, we introduce two algorithms that can be used for similar purposes as CARAMEL. We compare against both algorithms in the experiments.

In this section, we describe our approach to compress key-value datasets through (CARAMEL). For clarity of the mathematical presentation, we will describe our algorithm in terms of partitioning an integer matrix $A\in\mathbb{Z}^{N\times m}$ into $m$ different CSFs, one for each dimension. We note that CARAMEL can also operate on general hashable types such as strings. However, we can discuss the theoretical properties of CARAMEL in terms of integer matrices without loss of generality by assuming that the integers are the hashed representations of some initial input (which is also how we implement the data structure in practice). We also consider the set of keys to be the integers $\{1,...N\}$. In practice, for applications such as embedding lookup, we use the text string corresponding to each row of $A$ as the key but we can again consider integer keys in our analysis without loss of generality.

Construction and Query: The construction process consists of the following tasks, which are described by Algorithm 1. First, if the application supports the shuffling of items without changing the representation, we permute the items in $A$ to find the configuration with the lowest column-wise entropy (see Definition 5.3). This improves both the construction time and space of the CSF. Next, we decide whether to use a Bloom filter to pre-filter keys for each dimension. If the frequency of the most common value $v_{0}$ exceeds a threshold, we create a Bloom filter of non-dominating values and construct a CSF over the keys for which the filter returns ‘True.’ We will derive the decision criterion and optimal filter parameters in Section 5. Finally, we construct an independent CSF over the permuted and filtered elements in each column of $A$. To query the array with a key $k$, we first check the Bloom filter to determine whether the CSF will be needed. If the Bloom filter returns ‘True,’ (i.e. $v(k)$ is not the dominating value), then we query the CSF. Otherwise, we return $v_{0}$. We repeat the process for as many lookups as are required.

Discarding the Keys: The only practical constraint on the keys is that they be hashable. This allows integers, strings and many other types to be used. It should be noted that each CSF does not require the keys to be maintained or stored in any way. This property of the CSF structure allows us to achieve additional memory savings over alternative methods.

Why not use a single CSF? Since we may just as easily treat the entire matrix $A$ as a flat set of integer parameters, it is worth questioning whether a single CSF might result in a more efficient representation. However, there are good reasons for using a 2D representation. For example, there are information-theoretic benefits to independently encoding each dimension when different columns have different vocabulary distributions. For example, suppose we wish to compress a matrix with two columns. Column 1 has the vocabulary $(a,b,c)$ with relative frequencies $(0.5,0.25,0.25)$ while column 2 has the vocabulary $(d,e,f)$ with the same frequencies. If we compress the columns independently, $a$ and $d$ are both representable by 1 bit. However, the Huffman code for the merged version uses 2 bits for both $a$ and $d$ (while having the same codebook storage cost). Because CARAMEL is able to implicitly encode the knowledge that different columns have different vocabulary distributions, we can use specialized encodings within each column, enabling more optimizations (e.g. Algorithm  2).

Exploiting Parallelism: There are also practical reasons to decompose a large set of integer parameters into several independent CSFs. We find it advantageous to parallelize the construction process, since our larger tasks (e.g. MSMarco (nguyen2016ms, ) and the Pile (gao2020pile, )) would need systems with billions of equations to represent the flat version. The CSF array representation is also helpful at query time, where we may query multiple structures in parallel.

In this section, we discuss the space and query time of our CSF array. We also develop a rigorous analysis of CSFs with prefiltering, giving rise to optimal criteria and hyperparameters for Bloom-enhanced CSF structures. Finally, we discuss optimizations to reduce the column-wise entropy of the matrix for applications that support the reordering of items along one of the dimensions of $A$.

Memory and Lookup Time: We begin with an easy consequence of the results in (hreinsson2009storing, ). The space occupied by our data structure is proportional to the sum of column entropies on $A$.

We provide experiments for various classes of applications in Table 1 and Figure 1, analyzing popular datasets from web search, genomics, information retrieval, and more  (aumuller2017ann, ). Additionally, we provide baselines for related methods as discussed in Section 3.

Compression on Synthetic Datasets: As a preliminary exercise to examine the potential for CSFs to compress integer matrices, we conducted two synthetic data experiments where we generated integer matrices first sampled from a discrete uniform distribution $\mathcal{U}(1,1000)$ and then from a discrete truncated power law distribution $f(x)=cx^{-k}$ where we set $k=2$, set the support over $(1,1000)$, and select the normalizing constant $c$ accordingly. This synthetic experiment closely follows that of (8416577, ) with the notable exception that we examine compressing a two-dimensional matrix as opposed to a one-dimensional array.

Experiment Setup: Preprocessing work was done in python and resulted in some transformed integer matrix from which to build our CARAMEL structure. All results in Table 1 were obtained using using the publicly available Sux4j Library ²²2http://sux4j.di.unimi.it/ in Java. Compression numbers are recorded excluding keys and we report additional baselines as the sum of the column-wise entropy of the matrix. Query latencies shown in Figure 1 were obtained using timing modules built in C++. For our NLP experiments, we tokenize the text using the popular SentencePiece library ³³3https://github.com/google/sentencepiece (kudo2018sentencepiece, ). For our case study comparing against a production read-only database at Amazon, we build CSFs using our own Python implementation, which, unlike existing CSF libraries, supports generic hashable types such strings.

For our remaining baseline methods, we conduct all of the evalations in Java. For Succinct, we use the standard Java release by the authors (agarwal2015succinct, ). For MPH tables, we use a library that has been optimized to work in production by Indeed (indeedMPH, ). It should be noted that Succinct can only support files up to 2 GB in size and that Indeed’s MPH library can be slow to construct tables for large inputs. For this reason, we were unable to run the baselines for some of our data compression tasks.

Product-Quantized Embedding Tables: It is fairly common in enterprise systems to approximate large embedding tables with quantization (jegou2010product, ; guo2020accelerating, ; johnson2019billion, ; kang2020learning, ; ko2021low, ). We apply CARAMEL to quantized embedding tables and report our compression numbers compared to the space of these tables with keys included. Additionally, all embedding tables are quantized to ensure a reasonable metric distortion of ¿80% KNN-recall@100 (jegou2010product, ; kang2020learning, ).

Construction Time: Construction times are reasonable, especially in the context of machine learning systems that frequently don’t update for upwards of a day or more. For 10M keys we construct a single CSF in just over 1 minute, for 100M keys: 10+ minutes, and for 1B keys: less than 2 hours. For billion scale data this construction time is more than reasonable, especially considering CARAMEL and CSF constructions are trivially parallelizable.

Query Time: We compare query times between our CARAMEL structure and a standard hash table implemented in C++. We look at both median and 99^th percentile query time (P99) as P99 is the defining factor for latency in web-scale production systems. We also investigate the query time scaling as $N$ increases to demonstrate the the worst case complexity of hash-tables against the $O(1)$ lookups into CSFs. Timing experiments were done on a machine equipped with Intel(R) Xeon(R) Gold 5220R CPU @ 2.20GHz over 20,000 queries.

We introduce CARAMEL, a new data structure for read-only key-value lookups based on the key insight of combining multiple compressed static functions (CSFs) together. We demonstrate in this paper that CSFs are practically useful data structures that provide a powerful primitive for improving the scalability of numerous data-intensive applications. We also show that CARAMEL performs favorably when compared to existing algorithms and systems proposed in both the academic literature and in active production use at a leading online technology company, which underscores the relevance of our work for industry practitioners. Furthermore, we also push the theoretical foundations of CSFs forward by proving precise guarantees on when to apply Bloom filter enhancements. We hope that our work will bring the community’s attention to both the prevalence of low-entropy key-value mappings across data-intensive applications and the potential for representations like CARAMEL to aid in the important effort of scaling data infrastructure in the future.