| 摘要: |
| 在已发表文献中, 研究了基于图灵归约求解$ \varepsilon $-NN的问题, 即给定查询点q、点集P及近似参数$ \varepsilon $, 找到q在P中近似比不超过$ 1 + \varepsilon $的近似最近邻, 并提出了一个具有${\rm{O}}(\log n)$查询时间复杂度的图灵归约算法, 这里的查询时间是调用神谕的次数. 经过对比, 此时间优于所有现存的归约算法. 但是已发表文献中提出的归约算法的缺点在于, 其预处理时间和空间复杂度中有${\rm{O}}({(d/\varepsilon )^d})$的因子, 当维度数d较大或者近似参数$ \varepsilon $较小时, 此因子将变得不可接受. 因此, 重新研究了该归约算法, 在输入点集服从泊松点过程的情况下, 分析算法的期望时间和空间复杂度, 将算法的期望预处理时间复杂度降到${\rm{O}}(n\log n)$, 期望空间复杂度降到${\rm{O}}(n\log n)$, 而期望查询时间复杂度保持${\rm{O}}(\log n)$不变, 从而完成了在已发表文献中所提出的未来工作. |
| 关键词: 近似最近邻 归约 泊松点过程 复杂度 |
| DOI：10.13328/j.cnki.jos.006649 |
| 分类号:TP311 |
| 基金项目:国家自然科学基金(61732003,61832003,U1811461) |
|
| Revised Algorithm Based on Turing Reduction for Solving ε-NN in Possion Point Process |
|
MA Heng-Zhao1,2, YAN Yue3, LI Jian-Zhong1
|
|
1.School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China;2.Institute of Advanced Computing and Digital Engineering, Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences, Shenzhen 518055, China;3.Department of Computer Science, Harbin Finance University, Harbin 150001, China
|
| Abstract: |
| 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. |
| Key words: approximate nearest neighbor reduction Poisson point process complexity |
