Just Join for Parallel Ordered Sets
Just Join for Parallel Ordered Sets
复制标题
只需加入并行有序集
DOI：
10.1145/2935764.2935768
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Yihan Sun
中科院分区：
文献类型：
--
作者：
G. Blelloch;Daniel Ferizovic;Yihan Sun
有序集（与每个键关联时地图）是最重要的和有用的数据类型之一。基于2-3棵树的功能，在比较模型中符合最佳的θ（m log（n/m+1））时间边界（n和m≤n是输入尺寸）。这些功能和其他基于重量平衡的树然而，在二十四年中，没有人表明算法，顺序或平行是不对称的，在本文中，我们表明Adams的算法有效，并且高度平行（Polylog（Polylog） ）跨越四个不同的平衡方案--- avl树，红色树木，重量平衡的树木和树木。在整个方案中，算法在实践中的执行方式。超过45倍的64个内核）。
Ordered sets (and maps when data is associated with each key) are one of the most important and useful data types. The set-set functions union, intersection and difference are particularly useful in certain applications. Brown and Tarjan first described an algorithm for these functions, based on 2-3 trees, that meet the optimal Θ(m log (n/m+1)) time bounds in the comparison model (n and m ≤ n are the input sizes). Later Adams showed very elegant algorithms for the functions, and others, based on weight-balanced trees. They only require a single function that is specific to the balancing scheme---a function that joins two balanced trees---and hence can be applied to other balancing schemes. Furthermore the algorithms are naturally parallel. However, in the twenty-four years since, no one has shown that the algorithms, sequential or parallel are asymptotically work optimal. In this paper we show that Adams' algorithms are both work efficient and highly parallel (polylog span) across four different balancing schemes---AVL trees, red-black trees, weight balanced trees and treaps. To do this we use careful, but simple, algorithms for Join that maintain certain invariants, and our proof is (mostly) generic across the schemes. To understand how the algorithms perform in practice we have also implemented them (all code except Join is generic across the balancing schemes). Interestingly the implementations on all four balancing schemes and three set functions perform similarly in time and speedup (more than 45x on 64 cores). We also compare the performance of our implementation to other existing libraries and algorithms.
使用带有批量更新的权重平衡 B 树的并行双目标最短路径
DOI：
10.1007/978-3-319-07959-2_10
发表时间：
2014
期刊：
影响因子：
--
作者：
Stephan Erb;Moritz Kobitzsch;Peter Sanders
通讯作者：
Peter Sanders