KIT | KIT-Bibliothek | Impressum | Datenschutz

Scalable Hash Tables

Maier, Tobias ORCID iD icon 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)

Abstract (englisch):

The term scalability with regards to this dissertation has two meanings: It means
taking the best possible advantage of the provided resources (both computational
and memory resources) and it also means scaling data structures in the literal sense,
i.e., growing the capacity, by “rescaling” the table.
Scaling well to computational resources implies constructing the fastest best per-
forming algorithms and data structures. On today’s many-core machines the best
performance is immediately associated with parallelism. Since CPU frequencies
have stopped growing about 10-15 years ago, parallelism is the only way to take ad-
vantage of growing computational resources. But for data structures in general and
hash tables in particular performance is not only linked to faster computations. The
most execution time is actually spent waiting for memory. Thus optimizing data
structures to reduce the amount of memory accesses or to take better advantage of
the memory hierarchy especially through predictable access patterns and prefetch-
ing is just as important.
In terms of scaling the size of hash tables we have identified three domains where
... mehr


Volltext §
DOI: 10.5445/IR/1000148820
Veröffentlicht am 21.07.2022
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Publikationsdatum 21.07.2022
Sprache Englisch
Identifikator KITopen-ID: 1000148820
Verlag Karlsruher Institut für Technologie (KIT)
Umfang XIII, 189 S.
Art der Arbeit Dissertation
Fakultät Fakultät für Informatik (INFORMATIK)
Institut Institut für Theoretische Informatik (ITI)
Prüfungsdatum 23.07.2021
Schlagwörter Hash tables, Scaling, Memory, Cache efficiency, Concurrency, Approximate membership query filter
Relationen in KITopen
Referent/Betreuer Sanders, Peter
Shun, Julian
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page