Min-Wise independent linear permutations

Tom Bohman^{∗} Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh PA15213, U.S.A.

                   E-mail:tbohman@andrew.cmu.edu

Colin Cooper^{†} School of Mathematical Sciences, University of North London, London N7 8DB, UK.

                     E-mail:c.cooper@unl.ac.uk

Alan Frieze^{‡} Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh PA15213, U.S.A.,

                  E-mail:alan@random.math.cmu.edu

Submitted: January 12, 2000; Accepted: April 23, 2000

Abstract

A set of permutations F ⊆ S_{n} is min-wise independent if for any set X ⊆ [n] and any x ∈ X, when π is chosen at random in F we have ℙ (min{π(X)} = π(x)) = \frac{1}{|X|}. This notion was introduced by Broder, Charikar, Frieze and Mitzenmacher and is motivated by an algorithm for filtering near-duplicate web documents. Linear permutations are an important class of permutations. Let p be a (large) prime and let F_{p} = {π_{a,b} : 1 ≤ a ≤ p − 1, 0 ≤ b ≤ p − 1} where for x ∈ [p] = {0, 1, …, p − 1}, π_{a,b}(x) = ax + b mod p. For X ⊆ [p] we let F (X) = max_{x∈X} {ℙ_{a,b}(min{π(X)} = π(x))} where ℙ_{a,b} is over π chosen uniformly at random from F_{p}. We show that as k, p → ∞, 𝔼_{X}[F (X)] = \frac{1}{k} +O (\frac{(log k)^{3}}{k^{3/2}} ) confirming that a simply chosen random linear permutation will suffice for an average set from the point of view of approximate min-wise independence.

∗Supported in part by NSF Grant DMS-9627408 †Research supported by the STORM Research Group ‡Supported in part by NSF grant CCR-9818411

1 Introduction

Broder, Charikar, Frieze and Mitzenmacher [3] introduced the notion of a set of min-wise independent permutations. We say that F ⊆ S_{n} is min-wise independent if for any set X ⊆ [n] and any x ∈ X, when π is chosen at random in F we have

ℙ (min\{π(X)\} = π(x)) = \frac{1}{|X|}.  (1)

The research was motivated by the fact that such a family (under some relaxations) is essential to the algorithm used in practice by the AltaVista web index software to detect and filter near-duplicate documents. A set of permutations satisfying (1) needs to be exponentially large [3]. In practice we can allow certain relaxations. First, we can accept small relative errors. We say that F ⊆ S_{n} is approximately min-wise independent with relative error ϵ (or just approximately min-wise independent, where the meaning is clear) if for any set X ⊆ [n] and any x ∈ X, when π is chosen at random in F we have

|ℙ(min\{π(X)\} = π(x)) − \frac{1}{|X|}| ≤ \frac{ϵ}{|X|}.  (2)

In other words we require that all the elements of any fixed set X have only an almost equal chance to become the minimum element of the image of X under π.

Linear permutations are an important class of permutations. Let p be a (large) prime and let F_{p} = {π_{a,b} : 1 ≤ a ≤ p − 1, 0 ≤ b ≤ p − 1} where for x ∈ [p] = {0, 1, …, p − 1},

π_{a,b}(x) = ax + b mod p,

where for integer n we define n mod p to be the non-negative remainder on division of n by p.

For X ⊆ [p] we let

F (X) = max_{x∈X} {ℙ_{a,b}(min{π(X)} = π(x))}

where ℙ_{a,b} is over π chosen uniformly at random from F_{p}. The natural questions to discuss are what are the extremal and average values of F (X) as X ranges over A_{k} = {X ⊆ [p] : |X| = k}. The following results were some of those obtained in [3]:

Theorem 1

(a) Consider the set X_{k} = {0, 1, 2 … k − 1}, as a subset of [p]. As k, p → ∞, with k^{2} = o(p),

ℙ_{a,b}(min\{π(X_{k})\} = π(0)) = \frac{3}{π^{2}} \frac{ln k}{k} + O (\frac{k^{2}}{p} + \frac{1}{k}) .

(b) As k, p → ∞, with k^{4} = o(p),

\frac{1}{2(k − 1)} ≤ 𝔼_{X}[F (X)] ≤ \frac{\sqrt{2} + 1}{\sqrt{2}k} + O (\frac{1}{k^{2}} ) ,

where 𝔼_{X} denotes expectations over X chosen uniformly at random from A_{k}.

In this paper we improve the second result and prove

Theorem 2 As k, p → ∞,

𝔼_{X}[F (X)] = \frac{1}{k} + O (\frac{(log k)^{3}}{k^{3/2}} ) .

Thus a simply chosen random linear permutation will suffice for an average set from the point of view of min-wise independence. Other results on min-wise independence have been obtained by Indyk [6], Broder, Charikar and Mitzenmacher [4] and Broder and Feige [5].

2 Proof of Theorem 2

Let X = {x_{0}, x_{1}, …, x_{k−1}} ⊆ [p]. Let β_{i} = ax_{i} mod p for i = 0, 1, …, k − 1. Let

i = i(X, a) = min{β_{0} − β_{j} mod p : j = 1, 2, …, k − 1}.  (3)

Let

A_{i} = A_{i}(X) = {a ∈ [p] : i(X, a) = i}

