Prominent streak discovery in sequence data
Prominent streak discovery in sequence data
复制标题
DOI：
10.1145/2020408.2020601
复制
发表时间：
2011-08
期刊：
影响因子：
--
通讯作者：
Xiao Jiang;Chengkai Li;Ping Luo;Min Wang;Yong Yu
中科院分区：
文献类型：
--
作者：
Xiao Jiang;Chengkai Li;Ping Luo;Min Wang;Yong Yu
本文研究序列数据中显着条纹发现的问题。给定一个值序列，突出的条纹是仅由大（小）值组成的长连续子序列。为了找到突出的条纹，我们观察到突出的条纹是二维的天际线点——条纹间隔长度和间隔中的最小值。因此，我们的解决方案取决于将突出条纹发现的候选条纹生成和对候选条纹的天际线操作分开的两个步骤的想法。对于候选生成，我们提出了局部突出条纹（LPS）的概念。我们证明突出的条纹是 LPS 的子集，并且与暴力基线方法产生的候选者数量的二次方相比，LPS 的数量小于数据序列的长度。我们基于 LPS 的概念开发高效的算法。基于非线性LPS的方法（NLPS）将LPS的超集视为候选，并且基于线性LPS的方法（LLPS）进一步保证仅考虑LPS。使用多个真实数据集的实验结果验证了所提出方法的有效性，并显示出相对于基线方法的数量级性能改进。
This paper studies the problem of prominent streak discovery in sequence data. Given a sequence of values, a prominent streak is a long consecutive subsequence consisting of only large (small) values. For finding prominent streaks, we make the observation that prominent streaks are skyline points in two dimensions- streak interval length and minimum value in the interval. Our solution thus hinges upon the idea to separate the two steps in prominent streak discovery' candidate streak generation and skyline operation over candidate streaks. For candidate generation, we propose the concept of local prominent streak (LPS). We prove that prominent streaks are a subset of LPSs and the number of LPSs is less than the length of a data sequence, in comparison with the quadratic number of candidates produced by a brute-force baseline method. We develop efficient algorithms based on the concept of LPS. The non-linear LPS-based method (NLPS) considers a superset of LPSs as candidates, and the linear LPS-based method (LLPS) further guarantees to consider only LPSs. The results of experiments using multiple real datasets verified the effectiveness of the proposed methods and showed orders of magnitude performance improvement against the baseline method.