A closed frequent subgraph based containment query algorithm

Transportation network can be well described and analyzed through graph data. The analyzing methods include mine, query, and classification, etc. The improvement on the efficiency of scalable algorithms on large graph dataset is important in graph analyzing. Given a graph dataset and query graph, graph containment query retrieves graphs from the dataset which are subgraphs of query graph. In this paper, a frequent closed subgraph (CFG) based graph containment query algorithm is proposed. The algorithm selects discriminative-redundancy-aware CFG to build a tree structure index, which satisfies such query. Theoretical analysis and experimental evaluation are presented at the end. The results show that this algorithm is not only filtering out correlated indexed features efficiently, but also reducing subgraph isomorphism tests between query graph and indexed features effectively.