Retrieval Data Structure

A trivial example of a static function is a sorted list of the keys and values which implements all the above operations and many more. However, the retrieve on a list is slow and we implement many unneeded operations that can be removed to allow optimizations. Furthermore, we are even allowed to return junk if the queried key is not contained which we did not use at all.

Another simple example to build a static function is using a perfect hash function: After building the PHF for our keys, store the corresponding values at the correct position for the key. As can be seen, this approach also allows updating the associated values, the keys have to be static. The correctness follows from the correctness of the perfect hash function. Using a minimum perfect hash function gives a big space improvement if the associated values are relatively small.

Hashed filters can be categorized by their queries into OR, AND and XOR-filters. For example, the bloom filter is an AND-filter since it returns true for a membership query if all probed locations match. XOR filters work only for static retrievals and are the most promising for building them space efficiently.^[9] They are built by solving a linear system which ensures that a query for every key returns true.

Given a hash function ${\displaystyle h}$ that maps each key to a bitvector of length ${\displaystyle m\geq \left\vert S\right\vert =n}$ where all ${\displaystyle (h(x))_{x\in S}}$ are linearly independent the following system of linear equations has a solution ${\displaystyle Z\in \{0,1\}^{m\times r}}$:

${\displaystyle (h(x)\cdot Z=b(x))_{x\in S}}$

Therefore, the static function is given by ${\displaystyle h}$ and ${\displaystyle Z}$ and the space usage is dominated by ${\displaystyle Z}$ which is roughly ${\displaystyle (1+\epsilon )n}$ bits per key for ${\displaystyle m=(1+\epsilon )n}$, the hash function is assumed to be small.

A retrieval for ${\displaystyle x\in {\mathcal {U}}}$ can be expressed as the bitwise XOR of the rows ${\displaystyle Z_{i}}$ for all set bits ${\displaystyle i}$ of ${\displaystyle h(x)}$. Furthermore, fast queries require sparse ${\displaystyle h(x)}$, thus the problems that need to be solved for this method are finding a suitable hash function and still being able to solve the system of linear equations efficiently.

Using a sparse random matrix ${\displaystyle h}$ makes retrievals cache inefficient because they access most of ${\displaystyle Z}$ in a random non local pattern. Ribbon retrieval improves on this by giving each ${\displaystyle h(x)}$ a consecutive "ribbon" of width ${\displaystyle w={\mathcal {O}}(\log n/\epsilon )}$ in which bits are set at random.^[9]

Using the properties of ${\displaystyle (h(x))_{x\in S}}$ the matrix ${\displaystyle Z}$ can be computed in ${\displaystyle {\mathcal {O}}(n/\epsilon ^{2})}$ expected time: Ribbon solving works by first sorting the rows by their starting position (e.g. counting sort). Then, a REM form can be constructed iteratively by performing row operations on rows strictly below the current row, eliminating all 1-entries in all columns below the first 1-entry of this row. Row operations do not produce any values outside of the ribbon and are very cheap since they only require an XOR of ${\displaystyle {\mathcal {O}}(\log n/\epsilon )}$ bits which can be done in ${\displaystyle {\mathcal {O}}(1/\epsilon )}$ time on a RAM. It can be shown that the expected amount of row operations is ${\displaystyle {\mathcal {O}}(n/\epsilon )}$. Finally, the solution is obtained by backsubstitution.^[10]

To build an approximate membership data structure use a fingerprinting function ${\displaystyle h\colon \,{\mathcal {U}}\to \{0,1\}^{r}}$. Then build a static function ${\displaystyle D_{h_{S}}}$ on ${\displaystyle h_{S}}$ restricted to the domain of our keys ${\displaystyle S}$.

Checking the membership of an element ${\displaystyle x\in {\mathcal {U}}}$ is done by evaluating ${\displaystyle D_{h_{S}}}$ with ${\displaystyle x}$ and returning true if the returned value equals ${\displaystyle h(x)}$.

• If ${\displaystyle x\in S}$, ${\displaystyle D_{h_{S}}}$returns the correct value ${\displaystyle h(x)}$ and we return true.
• Otherwise, ${\displaystyle D_{h_{S}}}$returns a random value and we might give a wrong answer. The length ${\displaystyle r}$ of the hash allows controlling the false positive rate${\displaystyle f=2^{r}}$.

The performance of this data structure is exactly the performance of the underlying static function.^[11]

A retrieval data structure can be used to construct a perfect hash function: First insert the keys into a cuckoo hash table with ${\displaystyle H=2^{r}}$ hash functions ${\displaystyle h_{i}}$ and buckets of size 1. Then, for every key store the index of the hash function that lead to a key's insertion into the hash table in a ${\displaystyle r}$-bit retrieval data structure ${\displaystyle D}$. The perfect hash function is given by ${\displaystyle h_{D(x)}(x)}$.^[12]