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

摘要

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