Abstract:  Sequential data are prevalent in many real world applications. The quality evaluation on sequential data, which attracts the attentions from both academic research and industry fields, is important and prerequisite for extracting knowledge from the sequential data. Recently, a method using the probabilistic suffix tree has been proposed for evaluating the sequential data quality. However, this method cannot deal with the large-scale data set. To break this limitation, this paper proposes a Spark-based algorithm, called STALK (sequential data quality evaluation with Spark), for evaluating the quality of large-scale sequential data. Moreover, this paper uses the novel pruning strategies to improve the efficiency of STALK. Specifically, on the Spark platform, the large-scale sequential data are efficiently used to generate model, and the data quality of query sequence can be evaluated according to the generated model rapidly. Experiments on real-world sequential data sets demonstrate that STALK is effective, efficient and scalable.

Key words:  data quality, probabilistic suffix tree, Spark, parallel computing

摘要： 随着序列数据在实际中的广泛应用，序列数据质量评价成为学术、工业等众多领域的热门研究问题。目前主流的序列数据质量评价方法是基于概率后缀树模型进行数据质量评价，然而这种方法难以实现对大规模数据的处理。为解决此问题，提出了基于Spark的序列数据质量评价算法STALK（sequential data quality evaluation with Spark），并且采用了改进的剪枝策略来提高算法效率。具体地，在Spark平台下，利用大规模序列数据高效建立生成模型，并根据生成模型对查询序列的数据质量进行快速评价。最后通过真实序列数据集验证了STALK算法的有效性、执行效率和可扩展性。

关键词: 数据质量, 概率后缀树, Spark, 并行计算