Journal of Computer Science

Support Measure Admissibility Based on Operations on Instance Graphs

Ford Lumban Gaol

DOI : 10.3844/jcssp.2007.708.716

Journal of Computer Science

Volume 3, Issue 9

Pages 708-716


The concept of support is central to data mining. While the definition of support in transaction databases is intuitive and simple, that is not the case in graph datasets and databases. Most mining algorithms require the support of a pattern to be no grater than that of its subpatterns, a property called anti-monotonicity or admissibility. This study examines the requirements for admissibility of a support measure. Support measure for mining graphs are usually based on the notion of an instance graph-a graph representing all the instances of the pattern in a database and their intersection properties. Necessary and sufficient conditions for support measure admissibility, based on operations on instance graphs, are developed and proved. The sufficient conditions are used to prove ad admissibility of one support measure-the size of the independent set in the instance graph. Conversely, the necessary conditions are used to quickly show that some other support measures, such as weighted count of instances, are not admissible.


© 2007 Ford Lumban Gaol. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.