Overview of static data structures

Table of Contents

1 Classification of static data structures

2 Space lower bounds and practical approaches

2.1 Rank

2.2 Rank + Select

2.3 Minimal perfect hash function (MPHF)

2.4 TODO Monotone MPHF

2.5 TODO Order-preserving MPHF

2.6 Static retrieval: Static function with static values

2.7 Updatable retrieval: Static function with mutable values

2.8 Static set (membership)

2.9 Static ordered set

2.10 Static dictionary: static keys and values

2.11 Updatable dictionary with mutable values

2.12 TODO Dynamic dictionary with mutable keys and values

2.13 TODO Static filter

2.14 TODO Ordered static/updatable/dynamic dictionary?

3 Summary table

endtoc

[ \newcommand{\K}{\mathbb K} \newcommand{\V}{\mathbb V} \newcommand{\c}[1]{\mathbf{\mathsf{#1}}} ]