近似最近邻归约问题在泊松点过程上的再研究.pdf

近似最近邻归约问题在泊松点过程上的再研究*马恒钊1,3,闫跃2,李建中11(哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨150001)2(哈尔滨金融学院计算机系,黑龙江哈尔滨150001)3(中国科学院深圳先进技术研究院先进计算与数字工程研究所,广东深圳518055)通信作者:李建中,E-mail:1+O(logn)O(d/)d)O(nlogn)O(nlogn)O(logn)摘要:在已发表文献中,研究了基于图灵归约求解-NN 的问题,即给定查询点 q、点集 P 及近似参数,找到 q在 P 中近似比不超过的近似最近邻,并提出了一个具有查询时间复杂度的图灵归约算法,这里的查询时间是调用神谕的次数.经过对比,此时间优于所有现存的归约算法.但是已发表文献中提出的归约算法的缺点在于,其预处理时间和空间复杂度中有的因子,当维度数 d 较大或者近似参数较小时,此因子将变得不可接受.因此,重新研究了该归约算法,在输入点集服从泊松点过程的情况下,分析算法的期望时间和空间复杂度,将算法的期望预处理时间复杂度降到,期望空间复杂度降到,而期望查询时间复杂度保持不变,从而完成了在已发表文献中所提出的未来工作.关键词:近似最近邻;归约;泊松点过程;复杂度中图法分类号:TP311中文引用格式:马恒钊,闫跃,李建中.近似最近邻归约问题在泊松点过程上的再研究.软件学报,2023,34(10):48214829.http:/ Algorithm Based on Turing Reduction for Solving-NN in Possion Point ProcessMAHeng-Zhao1,3,YANYue2,LIJian-Zhong11(SchoolofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin150001,China)2(DepartmentofComputerScience,HarbinFinanceUniversity,Harbin150001,China)3(Institute of Advanced Computing and Digital Engineering,Shenzhen Institute of Advanced Technology,Chinese Academy of Sciences,Shenzhen518055,China)Abstract:Inapublishedstudy,theproblemofusingTuringreductiontosolve-NNisstudied.Inotherwords,givenaquerypointq,apointsetP,andanapproximatefactor,thepurposeistoreturntheapproximatenearestneighborofqinPwithanapproximationratioofnotmorethan1+.Moreover,aTuringreductionalgorithmwithO(logn)querytimecomplexityisproposed,wherethequerytimeisthenumberoftimesthattheoracleisinvoked.ThecomparisonindicatesthattheO(logn)querytimeisthelowestcomparedtothatofalltheexistingalgorithms.However,thedisadvantageoftheproposedalgorithmisthatthereisafactorofO(d/)d)inthepreprocessingtimecomplexity and space complexity.When the number of dimensions d is high,or the approximation factor is small,the factor wouldbecome unacceptable.Therefore,this study revises the reduction algorithm and analyzes the expected time complexity and spacecomplexity of the algorithm when the input point set follows the Poisson point process.As a result,the expected preprocessing timecomplexityisreducedtoO(nlogn),andtheexpectedspacecomplexityisreducedtoO(nlogn),whiletheexpectedquerytimecomplexityremainsO(logn).Inthissense,thefutureworkraisedinthepublishedstudyiscompleted.Key words:approximatenearestneighbor;reduction;Poissonpointprocess;complexity*基金项目:国家自然科学基金(61732003,61832003,U1811461)收稿时间:2020-09-06;修改时间:2020-10-30;采用时间:2022-01-29;jos 在线出版时间:2023-01-18CNKI 网络首发时间:2023-01-19软件学报ISSN1000-9825,CODENRUXUEWE-mail:Journal of Software,2023,34(10):48214829doi:10.13328/ki.jos.006649http:/中国科学院软件研究所版权所有.Tel:+86-10-62562563 1 前言O(logn)(1+)rrc 1Rdlkp=(p(1),.,p(d)q=(q(1),.,q(d)D(p,q)=di=1|p(i)q(i)|k1/k在文献 1 中,我们提出了从-NN 到(c,r)-NN 的一种时间的图灵归约,给出了一种高效的求解-NN问题的算法.这里,-NN 是近似最近邻问题,定义如下:给定点集 P、查询点 q 以及近似因子,输出一个距离 q不超过的点,其中,是 q 到 P 中最近的点的距离.(c,r)-NN 是近似近邻问题,定义如下:给定点集 P、查询点 q、查询范围 r 和近似因子,输出满足以下条件:若存在 p 使得 p 到 q 的距离不超过 r,则返回 P 中某一个距离 q 不超过 cr 的点;若 P 中所有点距离 q 都超过 cr,则返回否定答案 No.在以上定义中,所有的点都来自于,即每个输入点都是 d 维的向量,而距离用距离来表达,即两个点,之间的距离为.O(logn)O(logn)O(d/)dnlogn)O(d/)dn)O(d/)d)文献 1 中的算法的查询时间复杂度为,即调用神谕的次数或调用(c,r)-NN 算法的次数为.在文献 1 中我们已经证明,该算法的查询时间复杂度优于所有现存算法24.但是,文献 1 中算法的预处理时间复杂度为,空间复杂度为.若将 d 视为常数,则此算法的复杂度接近文献 5 中提出的最优复杂度.然而在维数 d 比较高或比较小的情况下,的因子将变得不可接受.因此,在文献 1 中,我们提出未来的工作是降低此因子.O(d/)d)O(d/)dnlogn)O(nlogn)O(nlogn)本文延续文献 1 的工作,解决降低算法预处理时间复杂度及空间复杂度中因子的问题.实际上,此因子的出现是因为文献 1 中分析的是最坏复杂度.本文的研究结果表明,当输入点集服从泊松点过程的情况下,算法的期望预处理时间复杂度从降低到,而且算法的期望空间复杂度为,与 d和独立.现介绍本文的贡献如下.(1)本文针对输入点集服从泊松点过程的情况,提出了不同于文献 1 中的算法,并分析了算法的正确性和时空复杂度.O(nlogn)O(nlogn)O(d/)d)(2)本文提出的算法的期望预处理时间复杂度为,期望空间复杂度为,在移除了因子的同时,仍保持比较低的复杂度.O(logn)(3)本文提出的算法的期望查询时间复杂度仍为,与文献 1 中的算法相同.本文第 1 节的其余部分介绍相关工作.第 2 节介绍预备知识及问题定义.第 3 节介绍本文提出的算法.第 4 节证明本文算法的正确性,并分析其时间和空间复杂度.最后第 5 节给出结论.1.1 相关工作最近邻问题(或 NN 问题)及其变种是计算几何的重要基础问题6,并在许多领域具有重要的应用710.精确最近邻问题可以追溯到 1960 年代11.研究者们发现,解决精确最近邻问题面临着“维度诅咒”,即当维度数增高时,算法的理论性能和实验表现都会极大地降低,甚至无法优于简单的直接搜索12,13.为了解决“维度诅咒”,许多研究者开始研究近似最近邻问题,即本文中研究的-NN 问题.研究者们提出了一系列算法5,14,15,但是维度诅咒问题只是减轻而没有被解决.更多的相关工作可以参阅文献 1,4.目前解决“维度诅咒”问题的最好方法当属 Indyk 等人提出的基于图灵归约的方法4.他们定义了(c,r)-NN 问题,并提出了第一个从-NN 问题到(c,r)-NN 问题的图灵归约.于是-NN 问题的求解被分为两部分,一部分是求解(c,r)-NN 问题,另一部分是解决从-NN 问题到(c,r)-NN 问题的图灵归约.如果两部分都能够避免“维度诅咒”,则-NN 问题的“维度诅咒”随之解决.下面我们分别介绍这两部分工作.Indyk 等人4提出的基于局部敏感哈希(LSH)的方法是目前解决(c,r)-NN 问题最有效的方法.简言之,局部敏感哈希函数能够使得距离较近的点对以较大概率被散列到同一个桶中,距离较远的点对以较大概率散列到不同的桶中.在文献 4 提出了局部敏感哈希的定义之后,Datar 等人16提出了第一个实用的局部敏感哈希函数,适用于欧氏空间.此后,局部敏感哈希的研究获得了长足的发展,既有关于不同数据、不同距离函数的局部敏感哈希函数设计的研究1719,也有关于局部敏感哈希函数的性能下界的研究20,21,也有关于局部敏感哈希在不同领域的应用的研究22.文献 23,24 给出了详细的综述.最后要说明的是,基于局部敏感哈希方法解决(c,r)-NN 的算法可以4822软件学报2023 年第 34 卷第 10 期达到伪亚线性时间,即经过多项式时间的预处理之后,可以在亚线性时间内得到结果.O(log2n)O(log(n/)O(logO(1)n)O(logn)O(d/)d)Indyk 等人4提出了第一个从-NN 问题到(c,r)-NN 问题的归约.请注意,这里的归约是图灵归约,即以一个解决(c,r)-NN 问题的算法作为神谕,通过反复调用(c,r)-NN 问题的算法来解决-NN 问题.设计图灵归约一般关注其查询复杂度,即调用神谕算法的次数.文献 4 中给出的归约的查询时间复杂度为.文献 2,3 中提出新的图灵归约,其查询时间复杂度分别为和,见文献 25.我们在文献 1 中提出另一种图灵归约,得到了目前最低的查询时间复杂度.但是,我们在文献 1 中提出的归约的预处理时间和空间复杂度中都有的因子.在本文中,我们就将致力于降低以至消除此因子.泊松点过程是一种十分重要的随机过程,它有着很多良好的几何性质,因此在计算几何领域有很多相关的研究.比如文献 26 中研究了服从泊松点过程的点集上构建的 Delaunay 三角剖分的性质,文献 27 中研究了服从泊松点过程的点集上的寻路问题,文献 28 研究了服从泊松点过程的网络节点的覆盖问题.由于泊松点过程的良好性质,通常能够使分析得到简化,并能够得到比较好的理论结果.据我们所知,目前还没有在服从泊松点过程的数据上的近似最近邻问题的研究.2 预备知识dd 2.1 维矩形和维超球Rd1 i dIi=ai,biR=I1I2.IdIili(R)=biaili(R)=l1 i d一个 d 维矩形 R 是空间上 d 个闭区间的笛卡尔积,即对于,设,则.称为 R 在第 i 维上的定义区间,为 R 在第 i 维上的边长.若对所有都成立,则称 R 为一个 d 维超立方体.c Rdr 0B(c,r)=x Rd|D(x,c)rB(c,r)D(p,c)0c 1D(p,q)cr定义 2(c,r)-NN 问题).设输入点集 P 如第 2.2 节所描述,为查询点,为查询范围,为近似参数,则(c,r)-NN 问题的输出如下:若存在 p 使得,则输出某点满足;若都有则输出否定答案 No.AcrnnAcrnnAcrnn本文所研究的问题为设计从-NN 问题到(c,r)-NN 的高效图灵归约,即以一个求解(c,r)-NN 的算法作为神谕,设计求解-NN 问题的高效算法.设计的要点在于使用恰当的预处理算法和数据结构,从而尽量减少调用的次数.算法的时间和空间复杂度分为 3 部分,一是预处理算法的时间复杂度,二是通过预处理算法构建的数据结构所占用的空间复杂度,三是查询时间复杂度,也即调用的次数.3 算法本文将要介绍的算法分为两部分,即预处理算法和查询算法.3.1 预处理算法预处理算法接受如定义 1 中所述的输入,返回一棵树型结构 T,用于支持查询阶段的算法.这棵树称为分裂树,其结构形式化定义如下.定义 3(分裂树).一棵分裂树 T 满足如下条件.R S(1)树中的每个结点都代表一个 d 维矩形,且根结点为 S.R TIi(R)=ai,biIi(1)(R)=ai,(ai+bi)/2 Ii(2)(R)=(ai+bi)/2,biR(1)=I1(R).Ii(1)(R).Id(R)R(2)=I1(R).Ii(2)(R).Id(R)R(2)任一非叶结点都有两个子结点,其构造方法如下:取 R 的最长边,将其从中点分成两部分,则,它们即为的两个子结点.|RP|=1(3)每个叶结点 R 满足.depT(R)对于分裂树 T 的每个结点 R,算法对其构造了一个数据结构 Nbr(R),保存和 R 满足一定位置关系的 T 中的其他结点.在下面的定义中,记 root(T)为 T 的根结点.对于 T 中某结点 R,记为结点 R 在树 T 中的深度,也即从 R 到 root(T)上的路径上边的数量.Nbr(R)的定义如下.R TR Nbr(R)定义 4.对于,满足以下条件.depT(R)=depT(R)(1).a(1)i,b(1)iia(2)i,b(2)iRi 1,d(a(1)i,b(1)ia(2)i,b(2)i,)(|a(1)ib(2)i|2Cplog1/dn)(|a(2)ib(1)i|2Cplog1/dn)(2)设为 R 在第 维上的定义区间,为在第 i 维上的定义区间,则对于,有为真.CP下面给出算法 1 即为预处理算法的伪代码.预处理算法分为两个主要过程,一是进行构造分裂树 T,二是对 T中每个结点建立其 Nbr 集.构造分裂树的过程是一个比较简单的递归过程,其伪代码在算法 2 中给出.建立 Nbr 集是一个层序遍历的过程,使用队列数据结构来完成层序遍历.预处理算法的详细描述请见下面的算法 1.在算法 1的第 11 行中,常数的值根据推论 1 选取.算法 1.预处理算法.输入:点集 P,查询点 q,超立方体 S;输出:一棵树结构 T.1初始化一棵树 T,其根为 S2Split(root(T)3Nbr(root(T)4初始化空队列 Q,将 root(T)入队4824软件学报2023 年第 34 卷第 10 期5While队列 Q 非空do6Rc队列 Q 中队顶元素7if|RcP|1then8SonscRcNbr(Rc)中结点的所有子结点9令 R1,R2为 Rc的两个子结点10foreachRSonscR1do11ifTestNbr(R,R1)=truethen12Nbr(R1)Nbr(R1)R13end14end15foreachRSonscR2do16ifTestNbr(R,R2=true)then17Nbr(R2)Nbr(R2)R18end19end20将 Rc从 Q 中出队,将 R1,R2入队21end22end算法 2.算法 1 中用到子程序.1ProcedureSplit(R):2取 R 的最长边,将其从中点一分为二,得到两个较小的矩形 R1和 R23将 R1,R2作为 R 的子结点加入到树 T 中4Split(R1)5Split(R2)6end7ProcedureTestNbr(R1,R2):8fori=1toddo9ai(1),bi(1)R1在第 i 维上的定义区间10ai(2),bi(2)R2在第 i 维上的定义区间11if(ai(1),bi(1)ai(2),bi(2)=)(|ai(1)bi(2)|2CPlog1/dn|ai(2)bi(1)|2CPlog1/dn)then12returnfalse13end14end15returntrue16end 3.2 查询算法在预处理算法结束之后,查询算法基于预处理算法所返回的分裂树 T 来解决第 2.4 节中给出的归约问题,算法的执行过程如下.Rc(1)设当前考虑的结点为 T 的根.马恒钊等:近似最近邻归约问题在泊松点过程上的再研究4825PcRcNbr(Rc)(2)设当前考虑的点集为和中包含的所有点.AcrnnPcCPlog1/dn1+CPp(3)调用,调用的输入点集为,查询点为 q,查询范围为,近似参数为,其中是推论 1中所给出的值,是-NN 问题的输入参数.在后面的引理 4 中我们将证明,此次调用一定会返回一个点.RcNbr(Rc)Rp RRc R(4)检视的所有子结点,设子结点满足,令.Rc(5)若中包含的点数多于 1,则返回第 2 步,否则继续.Pc(6)在中直接搜索-NN 的结果.算法的伪代码在下面的算法 3 中给出.算法 3.查询算法.Acrnn输入:输入点集 P,查询点 q,解决(c,r)-NN 的算法,算法 1 的输出 T;输出:-NN 的结果.1Rcroot(T)2while|RcP|1doRRcNbr(Rc)RP3PcAcrnn4调用(Pc,q,CPlog1/dn,1+),得到返回点 p5检视所有RcNbr(Rc)的所有子结点,设子结点 R满足 pR6RcR7end8在 Pc中用直接搜索找到-NN 的结果并返回 4 分析 4.1 准备工作CPE|B(q,CPlog1/dn)P|1引理 1.取为推论 1 中所给出的常数,则.n1/dPqCPlog1/dnCPlog1/dn证明:由问题定义,输入点集 P 和查询点 q 都位于边长为的区域 S 中,则根据推论 1,由构造的Delaunay 三角剖分的期望最长边为.于是在期望情况下,在以 q 为中心、为半径的范围之内至少存在一个点,引理得证.O(logn)R TE|Nbr(R)|=O(logn)引理 2.对 T 中任意结点 R,Nbr(R)集合的期望大小为,即对于,.O(log1/dn)O(logn)O(logn)O(logn)O(logn)证明:由泊松点过程的性质,体积为 1 的 d 维矩形中包含的期望点数为 1.由于 T 的每个结点中至少包含 P 中的一个点,所以每个结点的体积在期望情况下不小于 1.Nbr(R)的定义可知,Nbr(R)所包含的区域在各维上的边长都比 R 多,进而 Nbr(R)所包含的区域的体积为.于是,对于体积为 1 的结点 R,Nbr(R)中包含的体积为 1 的结点数最多为.对于体积大于 1 的结点 R,Nbr(R)中所包含的结点数则一定少于.总之,T 中任意结点的 Nbr 集合的期望大小为,引理得证.引理 3.预处理算法返回的分裂树 T 具有如下性质.O(n)(1)T 中最多有个结点.O(logn)(2)T 的期望高度为.O(n)2n1O(n)证明:根据定义 3 可知,T 的每个叶结点中有 1 个数据点,进而 T 中有个叶结点.T 中每个非叶结点都有两个子结点,则当 T 是一棵完全二叉树时,T 中有个结点,若 T 不是完全二叉树则 T 中结点会更少.于是 T中最多有个结点,性质 1 得证.R1R2R1R2由 T 的构造过程可知,结点 R 的子结点是通过把 R 的最长边二等分得到的.因此两个子结点和所代表的 d 维矩形具有相同的体积.由泊松点过程的性质,和中包含的期望点数相同.也即树 T 中每一层的结点中4826软件学报2023 年第 34 卷第 10 期O(logn)包含的点数的期望都比上一层少一半,则 T 的期望高度为.4.2 正确性分析Acrnn引理 4.在期望情况下,算法 3 的第 4 行每次调用都能返回一个点作为结果.Pc=PB(q,CPlog1/dn)AcrnnpRcPck+1pk+1PcAcrnnAcrnn证明:在第 1 次循环时,.又由引理 1,在期望情况下至少包含一个点,于是根据(c,r)-NN 问题的定义,第 1 次调用能够返回一个点.现假设在第 k 次调用时返回了一个点.由和的设置方法可知,在第次调用时,仍在第轮循环中所更新的中.由(c,r)-NN 问题的定义,此次调用算法仍能返回一个点.总之,算法每次调用在期望情况下每次都能返回一个点作为结果.pD(p,q)=minpPD(p,q)p Pc引理 5.设为 q 在 P 中的最近邻,即,则在算法 3 的每一次循环中,总有.pD(p,q)CPlog1/dnCPlog1/dnD(p,q)CPlog1/dnD(p,p)D(p,q)+D(p,q)2CPlog1/dn证明:由引理 4,算法 3 的第 4 行每次都能返回一个点.由(c,r)-NN 的定义可知,(c,r)满足.另由引理 1,查询点 q 的最近邻距离不超过.即.于是有.RpNbr(R)R2CPlog1/dnNbr(R)B(q,2CPlog1/dn)D(p,p)2CPlog1/dnpNbr(R)PcpNbr(R)p Pc由算法 3 的伪代码,是包含的子结点.由定义 4 可知,覆盖的区域在每个维度上都比拓展了,从而可以覆盖.因为,则也能够被覆盖.由的设置方法,能够被覆盖等价于,引理得证.定理 2.算法 3 能够正确地返回-NN 的结果.p Pcp证明:由引理 5,在算法的每一次循环中都有,其中是 q 在 P 中的最近邻.于是,算法第 8 行的直接搜索一定能够能产生-NN 的正确结果.4.3 复杂度分析O(nlogn)定理 3.算法 1 的期望时间复杂度为.证明:算法 1 的时间复杂度分为两部分,一是构造分裂树,二是对分裂树的所有结点建立 Nbr 集.ET(n)=2ET(n/2)+O(n)2ET(n/2)O(n)O(n)O(|Nbr(R)|)=O(logn)O(n)ET(n)=O(nlogn)构造分裂树的部分是分治算法,根据算法 1 的内容和引理 3 中的证明,可以写出关于此分治算法的期望时间复杂度的递归公式:.公式中来自于子结点中期望点数为父结点的一半,已经在引理 3 的证明过程中得以证明.关于项,观察算法 1 可知,将父结点分裂为两个子结点需要时间,遍历 Nbr(R)需要时间,则分治算法每次循环体需要时间.容易证明,此递归公式的解为.O(n)O(logn)O(nlogn)现在分析对分裂树的所有结点建立 Nbr 集的复杂度.由引理 3,分裂树 T 中总共有个结点.由引理 2,每个结点的 Nbr 集的期望大小都为.由算法 1 的伪代码可知,每个结点的 Nbr 集最多被遍历一次.从而建立所有结点的 Nbr 集的期望时间复杂度.O(nlogn)将以上两部分时间复杂度相加,则得到算法 1 的期望时间复杂度为.O(nlogn)定理 4.算法 1 需要期望空间.O(n)O(logn)O(nlogn)证明:算法 1 需要的空间即为存储分裂树 T 所需的空间.由引理 3,T 中共有个结点.由引理 2,对 T 中每个结点 R 存储的 Nbr(R)集合的期望大小为.于是,存储 T 总共需要期望空间.AcrnnO(logn)O(logn)定理 5.算法 3 需要调用算法次,也即算法以的查询时间解决第 2.4 节中给出的归约问题.O(logn)O(logn)AcrnnO(logn)证明:算法 3 在每一次循环中调用一次,而循环的执行次数等于分裂树 T 的高度.由引理 3,T 的期望高度为,于是算法 3 需要调用算法次得证.5 结论O(nlogn)O(nlogn)O(logn)本文是我们发表的文献 1 中工作的延续,研究了基于图灵归约求解-NN 问题在输入点集服从泊松点过程条件下的期望复杂度.我们提出了与文献 1 中不同的算法,并分析了其复杂度,证明了它具有期望预处理时间、期望空间和期望查询时间.本文解决了我们在文献 1 中提出的未来工作.马恒钊等:近似最近邻归约问题在泊松点过程上的再研究4827References:MaHZ,LiJZ.AnalgorithmforreducingapproximatenearestneighbortoapproximatenearneighborwithO(logn)querytime.In:Proc.ofthe12thIntlConf.onCombinatorialOptimizationandApplications.Atlanta:Springer,2018.465479.doi:10.1007/978-3-030-04651-4_311Har-PeledS.Areplacementforvoronoidiagramsofnearlinearsize.In:Proc.ofthe42ndIEEESymp.onFoundationsofComputerScience.NewportBeach:IEEE,2001.94103.doi:10.1109/SFCS.2001.9598842Har-PeledS,IndykP,MotwaniR.Approximatenearestneighbor:Towardsremovingthecurseofdimensionality.TheoryofComputing,2012,8(1):321350.doi:10.4086/toc.2012.v008a0143IndykP,MotwaniR.Approximatenearestneighbors:Towardsremovingthecurseofdimensionality.In:Proc.ofthe30thAnnualACMSymp.onTheoryofComputing.Dallas:ACM,1998.604613.doi:10.1145/276698.2768764AryaS,MountDM,NetanyahuNS,SilvermanR,WuAY.Anoptimalalgorithmforapproximatenearestneighborsearchingfixeddimensions.JournaloftheACM,1998,45(6):891923.doi:10.1145/293347.2933485GoelA,IndykP,VaradarajanK.Reductionsamonghighdimensionalproximityproblems.In:Proc.ofthe12thAnnualACM-SIAMSymp.onDiscreteAlgorithms.Washington:SocietyforIndustrialandAppliedMathematics,2001.769778.6IscenA,ToliasG,AvrithisY,ChumO.Miningonmanifolds:Metriclearningwithoutlabels.In:Proc.ofthe2018IEEE/CVFConf.onComputerVisionandPatternRecognition.SaltLakeCity:IEEE,2018.76427651.doi:10.1109/CVPR.2018.007977LuXL.Improvingsearchusingproximity-basedstatistics.In:Proc.ofthe38thIntlACMSIGIRConf.onResearchandDevelopmentinInformationRetrieval.Santiago:ACM,2015.1065.doi:10.1145/2766462.27678478LuoYC,ZhuJ,LiMX,RenY,ZhangB.Smoothneighborsonteachergraphsforsemi-supervisedlearning.In:Proc.ofthe2018IEEE/CVFConf.onComputerVisionandPatternRecognition.SaltLakeCity:IEEE,2018.88968905.doi:10.1109/CVPR.2018.009279ZhengYX,GuoQ,TungAKH,WuS.LazyLSH:Approximatenearestneighborsearchformultipledistancefunctionswithasingleindex.In:Proc.ofthe2016IntlConf.onManagementofData.SanFrancisco:ACM,2016.20232037.doi:10.1145/2882903.288293010MinskyM,PapertS.Perceptrons.Cambridge:MITPress,1969.11ClarksonKL.Analgorithmforapproximateclosest-pointqueries.In:Proc.ofthe10thAnnualSymp.onComputationalGeometry.StonyBrook:ACM,1994.160164.doi:10.1145/177424.17760912WeberR,SchekHJ,BlottS.Aquantitativeanalysisandperformancestudyforsimilarity-searchmethodsinhigh-dimensionalspaces.In:Proc.ofthe24thIntlConf.onVeryLargeDataBases.NewYorkCity:MorganKaufmannPublishersInc.,1998.194205.13AryaS,MountDM.Approximatenearestneighborqueriesinfixeddimensions.In:Proc.ofthe4thAnnualACM-SIAMSymp.onDiscreteAlgorithms.Austin:SocietyforIndustrialandAppliedMathematics,1993.271280.14KleinbergJM.Twoalgorithmsfornearest-neighborsearchinhighdimensions.In:Proc.ofthe29thAnnualACMSymp.onTheoryofComputing.ElPaso:ACM,1997.599608.doi:10.1145/258533.25865315DatarM,ImmorlicaN,IndykP,MirrokniVS.Locality-sensitivehashingschemebasedonp-stabledistributions.In:Proc.ofthe20thAnnualSymp.onComputationalGeometry.Brooklyn:ACM,2004.253262.doi:10.1145/997817.99785716Charikar MS.Similarity estimation techniques from rounding algorithms.In:Proc.of the 34th Annual ACM Symp.on Theory ofComputing.Montreal:ACM,2002.380388.doi:10.1145/509907.50996517LiP,MitzenmacherM,ShrivastavaA.Codingforrandomprojections.In:Proc.ofthe31thIntlConf.onMachineLearning.Beijing:JMLR.org,2014.II-676II-684.18TerasawaK,TanakaY.SphericalLSHforapproximatenearestneighborsearchonunithypersphere.In:Proc.ofthe10thIntlConf.onAlgorithmsandDataStructures.Halifax:Springer,2007.2738.doi:10.1007/978-3-540-73951-7_419AndoniA,RazenshteynIP.Tightlowerboundsfordata-dependentlocality-sensitivehashing.In:Proc.ofthe32ndIntlSymp.onComputational Geometry.Dagstuhl:Schloss Dagstuhl Leibniz-Zentrum fuer Informatik,2016.1 11.doi:10.4230/LIPIcs.SoCG.2016.920MotwaniR,NaorA,PanigrahyR.Lowerboundsonlocalitysensitivehashing.SIAMJournalonDiscreteMathematics,2008,21(4):930935.doi:10.1137/05064685821TaoYF,YiK,ShengC,KalnisP.Efficientandaccuratenearestneighborandclosestpairsearchinhigh-dimensionalspace.ACMTrans.onDatabaseSystems,2010,35(3):20.doi:10.1145/1806907.180691222Andoni A.Nearest neighbor search:The old,the new,and the impossible Ph.D.Thesis.Cambridge:Massachusetts Institute ofTechnology,2009.234828软件学报2023 年第 34 卷第 10 期WangJD,ShenHT,SongJK,JiJQ.Hashingforsimilaritysearch:Asurvey.arXiv:1408.2927,2014.24AndoniA,IndykP.Nearestneighborsinhigh-dimensionalspaces.In:GoodmanJE,ORourkeJ,TthCD,eds.HandbookofDiscreteandComputationalGeometry.3rded.,BocaRaton:ChapmanandHall/CRC,2017.11351155.25BernM,EppsteinD,YaoF.TheexpectedextremesinaDelaunaytriangulation.IntlJournalofComputationalGeometry&Applications,1991,1(1):7991.doi:10.1142/S021819599100007426BordenaveC.NavigationonaPoissonpointproces