近似最近邻归约问题在泊松点过程上的再研究*马恒钊1,3,闫跃2,李建中11(哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨150001)2(哈尔滨金融学院计算机系,黑龙江哈尔滨150001)3(中国科学院深圳先进技术研究院先进计算与数字工程研究所,广东深圳518055)通信作者:李建中,E-mail:lijzh@hit.edu.cnεε1+εO(logn)O((d/ε)d)εO(nlogn)O(nlogn)O(logn)摘要:在已发表文献中,研究了基于图灵归约求解-NN的问题,即给定查询点q、点集P及近似参数,找到q在P中近似比不超过的近似最近邻,并提出了一个具有查询时间复杂度的图灵归约算法,这里的查询时间是调用神谕的次数.经过对比,此时间优于所有现存的归约算法.但是已发表文献中提出的归约算法的缺点在于,其预处理时间和空间复杂度中有的因子,当维度数d较大或者近似参数较小时,此因子将变得不可接受.因此,重新研究了该归约算法,在输入点集服从泊松点过程的情况下,分析算法的期望时间和空间复杂度,将算法的期望预处理时间复杂度降到,期望空间复杂度降到,而期望查询时间复杂度保持不变,从而完成了在已发表文献中所提出的未来工作.关键词:近似最近邻;归约;泊松点过程;复杂度中图法分类号:TP311中文引用格式:马恒钊,闫跃,李建中.近似最近邻归约问题在泊松点过程上的再研究.软件学报,2023,34(10):4821–4829.http://www.jos.org.cn/1000-9825/6649.htm英文引用格式:MaHZ,YanY,LiJZ.RevisedAlgorithmBasedonTuringReductionforSolvingε-NNinPossionPointProcess.RuanJianXueBao/JournalofSoftware,2023,34(10):4821–4829(inChinese).http://www.jos.org.cn/1000-9825/6649.htmRevisedAlgorithmBasedonTuringReductionforSolvingε-NNinPossionPointProcessMAHeng-Zhao1,3,YANYue2,LIJian-Zhong11(SchoolofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin150001,China)2(DepartmentofComputerScience,HarbinFinanceUniversity,Harbin150001,China)3(InstituteofAdvancedComputingandDigitalEngineering,ShenzhenInstituteofAdvancedTechnology,ChineseAcademyofSciences,Shenzhen518055,China)Abstract:Inapublishedstudy,theproblemofusingTuringreductiontosolveε-NNisstudied.Inotherwords,givenaquerypointq,apointsetP,andanapproximatefactorε,thepurposeistoreturntheapproximatenearestneighborofqinPwithanapproximationratioofnotmorethan1+ε.Moreover,aTuringreductionalgorithmwith...
