Quicksort, largest bucket, and min-wise hashing with limited independence

DOI10.1007/978-3-662-48350-3_69zbMATH Open1467.68213arXiv1502.05729OpenAlexW1802575925MaRDI QIDQ3452844FDOQ3452844

Authors: Mathias Bæk Tejs Knudsen, Morten Stöckel 

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Abstract: Randomized algorithms and data structures are often analyzed under the assumption of access to a perfect source of randomness. The most fundamental metric used to measure how "random" a hash function or a random number generator is, is its independence: a sequence of random variables is said to be $k$-independent if every variable is uniform and every size $k$ subset is independent. In this paper we consider three classic algorithms under limited independence. We provide new bounds for randomized quicksort, min-wise hashing and largest bucket size under limited independence. Our results can be summarized as follows. -Randomized quicksort. When pivot elements are computed using a $5$-independent hash function, Karloff and Raghavan, J.ACM'93 showed $O(nlogn)$ expected worst-case running time for a special version of quicksort. We improve upon this, showing that the same running time is achieved with only $4$-independence. -Min-wise hashing. For a set $A$, consider the probability of a particular element being mapped to the smallest hash value. It is known that $5$-independence implies the optimal probability $O(1/n)$. Broder et al., STOC'98 showed that $2$-independence implies it is $O(1/sqrt|A|)$. We show a matching lower bound as well as new tight bounds for $3$- and $4$-independent hash functions. -Largest bucket. We consider the case where $n$ balls are distributed to $n$ buckets using a $k$-independent hash function and analyze the largest bucket size. Alon et. al, STOC'97 showed that there exists a $2$-independent hash function implying a bucket of size $Omega(n^{1/2})$. We generalize the bound, providing a $k$-independent family of functions that imply size $Omega(n^{1/k})$.

Full work available at URL: https://arxiv.org/abs/1502.05729

Recommendations

• On the \(k\)-independence required by linear probing and minwise independence
• On the \(k\)-independence required by linear probing and minwise independence
• Balls and bins: smaller hash families and faster evaluation
• scientific article; zbMATH DE number 1445297

Mathematics Subject Classification ID

Randomized algorithms (68W20) Data structures (68P05) Searching and sorting (68P10)

Cites Work

• Introduction to algorithms
• A Reliable Randomized Algorithm for the Closest-Pair Problem
• Universal classes of hash functions
• On Universal Classes of Extremely Random Constant-Time Hash Functions
• Title not available (Why is that?)
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Title not available (Why is that?)
• Title not available (Why is that?)
• Min-wise independent permutations
• From independence to expansion and back again
• Randomized algorithms and pseudorandom numbers
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (2)

• On the \(k\)-independence required by linear probing and minwise independence
• On the \(k\)-independence required by linear probing and minwise independence

This page was built for publication: Quicksort, largest bucket, and min-wise hashing with limited independence

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