License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.39
URN: urn:nbn:de:0030-drops-90436
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9043/
Go to the corresponding LIPIcs Volume Portal

Conway, Alex ; Farach-Colton, Martín ; Shilane, Philip

Optimal Hashing in External Memory

pdf-format:
LIPIcs-ICALP-2018-39.pdf (0.5 MB)

Abstract

Hash tables are a ubiquitous class of dictionary data structures. However, standard hash table implementations do not translate well into the external memory model, because they do not incorporate locality for insertions.
Iacono and Patrasu established an update/query tradeoff curve for external-hash tables: a hash table that performs insertions in O(lambda/B) amortized IOs requires Omega(log_lambda N) expected IOs for queries, where N is the number of items that can be stored in the data structure, B is the size of a memory transfer, M is the size of memory, and lambda is a tuning parameter. They provide a complicated hashing data structure, which we call the IP hash table, that meets this curve for lambda that is Omega(log log M + log_M N).
In this paper, we present a simpler external-memory hash table, the Bundle of Arrays Hash Table (BOA), that is optimal for a narrower range of lambda. The simplicity of BOAs allows them to be readily modified to achieve the following results:
- A new external-memory data structure, the Bundle of Trees Hash Table (BOT), that matches the performance of the IP hash table, while retaining some of the simplicity of the BOAs.
- The Cache-Oblivious Bundle of Trees Hash Table (COBOT), the first cache-oblivious hash table. This data structure matches the optimality of BOTs and IP hash tables over the same range of lambda.

BibTeX - Entry

@InProceedings{conway_et_al:LIPIcs:2018:9043,
  author =	{Alex Conway and Mart{\'i}n Farach-Colton and Philip Shilane},
  title =	{{Optimal Hashing in External Memory}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{39:1--39:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9043},
  URN =		{urn:nbn:de:0030-drops-90436},
  doi =		{10.4230/LIPIcs.ICALP.2018.39},
  annote =	{Keywords: hash tables, external memory algorthims, cache-oblivious algorithms, asymmetric data structures}
}

Keywords: hash tables, external memory algorthims, cache-oblivious algorithms, asymmetric data structures
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI