论文Approximate_Nearest_Neighbors总结文档

1、计算机学院论文1的总结文档Approximate Nearest Neighbors:Towards Removi ng the Curse of Dime nsion ality2013/4/5目录1、介绍 31.1 近邻搜索( NNS )问题： 31.2 前人的相关工作 31.3 三个观点 42 相关概念 43 转换到 PLEB 问题 43.1 构造 Ring-Cover Trees 63.2 分析 Ring-Cover Trees 74 PLEB 74.1 The Bucketing Method 84.2 LSH ( Locality-Sensitive Hashing ) 84.3

2、PLEB 算法的其他应用 91、介绍1.1近邻搜索(NNS)问题：在度量空间X中，给定一个由n点组成的集合P=P 1,P n，以及距离函数d,对P 进行预处理，使其能有效的回答这样一个查询：找到P中与查询点q ?X最近的点。我们在Ip范数下的d-维欧几里德空间中研究该问题，其中X = Rd。在处理NNS问题时，低维问题容易解决，主要的研究问题是维数灾难”；通常，对于高维问题，以往使用的办法一般为蛮力算法，对数据查询的效率没有显著提高。已知的算法分为两种类型：预处理代价低，但查询代价较高；查询代价较低，但预处理代价高。NNS问题的应用：数据压缩(Data compression)数据库和数据挖掘

3、 (Database and data mi ning)信息检索(In formati on retrieval)多媒体数据库(Image and video databases)机器学习(Machine learning)模式识另 U (Patter n recog niti on)统计与数据分析 (Statistics and data an alysis)NNS的基本问题是实现索引和相似查询；对象(文件或者图像等)的特征被表示成d-维空间中的一个点，点间距用来度量对象相似或者不相似的程度，其中特征的数量等于空间的维度。进来，业内主要通过近似近邻搜索的方法来研究维数灾难”，通过实验和理论权

4、衡得知，我们不必要得出准确的NNS问题中所求的点，事实上，只要 ？取值合理，？ -NNS问题就能够满足大部分实际需求，因此，我们将求解NNS问题转化为求解？ -INS问题。那么，这就引出了 ？ - NNS(?-approximate nearest neighbors) 问题：对于查询点q,找到一个？近似相邻的点p ?P,其对于所有的p P?都满足以下公式： d(p,q) < (1+ ?)d(p , q).其中d(p,q)为点p与点q之间的距离1.2前人的相关工作F面列举一些前任解决高维问题时所用算法的性能:性能姓名j 、预处理时间查询时间Dobki n & Lipt on2d