and note that

|A_{i}| ≤ k − 1, i = 1, 2, …, p − 1.

Then

min{π(X)} = π(x_{0}) iff 0 ∈ {β_{0} + b, β_{0} + b − 1, …, β_{0} + b − i + 1} mod p.

Thus if

Z = Z(X) = ∑_{i=1}^{p−1} i|A_{i}|,

ℙ_{a,b}(min\{π(X)\} = π(x_{0})) = \frac{Z}{p(p − 1)}.  (4)

Fix a ∈ {1, 2, …, p − 1} and x_{0}. Then

ℙ(a ∈ A_{i}) = (k − 1) · \frac{1}{p − 1} ∏_{t=1}^{k−2} (1 − \frac{i + t}{p − 1 − t})  (5)

We write Z = Z_{0} + Z_{1} where Z_{0} = ∑_{i=1}^{i_{0}} i|A_{i}| where i_{0} = \frac{4p log k}{k}. Now, by symmetry,

𝔼_{X}(ℙ_{a,b}(min\{π(X)\} = π(x_{0})) = \frac{1}{k}  (6)

and so

𝔼_{X}(Z) = \frac{p(p − 1)}{k}.

It follows from (5) that

𝔼(Z_{1}) ≤ (k − 1) ∑_{i=i_{0}+1}^{p−1} i exp \{−\frac{4(k − 2) log k}{k} \}

≤ \frac{p^{2}}{k^{3}}  (7)

for large k, p.

We continue by using the Azuma-Hoeffding Martingale tail inequality – see for example [1, 2, 7, 8, 9]. Let x_{0} be fixed and for a given X let X̂ be obtained from X by replacing x_{j} by randomly chosen x̂_{j}. For j ≥ 1 let

d_{j} = max_{X}{|𝔼x̂_{j}(Z(X) − Z(X̂))|}.

Then for any t > 0 we have

ℙ(|Z_{0} − 𝔼(Z_{0})| ≥ t) ≤ 2 exp \{−\frac{2t^{2}}{d_{1}^{2} + ⋯ + d_{k−1}^{2}} \} .  (8)

We claim that

d_{j} ≤ ∑_{i=1}^{i_{0}} i + ∑_{i=1}^{i_{0}} \frac{(k − 1)i^{2}}{p}  (9)

≤ \frac{i_{0}^{2}}{2} + \frac{i_{0}^{3}k}{3p} + O(p)
≤ \frac{30(log k)^{3}p^{2}}{k^{2}}  (10)

Explanation for (9): If a ∈ A_{i}(X) because ax_{j} = ax_{0} − i mod p then changing x_{j} to x̂_{j} changes |A_{i}| by one. This explains the first summation. The second accounts for those a ∈ A_{i}(X) for which ax_{0} − ax̂_{j} mod p < i, changing the minimum in (3). We then use |A_{i}| ≤ k − 1 and ℙ(ax_{0} − ax̂_{j} mod p < i) = \frac{i}{p}.

Using (10) in (8) with t = ε\frac{p^{2}}{k} we see that

ℙ (|Z_{0} − 𝔼(Z_{0})| ≥ ε\frac{p^{2}}{k} ) ≤ exp \{−\frac{ε^{2}k}{450(log k)^{6}} \} .

It now follows from (4), (6), (7) and the above that

𝔼_{X}[F (X)] = \frac{1}{k} + O (\frac{1}{k^{2}} + \frac{1}{k} ∫_{ε=0}^{∞} min \{1, k exp \{−\frac{ε^{2}k}{450(log k)^{6}} \}\} dε)

and the result follows. □

References

[1] N. Alon and J.H. Spencer, The Probabilistic Method, Wiley, 1992.

[2] B. Bollobás, Martingales, isoperimetric inequalities and random graphs, in Combinatorics, A. Hajnal, L. Lovász and V.T. Sós Ed., Colloq. Math. Sci. Janos Bolyai 52, North Holland 1988.

[3] A.Z. Broder, M. Charikar, A.M. Frieze and M. Mitzenmacher, Min-Wise Independent permutations, Proceedings of the 30th Annual ACM Symposium on Theory of Computing (1998) 327–336.

[4] A.Z. Broder, M. Charikar and M. Mitzenmacher, A derandomization using min-wise independent permutations, Proceedings of Second International Workshop RAN-DOM ’98 (M. Luby, J. Rolim, M. Serna Eds.) (1998) 15–24.

[5] A.Z. Broder and U. Feige, Min-Wise versus Linear Independence, Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (2000).

[6] P. Indyk, A small approximately min-wise independent family of hash-functions, Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (1999) 454–456.

[7] C.J.H. McDiarmid, On the method of bounded differences, Surveys in Combinatorics, 1989, Invited papers at the Twelfth British Combinatorial Conference, Edited by J. Siemons, Cambridge University Press, 148–188.

[8] C.J.H. McDiarmid, Concentration, Probabilistic methods for algorithmic discrete mathematics, (M.Habib, C. McDiarmid, J. Ramirez-Alfonsin, B. Reed, Eds.), Springer (1998) 195–248.

[9] M.J. Steele, Probability theory and combinatorial optimization, CBMS-NSF Regional Conference Series in Applied Mathematics 69, 1997.