Nearly Optimal Parallel Algorithms for Longest Increasing Subsequence
Nearly Optimal Parallel Algorithms for Longest Increasing Subsequence
复制标题
最长递增子序列的近最优并行算法
DOI：
10.1145/3558481.3591078
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Su, Hsin-Hao
中科院分区：
文献类型：
--
作者：
Cao, Nairen;Huang, Shang-En;Su, Hsin-Hao
本文提出了在EREW PRAM模型中乘以大小为n x n的隐式简单单位Monge矩阵（Krusche和Tiskin，PPAM 2009）的并行算法。我们表明隐式简单的单位Monge矩阵乘法的大小为n × n可以实现的确定性EREW PRAM算法与O（n log n log log n）的总工作和O（log 3 n）跨度。这意味着有一个确定性的EREW PRAM算法解决最长递增子序列（LIS）问题，在O（nlog 2nloglogn）的工作和O（log 4 n）的跨度。此外，通过随机化和按位操作，隐式地将两个简单的单位-Monge矩阵相乘可以改进为O（nlog n）工作和O（log 3 n）跨度，这导致随机EREW PRAM算法以O（nlog 2n）工作和O（log 4 n）跨度以高概率获得LIS。在LIS长度为k = n（log 3 n）的情况下，我们的结果将跨度从n（n2/3）（Krusche and Tiskin，SPAA 2010）和O（klog n）（Gu，Men，Shen，Sun，and Wan，SPAA 2023）提高到O（log 4 n），同时总工作保持在最佳n（n）附近。
The paper presents parallel algorithms for multiplying implicit simple unit-Monge matrices (Krusche and Tiskin, PPAM 2009) of size n x n in the EREW PRAM model. We show implicit simple unit-Monge matrices multiplication of size n x n can be achieved by a deterministic EREW PRAM algorithm with O(n log n log log n) total work and O(log3 n) span. This implies that there is a deterministic EREW PRAM algorithm solving the longest increasing subsequence (LIS) problem in O(n log2 n log log n) work and O(log 4 n) span. Furthermore, with randomization and bitwise operations, implicitly multiplying two simple unit-Monge matrices can be improved to O(n log n) work and O(log3n) span, which leads to a randomized EREW PRAM algorithm obtaining LIS in O(nlog2n) work and O(log4n) span with high probability. In the regime where the LIS has length k = Ψ(log3n), our results improve the span from Õ(n2/3) (Krusche and Tiskin, SPAA 2010) and O(klog n) (Gu, Men, Shen, Sun, and Wan, SPAA 2023) to O(log4 n) while the total work remains near optimal Õ (n).
登录
查看更多内容
使用增强地图进行并行范围、线段和矩形查询
DOI：
10.1137/1.9781611975499.13
发表时间：
2018
期刊：
ACM Transactions on Database Systems (TODS)
影响因子：
--
作者：
Yihan Sun;G. Blelloch
通讯作者：
G. Blelloch
影响因子：
7.2
作者：
Picot, Emma;Krusche, Peter;Ott, Sascha
通讯作者：
Ott, Sascha
一种成本最优的耐心排序并行算法
影响因子：
0.4
作者：
T. Nakashima;A. Fujiwara
通讯作者：
A. Fujiwara
所有对最短路径的 O(n3loglogn/log2n) 时间算法
DOI：
--
发表时间：
2016
期刊：
J. Discrete Algorithms
影响因子：
--
作者：
Yijie Han;T. Takaoka
通讯作者：
T. Takaoka
影响因子：
14.9
作者：
Delcher, AL;Kasif, S;Salzberg, SL
通讯作者：
Salzberg, SL