Mining Spatio-Temporal Graph Patterns

Abstract

Data mining in graph databases has received much attention. We have witnessed many algorithms proposed for mining frequent graphs. Inokuchi, Washio, and Nishimura (2002) and Karpis and Kumar (1998) introduce the Apriori-like algorithms, AGM and FSG, to mine the complete set of frequent graphs. However, both algorithms are not scalable as they require multiple scans of databases and tend to generate many candidates during the mining process. Subsequently, Yan and Han (2002) and Nijssen and Kok (2004) propose depth-first graph mining approaches called gSpan and Gaston, respectively. These approaches are essentially memory-based and their efficiencies decrease dramatically if the graph database is too large to fit into the main memory.