Discovering Frequent Geometric Subgraphs

As data mining techniques are being increasingly appliedto non-traditional domains, existing approaches forfinding frequent itemsets cannot be used as they cannotmodel the requirement of these domains. An alternate wayof modeling the objects in these data sets, is to use a graphto model the database objects. Within that model, the problemof finding frequent patterns becomes that of discoveringsubgraphs that occur frequently over the entire set ofgraphs. In this paper we present a computationally efficientalgorithm for finding frequent geometric subgraphs ina large collection of geometric graphs. Our algorithm isable to discover geometric subgraphs that can be rotation,scaling and translation invariant, and it can accommodateinherent errors on the coordinates of the vertices. Our experimentalresults show that our algorithms requires relativelylittle time, can accommodate low support values, andscales linearly on the number of transactions.