数据流下的容错和查询技术

［编者按］“文献导读”是为大数据领域的研究生和研究人员设置的栏目，本专栏将选取大数据与数据领域的前沿论文，并附以短评，帮助读者了解大数据领域的最新进展。

1. Tolerating Correlated Failures in Massively Parallel Stream Processing Engines

论文作者：Li Su, Yongluan Zhou

发表会议：ICDE 2016

所属方向：容错技术；并行计算

导读人：张浩然

［文献短评］：对于流处理引擎，容错技术可以分为被动和主动的方法。典型的被动方法定期检查处理任务的运行状态，并使用其最新检查点恢复其运行时状态来恢复故障的任务。主动方法通常使用备份节点来运行复制任务。一旦发生故障，活动副本可以以最小的延迟来处理失败的任务。然而，这两种方法在大规模并行流处理引擎中都有不足之处。被动方法会导致长的恢复延迟，主动方法需要额外的复制资源。本文提出了一种新的容错框架，即PPA。在PPA方案中，被动方法应用于所有任务，而只有一组选定的任务将被主动复制，主动复制任务的数量取决于可用的资源。如果没有活动副本的任务失败，则在恢复过程完成之前生成暂定输出。此外，本文提出了高效的算法来优化部分主动复制计划，从而最大化临时输出的质量。本文实现了PPA，并使用实时和合成数据集进行了大量实验，验证了所提出方法的有效性。

2. Scalable Pattern Sharing on Event Streams

论文作者：Medhabi Ray, Chuan Lei, Elke A.Rundensteiner

发表会议：SIGMOD 2016

所属方向：模式串匹配；事件数据流

导读人：林可

［文献短评］：事件流中的模式查找/匹配是一个经典的问题，即在由大量的事件E组成的数据流S中去查询一个模式串集合W。然而，目前的应用系统（例如交通监测）事件流中的数据量非常庞大，频率很高，因此对时效性的要求很高。这使得高效地处理事件流中的模式查找变得非常困难。为解决这一问题，本文提出了SPASS，即模式共享匹配算法和系统，为共享子串（文中有详细介绍）建立了估值模型。本文指出最优化模式串在数据流中的查询是一个NP难问题，即最小子串覆盖问题，并为该问题给出了一个多项式近似算法。基于算法和理论分析，本文设计实现了高效的运行系统，可应用于事件流中的模式查找或匹配问题。大量实验验证了该系统的有效性和效率。

3. Efficient Discovery of Longest-Lasting Correlation in SequenceDatabases

论文作者：Yuhong Li, Leong Hou U, ManLung Yiu, Zhiguo Gong

发表会议：VLDB 2016

所属方向：最长持续相似序列；序列数据

导读人：林可

［文献短评］：绝大多数序列数据库都是用欧拉距离或皮尔森相关系数作为两个序列的相似性度量函数。然而，使用以上两个方法都需要定义一个参数，即长度。可是在很多应用场景下并没有足够的先验知识，这使得提前定义长度难以实现，从而导致最长相似子序列的挖掘不够精确。因此，本文提出了一种空间限制的技术，即用于查询最长持续相关性子序列的方法。该方法可以在不必提前给出长度的情况下发现最长持续相似子序列，从而求解LCS问题。此外，本文提出了一个α-skipping技术来减小皮尔森相关系数的计算时间，并给出了一个大小可控的索引来有效地计算kLCS问题（kLCS问题是LCS问题的一个推广）。

（责任编辑：齐志鑫）

“大数据与数据科学家”公众号

主编：王宏志

特邀副主编：朱劼

副主编：丁小欧

责任编辑：齐志鑫，宋扬，万晓珑、魏龑，张荣恩

编辑： 陶颖安

-精彩内容，记得分享到朋友圈-