skip to main content
10.1145/1516241.1516320acmconferencesArticle/Chapter ViewAbstractPublication PagesicuimcConference Proceedingsconference-collections
research-article

Efficient serial episode mining with minimal occurrences

Published: 15 February 2009 Publication History

Abstract

Recently, knowledge discovery in large data increases its importance in various fields. Especially, data mining from time-series data gains much attention. This paper studies the problem of finding frequent episodes appearing in a sequence of events. We propose an efficient depth-first search algorithm for mining frequent serial episodes in a given event sequence using the notion of right-minimal occurrences. Then, we present some techniques for speeding up the algorithm, namely, occurrence-deliver and tail-redundancy pruning. Finally, we ran experiments on real datasets to evaluate the usefulness of the proposed methods.

References

[1]
S. Abiteboul, P. Buneman, D. Suciu, Data on the Web: From Relations to Semistructured Data and XML, Morgan Kaufmann, 1999.
[2]
A. V. Aho, J. E. Hopcroft, J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
[3]
H. Arimura, T. Uno, An Efficient Polynomial Space and Polynomial Delay Algorithm for Enumeration of Maximal Motifs in a Sequence, J. Comh. Optim., Vol.13, 243--262, 2006.
[4]
Hiroki Arimura and Takeaki Uno, Mining Maximal Flexible Patterns in a Sequence, Proc. LLLL2007, LNAI4914, Springer, 2008.
[5]
J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal, M. Hsu, PrefixSpan: Mining Sequential Patterns by Prefix-Projected Growth, Proc. IEEE ICDE 2001, 215--224, 2001.
[6]
Heikki Mannila, Hannu Toivonen, A. Inkeri Verkamo, Discovery of Frequent Episodes in Event Sequence, Data Mining and Knowledge Discovery, Vol. 1, 259--289, 1997.
[7]
Y. Uchida, An efficient algorithm for enumerating episodes in the window and closed episodes, Kyushu Univ ISEE, master thesis, 2004.
[8]
T. Uno, H. Arimura, Data intensive computing No.2 - An algorithm for enumerating frequent item sets -, Journal of the JSAE, Vol. 17(2), 2007.
[9]
Uno's Homepage, Nii, http://research.nii.ac.jp/ uno/index-j.html
[10]
T. Uno, T. Asai, Y. Uchida, H. Arimura, An efficient algorithm for enumerating closed patterns in transaction databases, In DS'04, LNAI 3245, 16--30, 2004.
[11]
J. Wang, J. Han, BIDE: Efficient Mining of Frequent Closed Sequences, Proc. IEEE ICDE 2004, 79--90, 2004.

Cited By

View all
  • (2015)Constraint-Based Sequence Mining Using Constraint ProgrammingIntegration of AI and OR Techniques in Constraint Programming10.1007/978-3-319-18008-3_20(288-305)Online publication date: 16-Apr-2015
  • (2013)Mining frequent partite episodes with partwise constraintsProceedings of the 2nd International Conference on New Frontiers in Mining Complex Patterns10.1007/978-3-319-08407-7_8(117-131)Online publication date: 27-Sep-2013
  • (2012)Predicting Behaviors of Residents by Modeling Preceding Action Transition from TrajectoriesJournal of Robotics and Mechatronics10.20965/jrm.2012.p032024:2(320-329)Online publication date: 20-Apr-2012
  • Show More Cited By

Index Terms

  1. Efficient serial episode mining with minimal occurrences

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      ICUIMC '09: Proceedings of the 3rd International Conference on Ubiquitous Information Management and Communication
      February 2009
      704 pages
      ISBN:9781605584058
      DOI:10.1145/1516241
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 15 February 2009

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. closed sequences
      2. depth-first algorithm
      3. frequent episode mining

      Qualifiers

      • Research-article

      Conference

      ICUIMC '09
      Sponsor:

      Acceptance Rates

      Overall Acceptance Rate 251 of 941 submissions, 27%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)0
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 13 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2015)Constraint-Based Sequence Mining Using Constraint ProgrammingIntegration of AI and OR Techniques in Constraint Programming10.1007/978-3-319-18008-3_20(288-305)Online publication date: 16-Apr-2015
      • (2013)Mining frequent partite episodes with partwise constraintsProceedings of the 2nd International Conference on New Frontiers in Mining Complex Patterns10.1007/978-3-319-08407-7_8(117-131)Online publication date: 27-Sep-2013
      • (2012)Predicting Behaviors of Residents by Modeling Preceding Action Transition from TrajectoriesJournal of Robotics and Mechatronics10.20965/jrm.2012.p032024:2(320-329)Online publication date: 20-Apr-2012
      • (2012)Analyzing consumers’ shopping behavior using RFID data and pattern miningAdvances in Data Analysis and Classification10.1007/s11634-012-0117-z6:4(355-365)Online publication date: 6-Oct-2012
      • (2011)Behavior prediction from trajectories in a house by estimating transition model using stay points2011 IEEE/RSJ International Conference on Intelligent Robots and Systems10.1109/IROS.2011.6094439(3419-3425)Online publication date: Sep-2011
      • (2010)Extracting promising sequential patterns from RFID data using the LCM sequenceProceedings of the 14th international conference on Knowledge-based and intelligent information and engineering systems: Part III10.5555/1885450.1885483(244-253)Online publication date: 8-Sep-2010
      • (2010)Extracting Promising Sequential Patterns from RFID Data Using the LCM SequenceKnowledge-Based and Intelligent Information and Engineering Systems10.1007/978-3-642-15393-8_28(244-253)Online publication date: 2010

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media