On the k -Independence Required by Linear Probing and Minwise Independence

DOI10.1145/2716317zbMath1398.68118OpenAlexW2245536463MaRDI QIDQ4962205

Mihai Pǎtraşcu, Mikkel Thorup

Publication date: 30 October 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2716317

zbMATH Keywords

linear probing\(k\)-independent hashingminwise independence

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items (5)

Three‐wise independent random walks can be slightly unbounded ⋮ Engineering Practical Lempel-Ziv Tries ⋮ Universal Hashing via Integer Arithmetic Without Primes, Revisited ⋮ Unnamed Item ⋮ LZ78 Compression in Low Main Memory Space

This page was built for publication: On the k -Independence Required by Linear Probing and Minwise Independence