LCP-Aware Parallel String Sorting
LCP-Aware Parallel String Sorting
复制标题
LCP 感知并行字符串排序
DOI：
10.1007/978-3-030-57675-2_21
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Sitchinava, Nodari
中科院分区：
文献类型：
--
作者：
Ellert, Jonas;Fischer, Johannes;Sitchinava, Nodari
当按字典顺序对字符串进行排序时，并不总是需要检查所有符号。例如，europaram 在字符串eureka、eurasia 和excells 中的词典顺序仅取决于其所谓的相关前缀euro。一组字符串的区别前缀 sizeD 是实际需要检查以建立所有字符串的字典顺序的符号数量。高效的字符串排序器应该具有D意识，即它们的复杂性应该取决于D而不是所有字符串中所有符号的总数N。虽然顺序设置中有许多 D-aware 排序器，但 PRAM 模型中似乎没有这样的结果。我们提出了一个框架，可以对任何现有的 PRAM 字符串排序器进行 D 感知修改。派生算法相对于其原始算法而言是工作最优的：如果原始算法需要工作，则派生算法也需要工作。执行时间仅增加一个很小的因子，该因子是最长相关前缀长度的对数。我们的框架普遍适用于 PRAM 模型所有变体中的确定性和随机算法，因此（D 不感知的）并行字符串排序的未来改进将直接导致 D 感知的并行字符串排序的改进。
When lexicographically sorting strings, it is not always necessary to inspect all symbols. For example, the lexicographical rank ofeuroparamongst the stringseureka,eurasia, andexcellsonly depends on its so calledrelevant prefixeuro. Thedistinguishing prefix sizeDof a set of strings is the number of symbols that actually need to be inspected to establish the lexicographical ordering of all strings. Efficient string sorters should beD-aware, i.e. their complexity should depend onDrather than on the total numberNof all symbols in all strings. While there are manyD-aware sorters in the sequential setting, there appear to be no such results in the PRAM model. We propose a framework yielding aD-aware modification of any existing PRAM string sorter. The derived algorithms are work-optimal with respect to their original counterpart: If the original algorithm requireswork, the derived one requireswork. The execution time increases only by a small factor that is logarithmic in the length of the longest relevant prefix. Our framework universally works for deterministic and randomized algorithms in all variations of the PRAM model, such that future improvements in (D-unaware) parallel string sorting will directly result in improvements inD-aware parallel string sorting.
登录
查看更多内容
DOI：
--
发表时间：
1994
期刊：
Proceedings of 8th International Parallel Processing Symposium
影响因子：
--
作者：
J. JáJá;K. Ryu;U. Vishkin
通讯作者：
U. Vishkin
快速确定性近似和精确并行排序
DOI：
--
发表时间：
1993
期刊：
ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
T. Hagerup;R. Raman
通讯作者：
R. Raman
最优并行字符串算法：排序、合并和计算最小值
DOI：
--
发表时间：
1994
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
T. Hagerup
通讯作者：
T. Hagerup
并行字符串样本排序
DOI：
--
发表时间：
2013
期刊：
Embedded Systems and Applications
影响因子：
--
作者：
Timo Bingmann;P. Sanders
通讯作者：
P. Sanders
DOI：
--
发表时间：
1991
期刊：
影响因子：
--
作者：
Ramachandran Vaidyanathan;C. Hartmann;P. Varshney
通讯作者：
P. Varshney