Document Open Access Logo

Dynamic Space Efficient Hashing

Authors Tobias Maier, Peter Sanders

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.58.pdf
  • Filesize: 1.03 MB
  • 14 pages

Document Identifiers

Author Details

Tobias Maier
Peter Sanders

Cite As Get BibTex

Tobias Maier and Peter Sanders. Dynamic Space Efficient Hashing. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.58

Abstract

We consider space efficient hash tables that can grow and shrink dynamically and are always highly space efficient, i.e., their space consumption is always close to the lower bound even while growing and when taking into account storage that is only needed temporarily. None of the traditionally used hash tables have this property. We show how known approaches like linear probing and bucket cuckoo hashing can be adapted to this scenario by subdividing them into many subtables or using virtual memory overcommitting. However, these rather straightforward solutions suffer from slow amortized insertion times due to frequent reallocation in small increments.

Our main result is DySECT (Dynamic Space Efficient Cuckoo Table) which avoids these problems. DySECT consists of many subtables which grow by doubling their size. The resulting inhomogeneity in subtable sizes is equalized by the flexibility available in bucket cuckoo hashing where each element can go to several buckets each of which containing several cells. Experiments indicate that DySECT works well with load factors up to 98%. With up to 2.7 times better performance than the next best solution.

Subject Classification

Keywords
  • Dynamic data structures
  • open addressing
  • closed hashing
  • cuckoo hashing
  • space efficiency

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Yuriy Arbitman, Moni Naor, and Gil Segev. De-amortized cuckoo hashing: Provable worst-case performance and experimental results. In International Conference on Automata, Languages and Programming (ICALP), number 5555 in LNCS, pages 107-118. Springer, 2009. Google Scholar
  2. Pedro Celis, Per-Ake Larson, and J. Ian Munro. Robin hood hashing. In 26th Symposium on Foundations of Computer Science (FOCS), pages 281-288, Oct 1985. Google Scholar
  3. Luc Devroye and Pat Morin. Cuckoo hashing: Further analysis. Information Processing Letters, 86(4):215-219, 2003. Google Scholar
  4. Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, and Michael Rink. Tight thresholds for cuckoo hashing via XORSAT. In 27th International Conference on Automata, Languages and Programming (ICALP), pages 213-225, 2010. Google Scholar
  5. Martin Dietzfelbinger, Anna Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert, and Robert E. Tarjan. Dynamic perfect hashing: Upper and lower bounds. SIAM Journal on Computing, 23(4):738-761, 1994. Google Scholar
  6. Martin Dietzfelbinger, Michael Mitzenmacher, and Michael Rink. Cuckoo hashing with pages. In 19th European Symposium on Algorithms (ESA), number 6942 in LNCS, pages 615-627. Springer, 2011. Google Scholar
  7. Martin Dietzfelbinger and Christoph Weidling. Balanced allocation and dictionaries with tightly packed constant size bins. Theoretical Computer Science, 380(1):47-68, 2007. Google Scholar
  8. Dimitris Fotakis, Rasmus Pagh, Peter Sanders, and Paul Spirakis. Space efficient hash tables with worst case constant access time. Theory of Computing Systems, 38(2):229-248, 2005. Google Scholar
  9. Nikolaos Fountoulakis, Konstantinos Panagiotou, and Angelika Steger. On the insertion time of cuckoo hashing. SIAM Journal on Computing, 42(6):2156-2181, 2013. Google Scholar
  10. Alan Frieze, Páll Melsted, and Michael Mitzenmacher. An analysis of random-walk cuckoo hashing. SIAM Journal on Computing, 40(2):291-308, 2011. Google Scholar
  11. Leo J. Guibas and Endre Szemeredi. The analysis of double hashing. Journal of Computer and System Sciences, 16(2):226-274, 1978. Google Scholar
  12. Adam Kirsch and Michael Mitzenmacher. Less hashing, same performance: Building a better bloom filter. In Yossi Azar and Thomas Erlebach, editors, 14th European Symposium on Algorithms (ESA), number 4168 in LNCS, pages 456-467. Springer, 2006. Google Scholar
  13. Adam Kirsch and Michael Mitzenmacher. Using a queue to de-amortize cuckoo hashing in hardware. In 45th Annual Allerton Conference on Communication, Control, and Computing, volume 75, 2007. Google Scholar
  14. Donald E. Knuth. The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998. Google Scholar
  15. Xiaozhou Li, David G. Andersen, Michael Kaminsky, and Michael J. Freedman. Algorithmic improvements for fast concurrent cuckoo hashing. In 9th European Conference on Computer Systems, EuroSys'14, pages 27:1-27:14. ACM, 2014. Google Scholar
  16. M. Mitzenmacher. The power of two choices in randomized load balancing. IEEE Transactions on Parallel and Distributed Systems, 12(10):1094-1104, Oct 2001. Google Scholar
  17. Michael Mitzenmacher. Some open questions related to cuckoo hashing. In Amos Fiat and Peter Sanders, editors, 17th European Symposium on Algorithms (ESA), volume 5757 of LNCS, pages 1-10. Springer, 2009. Google Scholar
  18. N. Nguyen and P. Tsigas. Lock-free cuckoo hashing. In 2014 IEEE 34th International Conference on Distributed Computing Systems (ICDCS), pages 627-636, June 2014. Google Scholar
  19. Rasmus Pagh and Flemming Friche Rodler. Cuckoo hashing. Journal of Algorithms, 51(2):122-144, 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact