0. Intro \textbf{0. Intro} 0. Intro
1️⃣ LSH \text{LSH} LSH的优势:在 λ \lambda{} λ较大的度量空间,也可以高效回答 c-ANN \text{c-ANN} c-ANN查询问题
2️⃣一些预备知识
- 多重集并集 (multi-set union): \text{(multi-set union): } (multi-set union): 和普通并集相比区别在于保留重复项
- 比如 Z 1 = { a , b } 和 Z 2 = { b , c } Z 1 ⇒ Z 1 ∪ Z 2 = { a , b , b , c } Z_1 = \{a, b\}和Z_2 = \{b, c\}Z_1 \Rightarrow{}Z_1\cup Z_2 = \{a, b, b,c\} Z1={a,b}和Z2={b,c}Z1⇒Z1∪Z2={a,b,b,c}
- Markov \text{Markov} Markov不等式: Pr [ X ≥ t ⋅ E [ X ] ] ≤ 1 t \text{Pr}[X \geq t \cdot \mathbf{E}[X]] \leq \frac{1}{t} Pr[X≥t⋅E[X]]≤t1
1. ( r , c ) -Near Neighbor Search \textbf{1. }(r,c)\textbf{-Near Neighbor Search} 1. (r,c)-Near Neighbor Search
1️⃣ ( r , c ) -NN (r,c)\text{-NN} (r,c)-NN概念
r ≥ 1 r \geq 1 r≥1且 c > 1 c > 1 c>1, S ⊆ U S\subseteq{}U S⊆U且 ∣ S ∣ = n |S|=n ∣S∣=n , q ∈ U q \in U q∈U
( r , c ) -NN (r,c)\text{-NN} (r,c)-NN查询返回:令 D =dist ( q , e i ) D\text{=dist}(q,e_i) D=dist(q,ei)
Case \textbf{Case} Case ∃ e i 使 D ∈ [ 0 , r ] \exist{}e_i使D\in[0,r] ∃ei使D∈[0,r] ∃ e i 使 D ∈ [ r , c r ] \exist{}e_i使D\in{}[r,cr] ∃ei使D∈[r,cr] ∃ e i 使 D ∈ [ c r , ∞ ] \exist{}e_i使D\in[cr,\infin{}] ∃ei使D∈[cr,∞] 返回对象 Case 1 \text{Case 1} Case 1 一定 可能 可能 满足 D ≤ c r D\leq{cr} D≤cr的 e i e_i ei Case 2 \text{Case 2} Case 2 不可能 不可能 不可能 返回寂寞 Case 3 \text{Case 3} Case 3 不可能 一定 可能 满足 D ≤ c r D\leq{cr} D≤cr的 e i e_i ei 2️⃣引理:按以下步骤,可回答 S S S上所有 c 2 -ANN c^{2}\text{-ANN} c2-ANN查询
- 条件:对任意 r ≥ 1 r \geq 1 r≥1和 c > 1 c > 1 c>1,我们已经知道了如何在 S S S上构建结构来回答 ( r , c ) -NN (r,c)\text{-NN} (r,c)-NN查询
- 步骤:
- 构建 O ( log diam ( S ) ) O(\log \text{diam}(S)) O(logdiam(S))个这样的结构
- 发起 O ( log diam ( S ) ) O(\log \text{diam}(S)) O(logdiam(S))个 ( r , c ) -NN (r,c)\text{-NN} (r,c)-NN查询 ( c c c相同但 r r r不同)
2. Locality Sensitive Hashing \textbf{2. Locality Sensitive Hashing} 2. Locality Sensitive Hashing
1️⃣局部敏感哈希函数定义:核心思想就是将相似的点映射进同一桶,不相似的点映射到不同桶
- 前提
- 设 r / c / p 1 / p 2 r/c/p_1/p_2 r/c/p1/p2满足 r ≥ 1 / c > 1 / 0 < p 2 < p 1 ≤ 1 r\geq{}1/c>1/0 < p_2 < p_1 \leq 1 r≥1/c>1/0<p2<p1≤1
- h h h是根据某种分布从函数族 H H H中抽取的函数
- 随机函数 h : U → N h\text{: }U \rightarrow \mathbb{N} h: U→N是 ( r , c r , p 1 , p 2 ) -LSH \left(r, cr, p_1, p_2\right)\text{-LSH} (r,cr,p1,p2)-LSH函数,需满足
- ∀ x , y ∈ U → { dist ( x , y ) ≤ r ⇒ Pr [ h ( x ) = h ( y ) ] ≥ p 1 dist ( x , y ) > c r ⇒ Pr [ h ( x ) = h ( y ) ] ≤ p 2 \forall{}x,y\in{}U\to{}\begin{cases}\text{dist}(x, y) \leq r\Rightarrow{}\text{Pr}[h(x) = h(y)] \geq p_1\\\\\text{dist}(x, y) > cr\Rightarrow{}\text{Pr}[h(x) = h(y)] \leq p_2\end{cases} ∀x,y∈U→⎩ ⎨ ⎧dist(x,y)≤r⇒Pr[h(x)=h(y)]≥p1dist(x,y)>cr⇒Pr[h(x)=h(y)]≤p2
- 即两个数据靠得近( ≤ r \leq{}r ≤r),哈希冲突到一个桶的概率就大;靠的远( > c r >cr >cr)则概率就小
- 此外定义 ( r , c r , p 1 , p 2 ) -LSH \left(r, cr, p_1, p_2\right)\text{-LSH} (r,cr,p1,p2)-LSH函数的对数比值为 ρ = ln ( 1 p 1 ) ln ( 1 p 2 ) = ln p 1 ln p 2 < 1 \rho = \cfrac{\ln \left(\cfrac{1}{p_1}\right)}{\ln \left(\cfrac{1}{p_2}\right)}=\cfrac{\ln{}p_1}{\ln{}p_2}<1 ρ=ln(p21)ln(p11)=lnp2lnp1<1
2️⃣放大引理:若已知如何获得 ( r , c r , p 1 , p 2 ) -LSH \left(r, cr, p_1, p_2\right)\text{-LSH} (r,cr,p1,p2)-LSH函数 h h h则 ∀ int ℓ ≥ 1 \forall{\text{int }}\ell \geq 1 ∀int ℓ≥1有 ( r , c r , p 1 ℓ , p 2 ℓ ) -LSH \left(r, cr, p_1^{\ell}, p_2^{\ell}\right)\text{-LSH} (r,cr,p1ℓ,p2ℓ)-LSH函数 g g g使
- ∀ x , g ( x ) \forall{}x,g(x) ∀x,g(x)计算复杂度是 h ( x ) h(x) h(x)的 O ( ℓ ) O(\ell) O(ℓ)倍
- g ( x ) g(x) g(x)空间复杂度为 O ( ℓ ) O(\ell) O(ℓ)
3️⃣ LHS \text{LHS} LHS实例: ( N d , dist=Euclidean ) \left(\mathbb{N}^d,\text{dist=Euclidean})\right. (Nd,dist=Euclidean)的 ( r , c r , p 1 , p 2 ) -LSH \left(r, cr, p_1, p_2\right)\text{-LSH} (r,cr,p1,p2)-LSH函数
- 构建
- 生成 d d d个随机变量 α 1 α 2 . . . α d \alpha_1\alpha_2...\alpha_d α1α2...αd且 α i ∼ N ( 0 , 1 ) \alpha_i\sim{}N(0,1) αi∼N(0,1)
- 令 β > 0 \beta > 0 β>0依赖于 c c c, γ \gamma γ在 [ 0 , β ] [0, \beta] [0,β]中均匀随机生成
- ∀ x ∈ N d \forall{}x\in\mathbb{N}^d ∀x∈Nd定义 h ( x ) = [ γ + ∑ i = 1 d ( α i ⋅ x [ i ] r ) β ] h(x)=\textbf{[}\cfrac{\gamma+\displaystyle\sum\limits_{i=1}^d\left(\cfrac{\alpha_i \cdot x[i]}{r}\right)}{\beta}\textbf{]} h(x)=[βγ+i=1∑d(rαi⋅x[i])]
- 性质: p 2 p_2 p2是一个常数,该函数的对数比值 ρ ≤ 1 c \rho\leq\cfrac{1}{c} ρ≤c1
3. A Structure for ( r , c ) -NN Search \textbf{3. A Structure for }(r,c)\textbf{-NN Search} 3. A Structure for (r,c)-NN Search
3.0. Inro \textbf{3.0. Inro} 3.0. Inro
1️⃣一些前置条件
- S ⊆ U ( ∣ S ∣ = n ) S\subseteq{}U\,(|S|=n) S⊆U(∣S∣=n)
- 若能够构建 ρ \rho ρ的 ( r , c r , p 1 , p 2 ) -LSH \left(r, cr, p_1, p_2\right)\text{-LSH} (r,cr,p1,p2)-LSH函数,该结构用于在 S S S上回答 ( r , c ) -NN (r,c)\text{-NN} (r,c)-NN查询
- 记 t l s h t_{lsh} tlsh为评估 ( r , c r , p 1 , p 2 ) -LSH \left(r, cr, p_1, p_2\right)\text{-LSH} (r,cr,p1,p2)-LSH函数值所需时间
2️⃣需要证明的定理:存在这样一种结构
- 复杂度:
- 空间复杂度:使用 O ( n 1 + ρ ⋅ log 1 p 2 n ) O\left(n^{1+\rho} \cdot \log_{\frac{1}{p_2}} n\right) O(n1+ρ⋅logp21n)个内存单元 + + +存储 O ( n 1 + ρ ) O\left(n^{1+\rho}\right) O(n1+ρ)个对象
- 时间复杂度:查询耗时 O ( n ρ ⋅ log 1 p 2 n ⋅ t l s h ) + O\left(n^\rho \cdot \log_{\frac{1}{p_2}} n \cdot t_{lsh}\right)+ O(nρ⋅logp21n⋅tlsh)+计算距离耗时 O ( n ρ ) O\left(n^\rho\right) O(nρ)
- 效果:能够至少以 1 10 \cfrac{1}{10} 101的概率,正确回答一次 ( r , c ) -NN (r,c)\text{-NN} (r,c)-NN查询
3.1. Structure \textbf{3.1. Structure} 3.1. Structure
1️⃣哈希函数 g 1 g 2 . . . g L g_1g_2...g_L g1g2...gL:令 ℓ ≥ 1 \ell \geq 1 ℓ≥1和 L ≥ 1 L \geq 1 L≥1为待定的整数,则
- 由函数 h : ( r , c r , p 1 , p 2 ) -LSH h\text{:}\left(r, cr, p_1, p_2\right)\text{-LSH} h:(r,cr,p1,p2)-LSH放大到为 L L L个独立函数 → { g 1 : ( r , c r , p 1 , p 2 ) -LSH g 2 : ( r , c r , p 1 2 , p 2 2 ) -LSH . . . . . . . g ℓ : ( r , c r , p 1 ℓ , p 2 ℓ ) -LSH . . . . . . . g L : ( r , c r , p 1 L , p 2 L ) -LSH \to\begin{cases}g_1\text{:}\left(r, cr, p_1, p_2\right)\text{-LSH}\\\\g_2\text{:}\left(r, cr, p_1^2, p_2^2\right)\text{-LSH}\\\\\,\,\,\,\,\,\,\,\text{. . . . . . . }\\g_{\ell}\text{:}\left(r, cr, p_1^{\ell}, p_2^{\ell}\right)\text{-LSH}\\\\\,\,\,\,\,\,\,\,\text{. . . . . . . }\\\\g_L\text{:}\left(r, cr, p_1^L, p_2^L\right)\text{-LSH}\end{cases} →⎩ ⎨ ⎧g1:(r,cr,p1,p2)-LSHg2:(r,cr,p12,p22)-LSH. . . . . . . gℓ:(r,cr,p1ℓ,p2ℓ)-LSH. . . . . . . gL:(r,cr,p1L,p2L)-LSH
2️⃣桶定义:让所有 x ∈ S x\in{}S x∈S通过所有哈希函数 g i g_i gi算出哈希值,所有哈希值相同的 x x x分到一个桶里
3️⃣哈希表: T i T_i Ti收集了由 g i g_i gi哈希出来的若干非空桶,一共 L L L张哈希表 T 1 , … , T L T_1, \ldots, T_L T1,…,TL 构成了我们的结构
- 空间消耗: { 内存单元: O ( n ⋅ L ⋅ ℓ ) 对象: O ( n ⋅ L ) → \small\begin{cases}内存单元\text{: }O(n \cdot L \cdot \ell)\\\\对象\text{: }O(n \cdot L)\end{cases}\to{} ⎩ ⎨ ⎧内存单元: O(n⋅L⋅ℓ)对象: O(n⋅L)→令 { ℓ = log 1 p 2 n L = n ρ → \begin{cases}\ell{}=\log_{\frac{1}{p_2}}n\\\\L=n^{\rho}\end{cases}\to{} ⎩ ⎨ ⎧ℓ=logp21nL=nρ→空间复杂度符合 Intro \text{Intro} Intro中的定理
3.2. Query \textbf{3.2. Query } 3.2. Query
1️⃣查询信息:对 q ∈ U / S q\in{U\text{/}S} q∈U/S执行 ( r , c ) -NN (r,c)\text{-NN} (r,c)-NN查询
2️⃣查询步骤
- 让 q q q分别通过 g 1 g 2 . . . g L g_1g_2...g_L g1g2...gL哈希函数,分别被分进桶 g 1 ( q ) g 2 ( q ) . . . g L ( q ) g_1(q)g_2(q)...g_L(q) g1(q)g2(q)...gL(q)记作 b 1 b 2 . . . b L b_1b_2...b_L b1b2...bL
- 让 Z = Z= Z= 在 b 1 b 2 . . . b L b_1b_2...b_L b1b2...bL的多重集并集中任选 2 L + 1 2L+1 2L+1个
- 特殊情况:如果 ∑ i = 1 L ∣ b i ∣ ≤ 4 L + 1 \displaystyle\sum_{i=1}^L |b_i| \leq 4L+1 i=1∑L∣bi∣≤4L+1,则 Z Z Z会包括所有桶的所有对象
- 在 Z Z Z中找到距 q q q最近的对象 e e e,若 dist ( q , e ) ≤ c r \text{dist}(q, e) \leq cr dist(q,e)≤cr则返回 e e e
3️⃣查询时间: { 原子操作: O ( t l s h ⋅ ℓ ⋅ L ) 计算距离: O ( L ) → \small\begin{cases}原子操作\text{: }O\left(t_{lsh} \cdot \ell \cdot L\right)\\\\计算距离\text{: }O(L)\end{cases}\to{} ⎩ ⎨ ⎧原子操作: O(tlsh⋅ℓ⋅L)计算距离: O(L)→令 { ℓ = log 1 p 2 n L = n ρ → \begin{cases}\ell{}=\log_{\frac{1}{p_2}}n\\\\L=n^{\rho}\end{cases}\to{} ⎩ ⎨ ⎧ℓ=logp21nL=nρ→时间复杂度符合 Intro \text{Intro} Intro中的定理
3.3. Analysis \textbf{3.3. Analysis } 3.3. Analysis
0️⃣ Good \text{Good} Good的标准: x ∈ S x\in{S} x∈S是 good ⇔ dist ( q , x ) ≤ c r \text{good}\xLeftrightarrow{}\text{dist}(q, x) \leq c r good dist(q,x)≤cr 否则就为 Bad \text{Bad} Bad,算法至少返回一个 good \text{good} good才成功
1️⃣引理 1 : 1\text{: } 1: 查询能被正确回答,需要满足以下两个条件
- C 1 : \mathbf{C 1:} C1: e ∗ e^* e∗至少出现在 b 1 , … , b L b_1, \ldots, b_L b1,…,bL中的一个
- C 2 : \mathbf{C 2:} C2: b 1 b 2 . . . b L b_1b_2...b_L b1b2...bL的多重集并集中,至少含有 2 L 2L 2L个 bad \text{bad} bad对象
2️⃣引理 2 2 2: C 1 \mathbf{C 1} C1不成立的概率小于 1 e \cfrac{1}{e} e1,即 Pr [ e ∗ ∉ ⋃ i = 1 L b i ] ≤ 1 e \text{Pr}\left[e^* \notin \displaystyle\bigcup\limits_{i=1}^L b_i\right]\leq{}\cfrac{1}{e} Pr[e∗∈/i=1⋃Lbi]≤e1 ,其中这个 e = 2.718... e=2.718... e=2.718...
3️⃣引理 3 3 3: C 2 \mathbf{C 2} C2不成立的概率小于 1 2 \cfrac{1}{2} 21
🤕所以 C 1 \mathbf{C}1 C1和 C 2 \mathbf{C}2 C2同时成立的概率至少为 1 − ( 1 e + 1 2 ) > 0.1 1-(\cfrac{1}{e}+\cfrac{1}{2})>0.1 1−(e1+21)>0.1