User:Optimalsloth/sandbox

In computer science, a static function, also known as retrieval data structure, is a space-efficient dictionary-like data type composed of a collection of (key, value) pairs that allows the following operations:

• Construction from a collection of (key, value) pairs
• Retrieve the value associated with the given key or anything if the key is not contained in the collection
• Update the value associated with a key (optional)

They can also be thought of as a function $b\colon \,{\mathcal {U}}\to \{0,1\}^{r}$ for an universe ${\mathcal {U}}$ and the set of keys $S\subseteq {\mathcal {U}}$ where retrieve has to return $b(x)$ for any value $x\in S$ and a random value from $\{0,1\}^{r}$ otherwise.

In contrast to static functions, AMQ-filters support (probabilistic) membership queries and dictionaries additionally allow operations like listing keys or looking up the value associated with a key and returning some other symbol if the key is not contained.

As can be derived from the operations, this data structure does not need to store the keys at all and may actually use less space than would be needed for a simple list of the key value pairs. This makes it attractive in situations where the associated data is small (e.g. a few bits) compared to the keys because we can save a lot by reducing the space used by keys.

To give a simple example suppose $n$ names annotated with either male or female are given. A static function built from this database can reproduce the associated tag for all names contained in the original set and a random one for other names. The size of this static function can be made to be only $(1+\epsilon )n$ bits for a small $\epsilon$ which is obviously much less than any pair based representation.

Examples

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.

Perfect Hash Functions

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.

Mit einer Minimum Perfect Hash Function hat man dann (besonders bei großen abzurufenden Elementen) kaum Overhead (TODO overhead gegenüber was??).

XOR-Filters

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 filters and are the most promising for building them space efficiently. They are built by solving a linear system which ensures that a query for every key returns true.

Construction

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

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

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

A retrieval for $x\in {\mathcal {U}}$ can be expressed as the bitwise XOR of the rows $Z_{i}$ for all set bits $i$ of $h(x)$. Furthermore, fast queries require sparse $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.

Ribbon fiters

Using a random matrix $h$ makes retrievals cache inefficient because they access most of $Z$ on average. Ribbon filters improve on this by giving each $h(x)$ a consecutive "ribbon" of width $w={\mathcal {O}}(\log n/\epsilon )$ in which bits are set at random. Furthermore, using the property of $(h(x))_{x\in S}$ the matrix $Z$ can be computed in ${\mathcal {O}}(n/\epsilon ^{2})$ expected time.

Applications

Approximate membership

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

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

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

The performance of this data structure is exactly the performance of the underlying static function.

Perfect Hash Functions

Das wird jetzt ein bisschen rekursiv, weil es bei den Beispielen zur Konstruktion auch schon dran stand, aber man kann static functions dazu benutzen, PHF zu bauen. Stell dir zum Beispiel eine cuckoo hashtabelle vor, in die schon alle Elemente eingefügt sind. Jedes Element darf an 2 verschiedenen Positionen sitzen und an jeder Position darf nur ein Element sitzen. Um jetzt eine PHF dieser Elemente zu generieren, müssen wir uns pro Element nur noch speichern, welche seiner beiden Positionen es denn am Ende genommen hat. Also eine 1-bit static function.