DocumentCode :
1626974
Title :
A Partition-Based Approach to Graph Mining
Author :
Wang, Junmei ; Hsu, Wynne ; Li Lee, Mong ; Sheng, Chang
Author_Institution :
National University of Singapore
fYear :
2006
Firstpage :
74
Lastpage :
74
Abstract :
Existing graph mining algorithms typically assume that databases are relatively static and can fit into the main memory. Mining of subgraphs in a dynamic environment is currently beyond the scope of these algorithms. To bridge this gap, we first introduce a partition-based approach called PartMiner for mining graphs. The PartMiner algorithm finds the frequent subgraphs by dividing the database into smaller and more manageable units, mining frequent subgraphs on these smaller units and finally combining the results of these units to losslessly recover the complete set of subgraphs in the database. Next, we extend PartMiner to handle updates in the dynamic environment. Experimental results indicate that PartMiner is effective and scalable in finding frequent subgraphs, and outperforms existing algorithms in the presence of updates.
Keywords :
Algorithm design and analysis; Bridges; Data engineering; Data structures; Databases; Memory management; Partitioning algorithms; Spatiotemporal phenomena; Tree graphs;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Data Engineering, 2006. ICDE '06. Proceedings of the 22nd International Conference on
Print_ISBN :
0-7695-2570-9
Type :
conf
DOI :
10.1109/ICDE.2006.7
Filename :
1617442
Link To Document :
بازگشت