In computer science, a retrieval data structure, also known as static function, 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 : U → { 0 , 1 } r {\displaystyle b\colon \,{\mathcal {U}}\to \{0,1\}^{r}} for a universe U {\displaystyle {\mathcal {U}}} and the set of keys S ⊆ U {\displaystyle S\subseteq {\mathcal {U}}} where retrieve has to return b ( x ) {\displaystyle b(x)} for any value x ∈ S {\displaystyle x\in S} and an arbitrary value from { 0 , 1 } r {\displaystyle \{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 {\displaystyle n} video game names annotated with a boolean indicating whether the game contains a dog that can be petted are given. A static function built from this database can reproduce the associated flag for all names contained in the original set and an arbitrary one for other names. The size of this static function can be made to be only ( 1 + ϵ ) n {\displaystyle (1+\epsilon )n} bits for a small ϵ {\displaystyle \epsilon } which is obviously much less than any pair based representation.
Space and Time Bounds Given a set of n {\displaystyle n} key-value pairs, where each value is r {\displaystyle r} bits, a retrieval data structure that uses r v + k {\displaystyle rv+k} bits is said to have redundancy k {\displaystyle k} . An ideal retrieval data structure should have small redundancy, while supporting fast retrieval. In the static setting, where the only operations are Construct and Retrieve, it is possible to construct solutions with redundancy k = o ( n ) {\displaystyle k=o(n)} . However, depending on the parameter regime, it is not always possible to achieve such a small redundancy while also supporting constant-time retrieval. For example, if r = Θ ( log n ) {\displaystyle r=\Theta (\log n)} and assuming machine words of length w = Θ ( log n ) {\displaystyle w=\Theta (\log n)} bits, any solution with constant-time retrieval queries must incur redundancy k = Ω ( n ) {\displaystyle k=\Omega (n)} . The optimal redundancy changes significantly if one considers non-static versions of the problem.
… excerpt ends here. Continue reading the full article.
