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

DOI10.1007/978-3-662-48350-3_69MaRDI QIDQ3452844zbMATH OpenOpenAlexFDO

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

Publication date 19 November 2015

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

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

Mathematics Subject Classification ID

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

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})$.

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

Cites work

• scientific article; zbMATH DE number 5485466 (Why is no real title available?)
• scientific article; zbMATH DE number 1305436 (Why is no real title available?)
• scientific article; zbMATH DE number 1559562 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 1445340 (Why is no real title available?)
• A Reliable Randomized Algorithm for the Closest-Pair Problem
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• From independence to expansion and back again
• Introduction to algorithms
• Min-wise independent permutations
• On Universal Classes of Extremely Random Constant-Time Hash Functions
• Randomized algorithms and pseudorandom numbers
• Universal classes of hash functions

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)