TP311

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

Fund Project:

• 摘要
• |
• 图/表
• |
• 访问统计
• |
• 参考文献
• |
• 相似文献
• |
• 引证文献
• |
• 资源附件
• |
• 文章评论
摘要:

在已发表文献中, 研究了基于图灵归约求解$\varepsilon$-NN的问题, 即给定查询点q、点集P及近似参数$\varepsilon$, 找到qP中近似比不超过$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)$不变, 从而完成了在已发表文献中所提出的未来工作.

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.

参考文献
相似文献
引证文献

• 点击次数:
• 下载次数:
• HTML阅读次数:
历史
• 收稿日期:2020-09-06
• 最后修改日期:2020-10-30
• 录用日期:
• 在线发布日期: 2023-01-18
• 出版日期: