Retrieval Data Structure

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:[1]

* 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:𝒰->{0,1}r for a universe 𝒰 and the set of keys S⊆𝒰 where retrieve has to return b(x) for any value x∈S and an arbitrary 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 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 bits for a small ϵ which is obviously much less than any pair based representation.[1]

## Contents

* 1 Space and Time Bounds
* 2 Examples
* 2.1 Perfect hash functions
* 2.2 XOR-retrieval
* 2.2.1 Construction
* 2.2.2 Ribbon retrieval
* 3 Applications
* 3.1 Approximate membership
* 3.2 Perfect hash functions
* 4 References

## Space and Time Bounds

Given a set of n key-value pairs, where each value is r bits, a retrieval data structure that uses rv+k bits is said to have redundancy k. An ideal retrieval data structure should have small redundancy, while supporting fast retrieval.[2]

In the static setting, where the only operations are Construct and Retrieve, it is possible to construct solutions with redundancy k=o(n).[2][3] However, depending on the parameter regime, it is not always possible to achieve such a small redundancy while also supporting constant-time retrieval.[4] For example, if r=Θ(log⁡n) and assuming machine words of length w=Θ(log⁡n) bits, any solution with constant-time retrieval queries must incur redundancy k=Ω(n).[4]

The optimal redundancy changes significantly if one considers non-static versions of the problem.

* In the value-dynamic retrieval problem, where the data structure must support an Update operation, the optimal redundancy is k=Θ(n) no matter the value of r and regardless of time efficiency.[5] Moreover, when r=ω(1), it is believed that the optimal redundancy, up to low order terms, is achieved by a minimal perfect hash function.[5]
* In the dynamic retrieval problem, the data structure must support Insert and Delete operations on the set of key-value pairs, with a maximum capacity n on the size of the set at any given moment. Assuming keys from a large polynomial-size universe, the optimal redundancy for this version of the problem is k=Θ(nlog⁡log⁡n) bits, even if r=1.[6][7] Moreover, if the capacity constraint of n is removed, then it is still possible to achieve redundancy k=Θ(nmaxlog⁡log⁡nmax), where nmax is the largest size the set has had so far.[8]
* In the incremental retrieval problem, the data structure must support Insert operations on the set of key-value pairs, with a maximum capacity n on the size of the set. In this setting, the optimal redundancy is k=o(n) bits, as in the static setting.[7]

## 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.

### XOR-retrieval

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.

Retrieval of an element

#### Construction

Given a hash function h that maps each key to a bitvector of length m≥|S|=n where all (h(x))x∈S are linearly independent the following system of linear equations has a solution Z∈{0,1}m×r:

(h(x)⋅Z=b(x))x∈S

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

A retrieval for x∈𝒰 can be expressed as the bitwise XOR of the rows Zi 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 retrieval

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

