✦ LIBER ✦
A Small Approximately Min-Wise Independent Family of Hash Functions
✍ Scribed by Piotr Indyk
- Publisher
- Elsevier Science
- Year
- 2001
- Tongue
- English
- Weight
- 73 KB
- Volume
- 38
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
In this paper we give a construction of a small approximately min-wise independent family of hash functions, i.e., a family of hash functions such that for any set of arguments X and x ∈ X, the probability that the value of a random function from that family on x will be the smallest among all values of that function on X is roughly 1/ X . The number of bits needed to represent each function is O log n • log 1/ . This construction gives a solution to the main open problem of A. Broder et al. (in "STOC'98").