Abstract
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.
| Original language | English (US) |
|---|---|
| Title of host publication | Proceedings - 2002 IEEE International Conference on Data Mining, ICDM 2002 |
| Pages | 258-265 |
| Number of pages | 8 |
| State | Published - 2002 |
| Event | 2nd IEEE International Conference on Data Mining, ICDM '02 - Maebashi, Japan Duration: Dec 9 2002 → Dec 12 2002 |
Publication series
| Name | Proceedings - IEEE International Conference on Data Mining, ICDM |
|---|---|
| ISSN (Print) | 1550-4786 |
Other
| Other | 2nd IEEE International Conference on Data Mining, ICDM '02 |
|---|---|
| Country/Territory | Japan |
| City | Maebashi |
| Period | 12/9/02 → 12/12/02 |
Bibliographical note
Funding Information:This work was supported by NSF CCR-9972519, EIA-9986042, ACI-9982274, ACI-0133464 and ACI-0312828, by Army Research Office contract DA/DAAG55-98-1-0441, by the DOE ASCI program, by the Army High Performance Computing Research Center (AHPCRC) under the auspices of the Department of the Army, Army Research Laboratory (ARL) under Cooperative Agreement numbers DAAH04-95-C-0008 and DAAD19-01-2-0014, and by the Digital Technology Center at the University of Minnesota. The content of which does not necessarily reflect the position or the policy of the government, and no official endorsement should be inferred. Access to research and computing facilities was provided by the Digital Technology Center and the Minnesota Supercomputing Institute.
Copyright:
Copyright 2010 Elsevier B.V., All rights reserved.