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

摘要：

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

关键词：近似最近邻、归约、泊松点过程、复杂度

所属期刊栏目：34

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金;国家自然科学基金;国家自然科学基金

在线出版日期：2023-10-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：4821-4829