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

Revised Algorithm Based on Turing Reduction for Solving ε-NN in Possion Point Process

在已发表文献中,研究了基于图灵归约求解ε-NN的问题,即给定查询点q、点集P及近似参数ε,找到q在P中近似比不超过1+ε的近似最近邻,并提出了一个具有O(logn)查询时间复杂度的图灵归约算法,这里的查询时间是调用神谕的次数.经过对比,此时间优于所有现存的归约算法.但是已发表文献中提出的归约算法的缺点在于,其预处理时间和空间复杂度中有O((d/ε)^(d))的因子,当维度数d较大或者近似参数ε较小时,此因子将变得不可接受.因此,重新研究了该归约算法,在输入点集服从泊松点过程的情况下,分析算法的期望时间和空间复杂度,将算法的期望预处理时间复杂度降到O(n logn),期望空间复杂度降到O(nlogn),而期望查询时间复杂度保持O(logn)不变,从而完成了在已发表文献中所提出的未来工作.

In a published study,the problem of using Turing reduction to solveε-NN is studied.In other words,given a query point q,a point set P,and an approximate factorε,the purpose is to return the approximate nearest neighbor of q in P with an approximation ratio of not more than 1+ε.Moreover,a Turing reduction algorithm with O(logn)query time complexity is proposed,where the query time is the number of times that the oracle is invoked.The comparison indicates that the O(logn)query time is the lowest compared to that of all the existing algorithms.However,the disadvantage of the proposed algorithm is that there is a factor of O((d/ε)^(d))in the preprocessing time complexity and space complexity.When the number of dimensions d is high,or the approximation factorεis small,the factor would become unacceptable.Therefore,this study revises the reduction algorithm and analyzes the expected time complexity and space complexity of the algorithm when the input point set follows the Poisson point process.As a result,the expected preprocessing time complexity is reduced to O(nlogn),and the expected space complexity is reduced to O(nlogn),while the expected query time complexity remains O(logn).In this sense,the future work raised in the published study is completed.