1. 问题背景

通用后缀树是一种对序列集合中的所有序列的后缀进行索引形成的数据结构，在诸多领域具有广泛的应用需求。然而，由于其构建过程涉及大量的计算和复杂的I/O，目前尚缺少大数据应用场景下高效可扩展的大规模通用后缀树构建算法。

本工作研究设计的通用后缀树构建算法LMdst在2017年第三届全国高校云计算应用创新大赛全国总决赛上取得技能赛第一名的成绩，荣获技能赛一等奖。

2. 算法目标

1. 该算法需要基于分布式场景设计，充分发挥分布式存储以及并行计算的优势，实现良好的可扩展性。
2. 该算法需要具有良好的通用性，可以针对不同的输入序列形态（例如很多短序列、一条或少量长序列、长度差异大的若干序列等）均具有良好的处理能力。
3. 该算法需要在保证以上两点技术目标的基础上，尽可能优化计算、I/O和网络开销，提升算法实际性能。

3. LMdst算法设计

LMdst将整个通用后缀树的构建任务划分成若干后缀子树的构建任务，然后再并行地实现各个后缀子树的构建，并且在主节点上维护各个后缀子树的连接关系。亦即，LMdst将通用后缀树构建任务解构为划分子树和构建子树两大环节。

图 2

划分子树环节

任务目标：将通用后缀树构建任务划分成若干后缀子树构建任务，并分配到不同的计算单元上。

基本问题：

1. 目前缺乏一个并行的划分子树算法。
2. 尚未有研究工作考虑划分子树算法的通用性，使得其应对各种输入形态（例如极长的序列、大量短序列、长度差异大的若干序列）都有相近的性能。
3. 尚未有研究工作讨论在分布式场景下的如何分配子树构建任务会使得通用后缀树构建最为高效。

本研究的贡献：

1. 研究提出基于输入片段的数据划分方式，达到良好的通用性。
2. 研究提出基于trie的并行划分子树算法，利用trie的结构特性高效地划分子树。
3. 研究提出基于装箱和整数划分的构建任务分配算法，既充分利用计算资源又考虑负载均衡，使得通用后缀树构建过程整体高效。

图 3

构建子树环节

任务目标：构建出所有后缀子树。

基本问题：是通用后缀树构建的核心流程，计算复杂，I/O巨大。现有研究尚未借助并行进一步提升计算性能。

本研究的贡献：

1. 研究提出了一套基于多模匹配和多路归并的后缀子树批量构建流程，充分利用并行计算，扫描一次输入后构建出一批后缀子树。
2. 研究设计了Lcp-range数据结构用来表示序列，结构简洁、占用空间小，显著降低了序列比较和传输的代价。
3. 研究提出了基于Lcp-range的多路归并序列排序算法，充分利用数据并行高效排序序列。
4. 研究设计了基于整合输入和排序请求的I/O访问优化策略，优化构建子树环节的I/O性能。

图 4

综上，LMdst算法的流程如下：

图 5

4. 技术实现方案与优化

随机场景下的理论分析：

复杂度特性：\(O(nlog_{2}n)\)，充分利用数据并行，减少了大部分过程中的规模基数。

I/O及网络特性：对I/O进行了重点优化，实现了所有过程的顺序I/O，并尽可能减少I/O次数、数据量以及网络传输数据量。

图 6

基于Apache Spark平台实现了LMdst与现有有代表性的ERa算法，并进行性能对比测试：

图 7

结论及分析：随着输入规模的增加，LMdst领先ERa的幅度越来越大。原因如下：

1. LMdst拥有更好的子树构建任务分配策略，既能充分利用每个计算单元的计算资源又能在分布式场景中保持良好的负载均衡。
2. ERa算法的划分子树环节严格串行，而且I/O次数和数据量都高于本文提出的基于trie的并行划分子树算法。因此，划分在子树阶段过程，LMdst领先ERa的幅度会随着数据量的增加而增大。
3. LMdst充分利用数据并行实现后缀子树的并行构建，并对I/O及网络通信等方面进行了深度优化，性能稳定高于ERa。

数据扩展性：

图 8

结论及分析：LMdst随着输入数据规模的增大，运行时间基本呈线性增长的趋势，而且略优于线性增长的理想状态。因为LMdst的几乎所有过程都是并行过程，而且针对每个并行过程设计的负载均衡策略均有效。

结果参考：WaveFront算法在1024核的IBM Blue Gene超级计算机上编码长度为2.6G的DNA序列，耗时15分钟。也就是说LMdst使用了25分之一的计算资源，获得了类似的性能。

通用性测试：

图 9

结论及分析：不同的输入形态对LMdst性能的影响较为微小。这是因为LMdst预先的整合输入阶段会首先将所有输入整合，在这之后的所有过程便均和原始输入没有任何关系。而整合输入阶段对LMdst的性能影响很小，所以LMdst对各种输入形态都能高效地构建通用后缀树，具有良好的通用性。

5. 总结

本文研究提出并设计实现了一个大规模高效可扩展的通用后缀树构建分布并行化算法LMdst，它能处理各种规模、各种形态的序列数据输入，并能充分利用数据并行高效地构建通用后缀树。本文的工作内容以及贡献点如下：

1. 研究提出了一种基于Lcp多路归并的高效可扩展的大规模通用后缀树构建分布并行算法LMdst。LMdst分为划分子树和构建子树两大环节，高度数据并行，可以充分利用分布式存储和并行计算提升计算性能。
2. 在子树划分环节，研究实现了基于trie树的分布并行化子树划分方法，可以高效并行化统计子序列频数进而划分子树；进一步提出了一种基于输入片段的数据划分方法，屏蔽了输入序列形态、数据存储等因素对算法性能的影响。因而使LMdst算法的划分子树环节具有良好的通用性。
3. 在子树构建环节，研究提出了基于Lcp-range的高效序列比较方法和基于败者树多路归并的后缀子树并行构建方法。以此为基础，设计实现了一套综合考虑计算和I/O的后缀子树批量构建优化方法，充分利用数据并行加速后缀子树的构建。此外，借助基于输入片段的数据划分方法，LMdst在本环节同样具有良好的通用性。
4. 研究提出了基于装箱和整数划分的子树构建任务分配方法，既能充分利用计算资源又能在分布式场景中保持良好的负载均衡。
5. 对算法进行了计算复杂度、IO与网络通信开销等方面的理论分析，最终基于Apache Spark平台设计实现了大规模通用后缀树构建分布并行算法LMdst，实验结果与理论分析结果基本一致，且实验结果表明，LMdst在大规模场景下具有优异的计算性能、近线性的可扩展性以及良好的通用性。