5、1O(n )2 d0(n log n)Clarks on0( nd2(1)0(n d 2 (1)Agarwal et.0(nd )0(d5 log n)Meiser0(nd )0(d5 log n)1.3三个观点为了解决？ NNS问题，本文提出了 3个观点：(1) 对？ >1,存在一个算法在p?1,2的lp范数下，使其预处理时间为0(n 1+1/?+dn)，查 询时间为0(dn"?)；(2) 对于0< ? <1,存在一个算法在任意lp范数下，使其预处理时间为0(n) X 0(1/ ?), 查询时间为0(d).(3) 对于任意?>0,存在一个算法在p?1,2的l

6、p范数下，使其预处理时间为(nd)。, 查询时间为0(d);1.4文章重点(1) 将？-NNS问题转化为 ？-PLEB问题建立 ring-cover trees(2) 对点位置问题的两种算法The Bucket ing MethodLSH (locality-sensitive hashing )2相关概念lp表示在lp范数下的Rd空间M=(X,d)为度量空间d(p,P) minq P d(p,q)(P) maxp,q pd(p,q)H d(0,1, dH)表示d维汉明度量空间定义1：球心为p半径为r的球定义为B( p,r) q X |d( p,q) r;环 R(p,1,r2)定义为 Re*)

7、 q X | 几 d(p,q)叨。3转换到PLEB问题定义2:(PLEB 问题-Reduction to Point Location in Equal Balls)在度量空间 M=(X,d)中，给定n个以C=C1,c为中心，半径为r的球。对于以下查询 q ?X:如果存在ci?C有q?(ci,r),返回ci;否则返回No。定义3：(?-PLEB问题)在度量空间 M=(X,d)中，给定n个以C=C1,c为中心，半径为r的球。对于以下查询点q ?X :如果对 q?(ci ,r), ci?C,有 q?(ci ,(1+?)r)返回 Yes 和点 ci /如果 q ?(ci ,(1+?)r),则返回 N

8、o ;如果有r w d(q, c w (1+?)r则随机返回Yes或者No。从定义2和定义3易知，从NNS问题可以转换到 PLEB问题，也存在它们之间个一个 逆序转换，处理 NNS问题和PLEB问题的预处理时间和查询时间相同。这里主要问题是怎 样转换，这个转换依赖一个如1.4中提到的ring-cover trees的数据结构；对于这个ring-covertrees,有如下定义(定义4、定义5和定义6 )。定义 4： ( a 1, a 2-rin|)eparator对P来说，有环R(p, «,2)满足PB(p,rJ1 p ;P B(p,d)2Pr2 /r1=则称环 R(p, r-i,r

9、2) 是一种(a 1, a 2jng separator.定义 5: ( y , -cluster有一个集合S ?P,对于任意p S,有P B(p, (S)|P则集合S ? P为P的一个(丫，-cluster.定义 6: (b,c,d)-cover有I个集合 A1,A , Ai ?P，如果对于 A= U Ai ,S ? A，存在一个r > d 对于i=1,2,l, 有：P(Up AB(p,r)bAiAl cP贝U Ai ? P 为 S ? P 的一个(b,c,d)-cover.定理1:对任意P, 0< a <且3 >1至少满足下面两个性质中的一个:(1) P 有一个(a

10、 , aringepartor(2) P 包含一个大小至少为 (1-2 a )|P0(1/(2 3 faster.定理2:令S为P的(丫 ,3)luster,则对于任意b,存在一个算法：产生集合序列S 的(b,-(1) log b nAi,Ak ?P，构成一个对) cov er °证明思路:Algorithm Cover: S P I R(q, r, rq);(S) . n r; j 0;logb nrepeat1j j 1; choosesome Pj S; Bj g;i 1; while | P IUqBj1BB(q,r)| b|Bj|dojplUqB； BE);en dwhil

11、e;Aj ;PP AjAjBj;Suntil S ;k j.P, 0< a <1,3 >1必须满足下面两个性质之一:aringeparator R(p,r,3 r)a-ct)ver,推论1:对于任意1、P 有一个(a ,2、存在一个S ? P的(b,|S| >-21a )rfi d=1/(23 +1)log3.1 构造 Ring-Cover Trees构造Ring-Cover Trees的构造过程是递归的，对于任意给定的根节点P,我们使用推论1中的性质1和性质2把P分解成更小的集合 S1,S;这些集合是节点 P的孩子节点。令:1111 log n2(1-)，b log2

12、n，2gCase 1:称P为一个ring节点定义S仁PH B(p, 3 r), S2=P-B(p,r);在节点P上存储关于环 R(p,r,的信息。Case 2:称P为一个cover节点定义 Si=pnu pe AiB(p,r)且 So=S-A.ro=(1+1/?) (A).对每个 i?1,k, K=log i+?(1+1/?)log bn/ 丫 +1令 ri=ro/(1+?) i,对每个 ri 生成 B(p, ri)的 PLEB 实例 p ?A;将所有实例存储在P节点上。搜索过程：1、 如果P是一个ring节点，用(a , a-rjngB进行划分为S1, S2(a) 如果 q B(p,r(1+

13、1/?) , Search(q,S1)(b) 否则，计算 p' =Search(q2S,return minq(p,p ');2、如果P是一个Cover节点，由半径为r的A1,A形成的对S ? P的(b,c,d)-cover,则(a) 如果q? B(a,ro),则对于a A ,计算p=Search(q,P-A),任意选择 a A ,返回 mi nq(p,a);(b) 如果q B(a,r0),但q? B(a ' k),则在r,s上使用二分搜索，在A中找到一个关于q的？-NN 的 P,计算 p' =Search(q,-A),返回 minq(p,p ')；(c

14、) 如果对 a Ai, q B(a, rk)，然后返回 Search(q,S);3.2 分析 Ring-Cover Trees引理1：程序Search(q,P)对P中的q产生一个 ？-NN引理2：Ring-Cover Tree 的深度是 O(log 1 2 n) 0 (log 2 n)。引理3:程序Search(q,P)的距离计算或者 PLEB查询花费是0 (log 2 n) log k。引理4：忽略算法实现 PLEB的非数据存储的空间花费，一个Ring-Cover Tree的空间花费至少是 0(knblog12 n(12(12 )logn)。推论2：对于一个给定的PLEB算法，其空间花费是

15、f(n)，其中n是实例大小，f(n)的图形是凸的；对于一个有n个点的集合P, Ring-Cover Trees空间花费是 0(f(nploy log n).事实2：对于由一个 Ring-Cover Tree 产生的任意的 PLEB 实例(C,r), (C) o(1log b n)。r4 PLEB在1.4中我们提到解决-PLEB问题的两种方案，The Bucketing Method(主要用来解决 1.3中的观点2)LSH (Locality-Sensitive Hashing )(主要用来解决 1.3 中的观点 1)4.1 The Bucketi ng Method假设p=2,把一个d-维空间

16、分解成多个一致的格子grid，则任意两个点属于一个格子方块的概率至多是。对于每一个求 Bi，定义Bi是与Bi相交的格子的集合，把所有在UiBi中与球有关的元素都存储在一个哈希表中。对于01,囘 0(1)d，球半径r 2/ Jd,总的空间花费是 0(n) 0(1/ )d，查询时间是计算哈希函数的时间。我们使用下面的哈希函数：h(x1,.,xd) (a1x1 . adxd mod P) mod M其中，P是素数，M是哈希表的大小，a,.ad ZP。定理3：对于01,在I,范式下，pleb的算法预处理花费是 0(n) 0(1/ )d，查询花费是O(1)。4.2 LSH ( Locality-Sens

17、itive Hashing )定义7：对于任意q, p, p S，如果pB(q,r1)，有 PrH【h(q)h( p)pi如果pB(q2)，有 Ph h(q)h(p，) P2则称族 H h : S U是相对与 D 的(1,r2,p1,p2)-sensitive其中，必须满足一下条件，P1>p2,并且r1<r2，或者p1>p2，并且 门>2。令WbP B(q,b)，p*是P中离q最近的点；选择合适的参数 k和I使得下面的两个属性以一个恒定的概率gj成立：1、 对于所有的 p， Wr2(q)，有 gj(p，) gj(q)2、 如果 p*B(q,rJ，则 gj(p*) gj(

18、q).引理5：对于一些gi如果性质1和性质2都成立，那么搜索程序能够正确执行。定理4:假设对 D存在一个(1,r2,p1,p2)-sensitive族H，那么就存在一个在度量D下的一个(门,r2)-PLEB算法，该算法空间花费是0(d n n1 p)，查询花费是0(np)，其中，In piP2观点4:另S H d ,D(p,q)是p,q H的汉明度量空间。对于任意的r, 0 ,族H hj : hj (bj,., bd) bj,i 1 .n是一个(r, r (1),1 ,1-)sen sitive -dd推论3:对于任意的 1，在Hd空间中存在一个 PLEB算法，该算法空间花费是 O(dn n1 1/ )，每一个查询花费是 0(/ )，其中哈希函数的计算需0(d)步操作。令s是所有观点5：X 1,., x的子集的集合，D是相似度量集合，则对于1»H hF面的哈希族是(1,r2,p1,p2)-sensitive 的:h (A) max (a)， 是 X 的一个序列。a A推论4：对于0r 1，在相似度量 D条件下存在一个(r, r) PLE