Optimal parallel all-nearest-neighbors using the well-separated pair decomposition
Optimal parallel all-nearest-neighbors using the well-separated pair decomposition
复制标题
使用良好分离对分解的最优并行所有最近邻居
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
Paul B. Callahan
中科院分区：
文献类型：
--
作者：
Paul B. Callahan
提出了一种构造R/sup /中点集P的良好分离对分解的最优并行算法。我们展示了这如何导致一个确定的最优O（log n）时间并行算法，用于找到P中每个点的k个最近邻居，其中k是一个常数。我们讨论了良好分离对分解的几个附加应用，从中我们可以推导出更快的并行算法
We present an optimal parallel algorithm to construct the well-separated pair decomposition of a point set P in R/sup d/. We show how this leads to a deterministic optimal O(log n) time parallel algorithm for finding the k nearest neighbors of each point in P, where k is a constant. We discuss several additional applications of the well-separated pair decomposition for which we can derive faster parallel algorithms.<<ETX>>