.png){kind=icon}
返回
Efficient Nearest Neighbor Search Using Dynamic Programming
.png){kind=icon}
PRE
AI
DOI：10.1109/TPAMI.2025.3610211.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
给定一组$\mathbb {R}^{3}$中的点，KD-Tree和R-Tree是两种知名的基于空间划分和索引技术的最近邻搜索（NNS）算法。然而，当查询点远离数据点或数据点本身代表一个2-流形表面时，它们的查询性能可能会下降。为解决这一问题，我们提出了一种新颖的动态规划技术，预先计算一个有向无环图（DAG）以编码数据点之间的邻近结构。更具体地说，该DAG捕捉了在数据点的Voronoi图增量构造过程中邻近结构的演变方式。实验结果表明，我们的方法实现了1-10倍的加速。此外，我们的算法在多样化应用中展现出显著的实际价值。我们通过在四个关键应用中的广泛测试验证了其有效性：点到网格距离查询、迭代最近点（ICP）配准、密度峰值聚类和点到线段距离查询。我们方法的一个特别显著的特点是其独特能力，能够高效地在点云的前$k$个点中识别最近邻，这一能力使得在低维应用（如密度峰值聚类）中实现显著加速。作为我们增量构造过程的自然扩展，我们的方法还可以轻松地适用于最远点采样任务。这些跨多个领域的实验结果强调了我们所提方法广泛的适用性和实际重要性。
Keyword:
Nearest neighbor search
delaunay triangulation
voronoi diagram
farthest point sampling
density peak clustering
期刊
IF:
18.6
论文数:
1.1K
被引数:
9.8W
机构
引用论文
.png){kind=icon}
分享收藏分享收藏分享收藏
查看更多内容