2011 ProminentStreakDiscoveryinSeque

• (Jiang et al., 2011) ⇒ Xiao Jiang, Chengkai Li, Ping Luo, Min Wang, and Yong Yu. (2011). “Prominent Streak Discovery in Sequence Data.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020601

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Prominent+Streak+Discovery+in+Sequence+Data
• http://dl.acm.org/citation.cfm?id=2020408.2020601&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; data mining; performance; sequence database; skyline query; time-series database

Abstract

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) value]]s. 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 isthe 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.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 ProminentStreakDiscoveryinSeque	Ping Luo Yong Yu Xiao Jiang Chengkai Li Min Wang			Prominent Streak Discovery in Sequence Data				10.1145/2020408.2020601		2011