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

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

zbMATH Keywords

hashingcache-oblivious algorithms

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Last-come-first-served hashing
• Title not available (Why is that?)
• Optimality in external memory hashing
• Maintaining External Memory Efficient Hash Tables

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)