2014/11/26 by Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Dahlgaard, Søren +5
Computer Science · #Advanced Image and Video Retrieval Techniques #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #cs.DS
paper · pdf · doi:10.48550/arxiv.1411.7191
Appear at FOCS'15
openalex publication_date 2014/11/26 · arxiv created 2016/02/15 · arxiv updated 2016/02/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we analyze a hash function for k-partitioning a set into bins, obtaining strong concentration bounds for standard algorithms combining statistics from each bin. This generic method was originally introduced by Flajolet and Martin~[FOCS'83] in order to save a factor Ω(k) of time per element over k independent samples when estimating the number of distinct elements in a data stream. It was also used in the widely used HyperLogLog algorithm of Flajolet et al.~[AOFA'97] and in large-scale machine learning by Li et al.~[NIPS'12] for minwise estimation of set similarity. The main issue of k-partition, is that the contents of different bins may be highly correlated when using popular hash functions. This means that methods of analyzing the marginal distribution for a single bin do not apply. Here we show that a tabulation based hash function, mixed tabulation, does yield strong concentration bounds on the most popular applications of k-partitioning similar to those we would get using a truly random hash function. The analysis is very involved and implies several new results of independent interest for both simple and double tabulation, e.g. a simple and efficient construction for invertible bloom filters and uniform hashing on a given set.