后缀树的并行构造算法

后缀树是一种非常重要的数据结构,它在与字符串处理相关的各种领域里有着非常广泛的应用。构造后缀树是应用后缀树解决问题的前提和关键。虽然很多现有的后缀树构造算法都是线性时间和空间的,但是,当被索引的字符串的长度很长时,构造其后缀树所消耗的时间和空间仍将非常巨大,这极大地限制了后缀树的实际应用。而并行技术是解决这一问题的很好途径,因此人们提出了后缀树的并行构造算法。本文对后缀树的三种并行构造算法进行了综述,通过系统的比较和分析,总结出当前存在的问题,并指明了下一步的研究方向。

基于闭包系统划分的概念格并行构造算法

随着处理的形式背景的增大,概念格的时空复杂度也会随着急剧增大。研究新的方法和手段来构造概念格,是概念格技术应用于大型复杂数据系统的前提,提高其构造效率的一种有效途径是利用高性能并行计算机和网络并行计算的能力,因此概念格的并行构造算法已成为众多学者的一个新的研究方向。概念格的并行构造思想就是根据不同的原理,采用分治策略,通过对形式背景的拆分,形成分布存储的多个子背景,然后构造相应的子概念格,再由子概念格的合并得到所需的概念格。目前建格算法的分布处理研究主要有形式背景的并置和叠置以及形式背景的折叠搜索子空间划分两种方法,本文在总结研究这两种方法的基础上,基于偏序集上闭包系统分解的思想,对提出的闭包系统划分为多个子闭包系统的判定定理进行了证明,使闭包系统的分解既不会产生冗余信息,也不会使信息丢失,并把所提出的判定定理用于概念格的并行处理,提出了一个新的基于闭包划分的概念格并行生成算法——Para-Pruning算法。通过实验,利用随机生成的数据集同经典NextClosure算法进行比较分析,验证了新算法的正确性和有效性。

MapReduce框架下近似概念格的并行构造算法

具有缺值的形式背景称为不完备形式背景,相应的概念格扩展模型称为近似概念格。近似概念格构造中,在数据规模大的情况下采用串行算法效率低,完备形式背景下概念格并行构造算法不适用于不完备形式背景。针对这些问题,对近似概念格的特征进行深入分析,提出了在MapReduce框架下的两种分布式构造算法,包括一种并行合并算法和一种增量式并行算法。实验结果表明,相比串行算法,两种并行构造算法可以提高近似概念格的建格效率。

Efficient Configuration Space Construction and Optimization for Motion Planning

The configuration space is a fundamental concept that is widely used in algorithmic robotics. Many applications in robotics, computer-aided design, and related areas can be reduced to computational problems in terms of configuration spaces. In this paper, we survey some of our recent work on solving two important challenges related to configuration spaces： ~ how to efficiently compute an approximate representation of high-dimensional configuration spaces; and how to efficiently perform geometric proximity and motion planning queries （n high-dimensional configuration spaces. We present new configuration space construction algorithms based on machine learning and geometric approximation techniques. These algorithms perform collision queries on many configuration samples. The collision query results are used to compute an approximate representation for the configuration space, which quickly converges to the exact configuration space. We also present parallel GPU-based algorithms to accelerate the performance of optimization and search computations in configuration spaces. In particular, we design efficient GPU-based parallel k-nearest neighbor and parallel collision detection algorithms and use these algorithms to accelerate motion planning.

Tree-Structured Parallel Regeneration for Multiple Data Losses in Distributed Storage Systems Based on Erasure Codes

To reduce the time required to complete the regeneration process of erasure codes, we propose a Tree-structured Parallel Regeneration (TPR) scheme for multiple data losses in distributed storage systems. Under the scheme, two algorithms are proposed for the construction of multiple regeneration trees, namely the edge-disjoint algorithm and edge-sharing algorithm. The edge-disjoint algorithm constructs multiple independent trees, and is simple and appropriate for environments where newcomers and their providers are distributed over a large area and have few intersections. The edge-sharing algorithm constructs multiple trees that compete to utilize the bandwidth, and make a better utilization of the bandwidth, although it needs to measure the available band-width and deal with the bandwidth changes; it is therefore difficult to implement in practical systems. The parallel regeneration for multiple data losses of TPR primarily includes two optimizations: firstly, transferring the data through the bandwidth optimized-paths in a pipe-line manner; secondly, executing data regeneration over multiple trees in parallel. To evaluate the proposal, we implement an event-based simulator and make a detailed comparison with some popular regeneration methods. The quantitative comparison results show that the use of TPR employing either the edge-disjoint algorithm or edge-sharing algorithm reduces the regeneration time significantly.