Using the properties of (h(x))x∈S the matrix Z can be computed in 𝒪(n/ϵ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 𝒪(log⁡n/ϵ) bits which can be done in 𝒪(1/ϵ) time on a RAM. It can be shown that the expected amount of row operations is 𝒪(n/ϵ). Finally, the solution is obtained by backsubstitution.[10]

## Applications

Hash functions that lead to insertions are used to build a perfect hash function

### Approximate membership

To build an approximate membership data structure use a fingerprinting function h:𝒰->{0,1}r. Then build a static function DhS on hS restricted to the domain of our keys S.

Checking the membership of an element x∈𝒰 is done by evaluating DhS with x and returning true if the returned value equals h(x).

* If x∈S, DhSreturns the correct value h(x) and we return true.
* Otherwise, DhSreturns a random value and we might give a wrong answer. The length r of the hash allows controlling the false positive ratef=2r.

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

### Perfect hash functions

A retrieval data structure can be used to construct a perfect hash function: First insert the keys into a cuckoo hash table with H=2r hash functions hi 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 r-bit retrieval data structure D. The perfect hash function is given by hD(x)(x).[12]

## References

1. ↑ 1.0 1.1 Stefan, Walzer (2020). Random hypergraphs for hashing-based data structures (PhD). pp. 27–30.
2. ↑ 2.0 2.1 Dietzfelbinger, Martin; Pagh, Rasmus (2008), "Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)", Lecture Notes in Computer Science, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 385–396, doi:10.1007/978-3-540-70575-8_32, ISBN 978-3-540-70574-1, https://doi.org/10.1007/978-3-540-70575-8_32, retrieved 2026-04-04
3. ↑ Porat, Ely (2009), "An Optimal Bloom Filter Replacement Based on Matrix Solving", Computer Science - Theory and Applications, Lecture Notes in Computer Science, 5675, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 263–273, doi:10.1007/978-3-642-03351-3_25, ISBN 978-3-642-03350-6, https://doi.org/10.1007/978-3-642-03351-3_25, retrieved 2026-04-04
4. ↑ 4.0 4.1 Hu, Yang; Kuszmaul, William; Liang, Jingxun; Yu, Huacheng; Zhang, Junkai; Zhou, Renfei (2025-12-14). "Static Retrieval Revisited: To Optimality and Beyond". 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS). IEEE. pp. 2392–2409. doi:10.1109/focs63196.2025.00126. ISBN 979-8-3315-7132-0. https://doi.org/10.1109/focs63196.2025.00126.
5. ↑ 5.0 5.1 Kuszmaul, William; Walzer, Stefan (2024-06-10). "Space Lower Bounds for Dynamic Filters and Value-Dynamic Retrieval". Proceedings of the 56th Annual ACM Symposium on Theory of Computing. New York, NY, USA: ACM. pp. 1153–1164. doi:10.1145/3618260.3649649. ISBN 979-8-4007-0383-6.
6. ↑ Demaine, Erik D.; der Heide, Friedhelm Meyer auf; Pagh, Rasmus; Pǎtraşcu, Mihai (2006), "De Dictionariis Dynamicis Pauco Spatio Utentibus", Lecture Notes in Computer Science, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 349–361, doi:10.1007/11682462_34, ISBN 978-3-540-32755-4, https://doi.org/10.1007/11682462_34, retrieved 2026-04-04
7. ↑ 7.0 7.1 Kuszmaul, William; Putterman, Aaron; Xu, Tingqiang; Zhou, Hangrui; Zhou, Renfei (2025), "Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval", Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Philadelphia, PA: Society for Industrial and Applied Mathematics, pp. 3974–3997, doi:10.1137/1.9781611978322.135, ISBN 978-1-61197-832-2, https://doi.org/10.1137/1.9781611978322.135, retrieved 2026-04-04
8. ↑ Bercea, Ioana Oriana; Even, Guy (2022-06-09). "An extendable data structure for incremental stable perfect hashing". Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. New York, NY, USA: ACM. pp. 1298–1310. doi:10.1145/3519935.3520070. ISBN 978-1-4503-9264-8. https://doi.org/10.1145/3519935.3520070.
9. ↑ 9.0 9.1 Dillinger, Peter C.; Walzer, Stefan (2021). "Ribbon filter: practically smaller than Bloom and Xor". arXiv:2103.02515 [cs.DS].
10. ↑ Dietzfelbinger, Martin; Walzer, Stefan (2019). "27th Annual European Symposium on Algorithms, ESA 2019, September 9–11, 2019, Munich/Garching, Germany". in Bender, Michael A.; Svensson, Ola; Herman, Grzegorz. 144. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 39:1–39:18. doi:10.4230/LIPIcs.ESA.2019.39.
11. ↑ Dietzfelbinger, Martin; Pagh, Rasmus (2008). "Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008, Proceedings, Part I: Track A: Algorithms, Automata, Complexity, and Games". in Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann et al.. 5125. Springer. pp. 385–396. doi:10.1007/978-3-540-70575-8_32. ISBN 978-3-540-70574-1.
12. ↑ Walzer, Stefan (2021). "Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10–13, 2021". in Marx, Dániel. Society for Industrial and Applied Mathematics. pp. 2194–2211. doi:10.1137/1.9781611976465.131. ISBN 978-1-61197-646-5.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Retrieval Data Structure. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Retrieval_Data_Structure&oldid=4566573"