Cache-oblivious hashing

DOI10.1007/S00453-013-9763-6zbMATH Open1307.68032OpenAlexW2048064086MaRDI QIDQ472489FDOQ472489

Authors Rasmus Pagh, Zhewei Wei, Ke Yi, Qin Zhang

Publication date 19 November 2014

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-013-9763-6

zbMATH Keywords

hashingcache-oblivious algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05) Searching and sorting (68P10) Database theory (68P15)

Recommendations

• Optimal hashing in external memory
• Optimality in external memory hashing
• Maintaining External Memory Efficient Hash Tables
• Linear probing with constant independence
• Linear probing with 5-wise independence

Cites work

• scientific article; zbMATH DE number 989379 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Cache-Oblivious B-Trees
• Cache-oblivious range reporting with optimal queries requires superlinear space
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Cuckoo hashing
• Linear probing with 5-wise independence
• New hash functions and their use in authentication and set equality
• On the limits of cache-obliviousness
• Optimality in external memory hashing
• The cost of cache-oblivious searching
• The effect of table expansion on the program complexity of perfect hash functions
• The limits of buffering: a tight lower bound for dynamic membership in the external memory model
• Universal classes of hash functions

Cited in

(5)

• Maintaining External Memory Efficient Hash Tables
• Optimal hashing in external memory
• Last-come-first-served hashing
• Optimality in external memory hashing
• scientific article; zbMATH DE number 2011837 (Why is no real title available?)

This page was built for publication: Cache-oblivious hashing

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