{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T11:49:10Z","timestamp":1751629750987,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,6,1]],"date-time":"2014-06-01T00:00:00Z","timestamp":1401580800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["IIS-1018865 and CCF-1117369"],"award-info":[{"award-number":["IIS-1018865 and CCF-1117369"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007302","name":"HP Labs","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007302","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-1018865 and CCF-1117369"],"award-info":[{"award-number":["IIS-1018865 and CCF-1117369"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2014,6]]},"abstract":"<jats:p>This article 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, such as consecutive games of outstanding performance in sports, consecutive hours of heavy network traffic, and consecutive days of frequent mentioning of a person in social media. Prominent streak discovery provides insightful data patterns for data analysis in many real-world applications and is an enabling technique for computational journalism. Given its real-world usefulness and complexity, the research on prominent streaks in sequence data opens a spectrum of challenging problems.<\/jats:p>\n          <jats:p>\n            A baseline approach to finding prominent streaks is a quadratic algorithm that exhaustively enumerates all possible streaks and performs pairwise streak dominance comparison. For more efficient methods, we make the observation that prominent streaks are in fact skyline points in two dimensions\u2014streak interval length and minimum value in the interval. Our solution thus hinges on 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 the brute-force baseline method. We develop efficient algorithms based on the concept of LPS. The nonlinear local prominent streak (NLPS)-based method considers a superset of LPSs as candidates, and the linear local prominent streak (LLPS)-based method further guarantees to consider only LPSs. The proposed properties and algorithms are also extended for discovering general top-\n            <jats:italic>k<\/jats:italic>\n            , multisequence, and multidimensional prominent streaks. 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.\n          <\/jats:p>","DOI":"10.1145\/2601439","type":"journal-article","created":{"date-parts":[[2014,6,3]],"date-time":"2014-06-03T12:31:21Z","timestamp":1401798681000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Discovering General Prominent Streaks in Sequence Data"],"prefix":"10.1145","volume":"8","author":[{"given":"Gensheng","family":"Zhang","sequence":"first","affiliation":[{"name":"The University of Texas at Arlington"}]},{"given":"Xiao","family":"Jiang","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University"}]},{"given":"Ping","family":"Luo","sequence":"additional","affiliation":[{"name":"HP Labs China"}]},{"given":"Min","family":"Wang","sequence":"additional","affiliation":[{"name":"Google Research"}]},{"given":"Chengkai","family":"Li","sequence":"additional","affiliation":[{"name":"The University of Texas at Arlington"}]}],"member":"320","published-online":{"date-parts":[[2014,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57301-1_5"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/645921.673155"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/645480.655281"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-2836(05)80360-2"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1979.234200"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656550"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11687238_30"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2003.1260846"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 5th Biennial Conference on Innovative Data Systems Research (CIDR\u201911)","author":"Cohen Sarah","year":"2011","unstructured":"Sarah Cohen , Chengkai Li , Jun Yang , and Cong Yu . 2011 . Computational journalism: A call to arms to database researchers . In Proceedings of the 5th Biennial Conference on Innovative Data Systems Research (CIDR\u201911) . 148--151. Sarah Cohen, Chengkai Li, Jun Yang, and Cong Yu. 2011. Computational journalism: A call to arms to database researchers. In Proceedings of the 5th Biennial Conference on Innovative Data Systems Research (CIDR\u201911). 148--151."},{"volume-title":"Fast Subsequence Matching in Time-Series Databases","author":"Faloutsos Christos","key":"e_1_2_1_11_1","unstructured":"Christos Faloutsos , M. Ranganathan , and Yannis Manolopoulos . 1993. Fast Subsequence Matching in Time-Series Databases . University of Maryland at College Park , College Park, MD . Christos Faloutsos, M. Ranganathan, and Yannis Manolopoulos. 1993. Fast Subsequence Matching in Time-Series Databases. University of Maryland at College Park, College Park, MD."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009726021843"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.70"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020601"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287394"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321910"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2005.01.025"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367854"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2011.16"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061320"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.77"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1189769.1189774"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.18626"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1625275.1625445"},{"volume-title":"Advances in Neural Information Processing Systems","author":"Smyth Padhraic","key":"e_1_2_1_25_1","unstructured":"Padhraic Smyth . 1997. Clustering sequences with hidden Markov models . In Advances in Neural Information Processing Systems . MIT Press , Cambridge, MA , 648--654. Padhraic Smyth. 1997. Clustering sequences with hidden Markov models. In Advances in Neural Information Processing Systems. MIT Press, Cambridge, MA, 648--654."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/645337.650382"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/645927.672217"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.84"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.149"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/11775300_28"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142529"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972733.15"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 14th International Conference on Data Engineering. 201--208","author":"Yi Byoung-Kee","year":"1998","unstructured":"Byoung-Kee Yi , H. V. Jagadish , and Christos Faloutsos . 1998 . Efficient retrieval of similar time sequences under time warping . In Proceedings of the 14th International Conference on Data Engineering. 201--208 . DOI: http:\/\/dx.doi.org\/10.1109\/ICDE.1998.655778 10.1109\/ICDE.1998.655778 Byoung-Kee Yi, H. V. Jagadish, and Christos Faloutsos. 1998. Efficient retrieval of similar time sequences under time warping. In Proceedings of the 14th International Conference on Data Engineering. 201--208. DOI: http:\/\/dx.doi.org\/10.1109\/ICDE.1998.655778"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007652502315"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1099554.1099610"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2601439","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2601439","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:00:53Z","timestamp":1750276853000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2601439"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["10.1145\/2601439"],"URL":"https:\/\/doi.org\/10.1145\/2601439","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2014,6]]},"assertion":[{"value":"2013-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}