BIDE

BIDE: efficient mining of frequent closed sequences. Previous studies have presented convincing arguments that a frequent pattern mining algorithm should not mine all frequent patterns but only the closed ones because the latter leads to not only more compact yet complete result set but also better efficiency. However, most of the previously developed closed pattern mining algorithms work under the candidate maintenance-and-test paradigm which is inherently costly in both runtime and space usage when the support threshold is low or the patterns become long. We present, BIDE, an efficient algorithm for mining frequent closed sequences without candidate maintenance. We adopt a novel sequence closure checking scheme called bidirectional extension, and prunes the search space more deeply compared to the previous algorithms by using the BackScan pruning method and the Scan-Skip optimization technique. A thorough performance study with both sparse and dense real-life data sets has demonstrated that BIDE significantly outperforms the previous algorithms: it consumes order(s) of magnitude less memory and can be more than an order of magnitude faster. It is also linearly scalable in terms of database size.


References in zbMATH (referenced in 36 articles )

Showing results 1 to 20 of 36.
Sorted by year (citations)

1 2 next

  1. Cule, Boris; Feremans, Len; Goethals, Bart: Efficiently mining cohesion-based patterns and rules in event sequences (2019)
  2. Kocheturov, A.; Pardalos, P. M.: Frequent temporal pattern mining with extended lists (2018)
  3. Liu, Qian; Ghosh, Shameek; Li, Jinyan; Wong, Limsoon; Ramamohanarao, Kotagiri: Discovering pan-correlation patterns from time course data sets by efficient mining algorithms (2018)
  4. Kemmar, Amina; Lebbah, Yahia; Loudni, Samir; Boizumault, Patrice; Charnois, Thierry: Prefix-projection global constraint and top-(k) approach for sequential pattern mining (2017)
  5. Tabaei Befrouei, Mitra; Wang, Chao; Weissenbacher, Georg: Abstraction and mining of traces to explain concurrency bugs (2016)
  6. Tatti, Nikolaj: Ranking episodes using a partition model (2015)
  7. Zhao, Yuhai; Li, Yuan; Yin, Ying; Sheng, Gang: Finding top-(k) covering irreducible contrast sequence rules for disease diagnosis (2015)
  8. Cule, Boris; Tatti, Nikolaj; Goethals, Bart: Marbles: mining association rules buried in long event sequences (2014)
  9. Achar, Avinash; Laxman, Srivatsan; Viswanathan, Raajay; Sastry, P. S.: Discovering injective episodes with general partial orders (2012)
  10. Tatti, Nikolaj; Cule, Boris: Mining closed strict episodes (2012)
  11. Kaneiwa, Ken; Kudo, Yasuo: A sequential pattern mining algorithm using rough set theory (2011) ioport
  12. Gouda, Karam; Hassaan, Mosab; Zaki, Mohammed J.: PRISM: an effective approach for frequent sequence mining via prime-block encoding (2010)
  13. Loekito, Elsa; Bailey, James; Pei, Jian: A binary decision diagram based approach for mining frequent subsequences (2010) ioport
  14. Bernshtein, L. S.; Kovalev, S. M.; Muravskii, A. V.: Models of representation of fuzzy temporal knowledge in databases of temporal series (2009)
  15. Chang, Joong Hyuk; Kum, Hye-Chung (Monica): Frequency-based load shedding over a data stream of tuples (2009) ioport
  16. Li, Guoliang; Feng, Jianhua; Wang, Jianyong; Zhou, Lizhu: Incremental sequence-based frequent query pattern mining from XML queries (2009) ioport
  17. Lo, David; Khoo, Siau-Cheng; Wong, Limsoon: Non-redundant sequential rules-theory and algorithm (2009) ioport
  18. Papapetrou, Panagiotis; Kollios, George; Sclaroff, Stan; Gunopulos, Dimitrios: Mining frequent arrangements of temporal intervals (2009) ioport
  19. Wang, Jianyong; Zhang, Yuzhou; Zhou, Lizhu; Karypis, George; Aggarwal, Charu C.: CONTOUR: an efficient algorithm for discovering discriminating subsequences (2009) ioport
  20. Chaoji, Vineet; Hasan, Mohammad Al; Salem, Saeed; Zaki, Mohammed J.: An integrated, generic approach to pattern mining: data mining template library (2008) ioport

1 2 next