Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation

DOI10.1137/100800774zbMath1246.68107OpenAlexW2050026004WikidataQ56564210 ScholiaQ56564210MaRDI QIDQ2903519

Mikkel Thorup, Yin Zhang

Publication date: 10 August 2012

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/39034ba94cc6ad056fb007f5871212ce8a8553c5

zbMATH Keywords

data streamshash functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Searching and sorting (68P10) Data structures (68P05) Information storage and retrieval of data (68P20) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (13)

A unified framework for linear dimensionality reduction in L1 ⋮ Triangle counting in dynamic graph streams ⋮ Sparser Johnson-Lindenstrauss Transforms ⋮ Sample(x)=(a*x<=t) Is a Distinguisher with Probability 1/8 ⋮ Optimal (Euclidean) Metric Compression ⋮ Near-Linear Time Local Polynomial Nonparametric Estimation with Box Kernels ⋮ M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions ⋮ Universal Hashing via Integer Arithmetic Without Primes, Revisited ⋮ Unnamed Item ⋮ Simple Analyses of the Sparse Johnson-Lindenstrauss Transform. ⋮ Explicit and efficient hash families suffice for cuckoo hashing with a stash ⋮ Tracking the l_2 Norm with Constant Update Time ⋮ A count sketch maximal weighted residual Kaczmarz method for solving highly overdetermined linear systems

This page was built for publication: Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation