Association Rule Mining using Path Systems in Directed Graphs


  • Subramanian Arumugam Senior Professor (Research) Kalasalingam University Anand Nagar, Krishnankoil
  • S. Sabeen Department of Computer Applications, Jaya Engineering College, Chennai-600054, INDIA.


Directed graphs, path system, in-degree, out-degree, association rule mining, frequent patterns, data mining.


A transaction database (TDB) consists of a set $I$ of items and a multiset $\mathcal{D}$ of nonempty subsets of $I,$ whose elements are called transactions. There are several algorithms for solving the popular and computationally expensive task of association rule mining from a TDB. In this paper we propose a data structure which consists of a directed graph $D$ (loops and multiple arcs are permitted) and a system of directed paths in $D$ to represent a TDB. We give efficient algorithms for generating the data structure, for extracting frequent patterns and  for association rule mining.  We also propose several graph theoretic parameters which lead to a better understanding of the system.

Author Biography

Subramanian Arumugam, Senior Professor (Research) Kalasalingam University Anand Nagar, Krishnankoil

National Centre for Advanced Research in Discrete Mathematics


R. Agrawal, T. Imielinski and A. Swami, Mining association rules between sets of items in large database, In Proc. of the ACM SIGMOD International Conference on Management of Data (ACM SIGMOD 93), Washington, USA, May 1993, 207-216.

G. Chartrand and L. Lesniak, Graphs and Digraphs, Chapman and Hall, CRC, 4th edition, 2005.

R. Agrawal and R. Srikant, Fast Algorithms for mining association rules, In Proc. of the 20th International Conference on Very Large Database (VLDB' 94), Santiago, Chile, June 1994.

J. Han, J. Pei and Y. Yin, Mining Frequent Patterns without Candidate Generation, In Proc. of the 2000 ACM SIGMOD International Conference on Management of Data, Dallas, Texas, USA, May 2000.

S. Brin, R. Motwani, J.D. Ullman and S. Tsur, Dynamic itemset counting and implications rules for masket basket data, In Proc. of the ACM SIGMOD International Conference on Management Data, 1997.

M. Hontsma and A. Swami, Set oriented mining for association rules in relatrend database, The technical report RJ9567, IBM Almaden Research Centre, San Jose, California, October 1993. J. Han and M. Kamber, Data minining, Concepts and Applications, Elsevier Inc., (2006).



Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.