External-memory multimaps

DOI10.1007/978-3-642-25591-5_40zbMATH Open1274.68086arXiv1104.5533OpenAlexW1982125793MaRDI QIDQ378243FDOQ378243

Michael T. Goodrich, Justin Thaler, Michael Mitzenmacher, Elaine Angelino

Publication date: 11 November 2013

Published in: Algorithmica, Algorithms and Computation (Search for Journal in Brave)

Abstract: Many data structures support dictionaries, also known as maps or associative arrays, which store and manage a set of key-value pairs. A emph{multimap} is generalization that allows multiple values to be associated with the same key. For example, the inverted file data structure that is used prevalently in the infrastructure supporting search engines is a type of multimap, where words are used as keys and document pointers are used as values. We study the multimap abstract data type and how it can be implemented efficiently online in external memory frameworks, with constant expected I/O performance. The key technique used to achieve our results is a combination of cuckoo hashing using buckets that hold multiple items with a multiqueue implementation to cope with varying numbers of values per key. Our external-memory results are for the standard two-level memory model.

Full work available at URL: https://arxiv.org/abs/1104.5533

Recommendations

• External-memory multimaps
• Cache-oblivious dictionaries and multimaps with negligible failure probability
• scientific article; zbMATH DE number 1792106
• scientific article; zbMATH DE number 1875404
• Algorithms and data structures for external memory

zbMATH Keywords

dictionariescuckoo hashingexternal memory algorithmsmultimaps

Mathematics Subject Classification ID

Data structures (68P05) Abstract data types; algebraic specification (68Q65)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Cuckoo hashing
• Probability and Computing
• Balanced allocation and dictionaries with tightly packed constant size bins
• The limits of buffering: a tight lower bound for dynamic membership in the external memory model
• Dictionaries using variable-length keys and data, with applications
• Efficient hashing with lookups in two memory accesses
• Title not available (Why is that?)
• De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results
• Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree

Cited In (2)

• Title not available (Why is that?)
• A glimpse of complex maps with memory

Uses Software

• STL

This page was built for publication: External-memory multimaps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q378243)