LCM

LCM: An Efficient Algorithm for Enumerating Frequent Closed Item Sets. In this paper, we propose three algorithms LCM- freq, LCM, and LCMmax for mining all frequent sets, frequent closed item sets, and maximal frequent sets, respectively, from transaction databases. The main theoretical contribution is that we construct tree-shaped transversal routes composed of only frequent closed item sets, which is induced by a parent-child relationship defined on frequent closed item sets. By traversing the route in a depth-first manner, LCM finds all frequent closed item sets in polynomial time per item set, without storing previously obtained closed item sets in memory. Moreover, we introduce several algorithmic techniques using the sparse and dense structures of input data. Algorithms for enumerating all frequent item sets and maximal frequent item sets are obtained from LCM as its variants. By computational experiments on real world and synthetic databases to compare their performance to the previous algorithms, we found that our algorithms are fast on large real world datasets with natural dis- tributions such as KDD-cup2000 datasets, and many other synthetic databases.


References in zbMATH (referenced in 41 articles )

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

1 2 3 next

  1. Janostik, Radek; Konecny, Jan; Krajča, Petr: LCM from FCA point of view: a CbO-style algorithm with speed-up features (2022)
  2. Makhalova, Tatiana; Buzmakov, Aleksey; Kuznetsov, Sergei O.; Napoli, Amedeo: Introducing the closure structure and the GDPM algorithm for mining and understanding a tabular dataset (2022)
  3. Fournier-Viger, Philippe; Yang, Peng; Kiran, Rage Uday; Ventura, Sebastian; Luna, José María: Mining local periodic patterns in a discrete sequence (2021)
  4. Janostik, Radek; Konecny, Jan; Krajča, Petr: Pruning techniques in LinCbO for computation of the Duquenne-Guigues basis (2021)
  5. Reynolds, David; Carvalho, Luis: Latent association graph inference for binary transaction data (2021)
  6. Fujita, Takahiro; Hatano, Kohei; Takimoto, Eiji: Boosting over non-deterministic ZDDs (2020)
  7. Lee, Taito; Matsushima, Shin; Yamanishi, Kenji: Grafting for combinatorial binary model using frequent itemset mining (2020)
  8. Fournier-Viger, Philippe; Li, Zhitian; Lin, Jerry Chun-Wei; Kiran, Rage Uday; Fujita, Hamido: Efficient algorithms to identify periodic patterns in multiple sequences (2019)
  9. Denzumi, Shuhei; Kawahara, Jun; Tsuda, Koji; Arimura, Hiroki; Minato, Shin-ichi; Sadakane, Kunihiko: DenseZDD: a compact and fast index for families of sets (2018)
  10. Benhamou, Belaïd: Local and global symmetry breaking in itemset mining (2017)
  11. Dzyuba, Vladimir; van Leeuwen, Matthijs; De Raedt, Luc: Flexible constrained sampling with guarantees for pattern mining (2017)
  12. Li, Yao; Liu, Lingqiao; Shen, Chunhua; van den Hengel, Anton: Mining mid-level visual patterns with deep CNN activations (2017)
  13. Crespelle, Christophe; Latapy, Matthieu; Phan, Thi Ha Duong: On the termination of some biclique operators on multipartite graphs (2015)
  14. Hadzic, Fedja; Hecker, Michael; Tagarelli, Andrea: Ordered subtree mining via transactional mapping using a structure-preserving tree database schema (2015)
  15. Baixeries, Jaume; Kaytoue, Mehdi; Napoli, Amedeo: Characterizing functional dependencies in formal concept analysis with pattern structures (2014)
  16. Baralis, Elena; Cagliero, Luca; Cerquitelli, Tania; D’Elia, Vincenzo; Garza, Paolo: Expressive generalized itemsets (2014)
  17. Fernando, Basura; Fromont, Elisa; Tuytelaars, Tinne: Mining mid-level features for image classification (2014) ioport
  18. Negrevergne, Benjamin; Termier, Alexandre; Rousset, Marie-Christine; Méhaut, Jean-François: \textscPara\textscMiner: a generic pattern mining algorithm for multi-core architectures (2014)
  19. Ouchi, Koji; Nakamura, Atsuyoshi; Kudo, Mineichi: An efficient construction and application usefulness of rectangle greedy covers (2014) ioport
  20. Spyropoulou, Eirini; De Bie, Tijl; Boley, Mario: Interesting pattern mining in multi-relational data (2014)

1 2 3 next