A Compact Cache-Efficient Function Store with Constant Evaluation Time

A new data structure to store a set of key-value mappings for finite static key sets
is presented. The data structure, which is called Cache-Efficient Function Stores
(CEFS), can be built in linear expected time and supports evaluation for a key within
worst-case constant time. Furthermore, (i) the building process can be parallelized
to achieve massive speed-up over known methods; (ii) an evaluation needs less than
two cache misses in average case for many applications, improving upon all known
methods. The data structure is also compact, needing only O(n) bits extra space to
be stored. The data structure is flexible in that there are many parameters that can
be configured in order to fit in specific applications. The time and space properties
for different parameters can be predicted to great precision in advance with formulae
developed in the thesis. It is also possible to automate the selection of parameters.
Experiments have shown the efficiency of the new data structure and confirmed the
theoretical analysis.