KIT | KIT-Bibliothek | Impressum | Datenschutz

A Compact Cache-Efficient Function Store with Constant Evaluation Time

Zhou, Wei

Abstract:

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.


Volltext §
DOI: 10.5445/IR/1000058923
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Publikationsjahr 2013
Sprache Englisch
Identifikator urn:nbn:de:swb:90-589232
KITopen-ID: 1000058923
Verlag Karlsruher Institut für Technologie (KIT)
Art der Arbeit Abschlussarbeit - Bachelor
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page