Parallel Cover Trees and their Applications
Parallel Cover Trees and their Applications
复制标题
DOI：
10.1145/3490148.3538581
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Yan Gu;Zachary Napier;Yihan Sun;Letong Wang
中科院分区：
文献类型：
--
作者：
Yan Gu;Zachary Napier;Yihan Sun;Letong Wang
覆盖树是一种规范的数据结构，它能有效地维护度量空间上的动态点集，并支持最近邻和k - 最近邻搜索。对于大多数具有合理分布（数学上恒定的扩展率和有界的宽高比）的现实世界数据集，单点插入、单点删除以及最近邻搜索（NNS）的成本仅与点集的大小成对数关系。不幸的是，由于覆盖树算法的复杂性以及使用深度优先遍历顺序，我们不知道针对这些覆盖树算法的任何并行方法。本文展示了高度并行且工作高效的覆盖树算法，它能够处理批量插入（以及因此的构建）和批量删除。假设恒定的扩展率和有界的宽高比，将m个点插入到具有n个点的覆盖树中，预期工作量为O(m log n)，并且大概率具有多项对数级的跨度。我们的算法依赖于一些新颖的算法见解。我们将插入和删除过程建模为一个图，并使用最大独立集（MIS）来生成无冲突的树节点。我们使用三个关键思想来保证工作效率：前缀加倍方案、精心设计以限制应用MIS的图的大小，以及在覆盖树的不同层级之间传播信息的策略。我们还使用路径复制使我们的并行覆盖树成为一种持久化的数据结构，这在一些应用中是很有用的。利用我们的并行覆盖树，我们为计算几何和机器学习中的一系列问题展示了工作高效（或接近工作高效）且高度并行的解决方案，包括欧几里得最小生成树（EMST）、单连接聚类、双色最近对（BCP）、基于密度的聚类及其层次版本等等。据我们所知，在假设恒定扩展率和有界宽高比的情况下，它们中的许多是实现工作效率和多项对数级跨度的首批解决方案。
The cover tree is the canonical data structure that efficiently maintains a dynamic set of points on a metric space and supports nearest and k-nearest neighbor searches. For most real-world datasets with reasonable distributions (constant expansion rate and bounded aspect ratio mathematically), single-point insertion, single-point deletion, and nearest neighbor search (NNS) only cost logarithmically to the size of the point set. Unfortunately, due to the complication and the use of depth-first traversal order in the cover tree algorithms, we were unaware of any parallel approaches for these cover tree algorithms. This paper shows highly parallel and work-efficient cover tree algorithms that can handle batch insertions (and thus construction) and batch deletions. Assuming constant expansion rate and bounded aspect ratio, inserting or deleting m points into a cover tree with n points takes O(m log n) expected work and polylogarithmic span with high probability. Our algorithms rely on some novel algorithmic insights. We model the insertion and deletion process as a graph and use a maximal independent set (MIS) to generate tree nodes without conflicts. We use three key ideas to guarantee work-efficiency: the prefix-doubling scheme, a careful design to limit the graph size on which we apply MIS, and a strategy to propagate information among different levels in the cover tree. We also use path-copying to make our parallel cover tree a persistent data structure, which is useful in several applications. Using our parallel cover trees, we show work-efficient (or near-work-efficient) and highly parallel solutions for a list of problems in computational geometry and machine learning, including Euclidean minimum spanning tree (EMST), single-linkage clustering, bichromatic closest pair (BCP), density-based clustering and its hierarchical version, and others. To the best of our knowledge, many of them are the first solutions to achieve work-efficiency and polylogarithmic span assuming constant expansion rate and bounded aspect ratio.