嗨，我在试图解决这个 excersie 时不知所措。我真的很感激一些帮助！谢谢你。
定义：如果对于任何 q，p ∈ S ，哈希函数族 H = {h : X → U} 是 (r 1 , r 2 , p 1 , p 2 ) 敏感的：
• 如果 p ∈ B(q, r 1 ) 则 Pr[h(q) = h(p)] ≥ p 1（其中概率超过 h 是从 H 中均匀随机选择的）。
• 如果 p 不在 B(q, r2) 中，则 PH[h(q) = h(p)] ≤ p 2
要将 LSH 用于 ε-PLEB，我们首先固定两个参数 k，L，它们将在下面选择。对于每个 i = 1..`，我们将 P 中的每个点映射（在预处理中）到一个桶 g i (p) = (h i 1(p), . . . , h i k(p))，其中 h i 1...h i k 是从 H 中均匀随机选择的。注意，这意味着桶的数量是 |U| k，每个 p 映射到其中的 L 个。为了处理查询 q，我们搜索所有桶 g 1 (q)...g L (q)。设 p 1 ...p t是这些桶中所有点的组合。对于每个这样的 p j ，如果 p j ∈ B(q, r2) 则返回 YES 和 pĴ。否则（如果没有 p j在 B(q, r 2 ) 内）返回 NO。
现在设置 k = log 1/p2 n, l = n ρ其中 ρ = (log(1/p1))/(log(1/p2))。固定一个查询 q，并证明以下两个主张：
1.如果数据集 P 包含 p 使得 q ∈ B(p, r1)，那么至少有 1/2 的概率，p 将与 q 共享一个桶。换句话说，至少有 1/2 的概率存在 j ∈ [ ] such that g<sub>j</sub> (q) = g<sub>j</sub> (p). **2.** Define a point p to be bad for q if q 6∈ B(p, r2). Then the expected number of bad points colliding with q at some hash function g<sub>j</sub> is at most 。