TY - GEN
T1 - Discovering frequent geometric subgraphs
AU - Kuramochi, Michihiro
AU - Karypis, George
PY - 2002/12/1
Y1 - 2002/12/1
N2 - As data mining techniques are being increasingly applied to non-traditional domains, existing approaches for finding frequent itemsets cannot be used as they cannot model the requirement of these domains. An alternate way of modeling the objects in these data sets, is to use a graph to model the database objects. Within that model, the problem of finding frequent patterns becomes that of discovering subgraphs that occur frequently over the entire set of graphs. In this paper we present a computationally efficient algorithm for finding frequent geometric subgraphs in a large collection of geometric graphs. Our algorithm is able to discover geometric subgraphs that can be rotation, scaling and translation invariant, and it can accommodate inherent errors on the coordinates of the vertices. Our experimental results show that our algorithms requires relatively little time, can accommodate low support values, and scales linearly on the number of transactions.
AB - As data mining techniques are being increasingly applied to non-traditional domains, existing approaches for finding frequent itemsets cannot be used as they cannot model the requirement of these domains. An alternate way of modeling the objects in these data sets, is to use a graph to model the database objects. Within that model, the problem of finding frequent patterns becomes that of discovering subgraphs that occur frequently over the entire set of graphs. In this paper we present a computationally efficient algorithm for finding frequent geometric subgraphs in a large collection of geometric graphs. Our algorithm is able to discover geometric subgraphs that can be rotation, scaling and translation invariant, and it can accommodate inherent errors on the coordinates of the vertices. Our experimental results show that our algorithms requires relatively little time, can accommodate low support values, and scales linearly on the number of transactions.
UR - http://www.scopus.com/inward/record.url?scp=45149090173&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=45149090173&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:45149090173
SN - 0769517544
SN - 9780769517544
T3 - Proceedings - IEEE International Conference on Data Mining, ICDM
SP - 258
EP - 265
BT - Proceedings - 2002 IEEE International Conference on Data Mining, ICDM 2002
T2 - 2nd IEEE International Conference on Data Mining, ICDM '02
Y2 - 9 December 2002 through 12 December 2002
ER -