Thoughts on "Static Retrieval Revisited"

Table of Contents

1 Problem definitions

2 Optimal solutions

3 Why an overhead is necessary

4 Augmented Retrieval

endtoc

These are some summarizing notes and thoughts on“Static Retrieval Revisited: To Optimality and beyond” by Hu, Kuszmaul, Liang, Yu, Zhang, and Zhou.

1 Problem definitionsLink to heading

Static Retrieval. Given (n) keys (X\subseteq U) and (n) $v$-bit values (f(X) \in [2^v]), encode (f: X\to [2^v]). The goal is use a minimal number of bits on top of the trivial (nv) lower bound, while allowing efficient queries.