Linear probing with 5-wise independence

DOI10.1137/110827831MaRDI QIDQ3115862zbMATH OpenOpenAlexFDO

Authors Anna Pagh, Rasmus Pagh, Milan Ružić

Publication date 11 February 2012

Published in SIAM Review (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/110827831

zbMATH Keywords

hashinglinear probing

Mathematics Subject Classification ID

Searching and sorting (68P10) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• Linear probing with constant independence
• On the \(k\)-independence required by linear probing and minwise independence
• On the \(k\)-independence required by linear probing and minwise independence
• Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation
• Tabulation based 5-universal hashing and linear probing

Cited in

(14)

• Linear open addressing and Peterson's theorem rehashed
• Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation
• Hashing with Linear Probing under Nonuniform Probabilities
• Linear probing with constant independence
• On the \(k\)-independence required by linear probing and minwise independence
• scientific article; zbMATH DE number 1156718 (Why is no real title available?)
• String hashing for linear probing
• Cache-oblivious hashing
• Linear probing: The probable largest search time grows logarithmically with the number of records
• On the \(k\)-independence required by linear probing and minwise independence
• Engineering practical Lempel-Ziv tries
• LZ78 compression in low main memory space
• Tabulation based 5-universal hashing and linear probing
• Advances in Computer Science - ASIAN 2004. Higher-Level Decision Making

This page was built for publication: Linear probing with 5-wise independence

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