论文标题
配对的压缩盖树保证所有$ k $ neart的邻居在任意度量空间中搜索的几乎线性参数化的复杂性
Paired compressed cover trees guarantee a near linear parametrized complexity for all $k$-nearest neighbors search in an arbitrary metric space
论文作者
论文摘要
本文研究了在任何公制空间内的另一个参考套装$ r $中查找所有$ k $ neart最邻居的重要问题。我们以前的工作定义了压缩树，并在过去的几篇论文中纠正了针对挑战数据集的关键参数。在2009年，RAM，Lee，March和Gray试图通过在查询和参考集中使用一对盖树来改善时间复杂性。在2015年，Curtin与上述合着者使用了额外的参数，最终证明了$ k = 1 $的时间复杂性。当前的工作填补了所有以前的空白，并根据新的压缩盖树改进了最近的邻居搜索。配对树的新颖不平衡参数使我们能够证明任何数量的邻居$ k \ geq 1 $都具有更好的时间复杂性。
This paper studies the important problem of finding all $k$-nearest neighbors to points of a query set $Q$ in another reference set $R$ within any metric space. Our previous work defined compressed cover trees and corrected the key arguments in several past papers for challenging datasets. In 2009 Ram, Lee, March, and Gray attempted to improve the time complexity by using pairs of cover trees on the query and reference sets. In 2015 Curtin with the above co-authors used extra parameters to finally prove a time complexity for $k=1$. The current work fills all previous gaps and improves the nearest neighbor search based on pairs of new compressed cover trees. The novel imbalance parameter of paired trees allowed us to prove a better time complexity for any number of neighbors $k\geq 1$.
