期刊名称:International Journal of Data Mining & Knowledge Management Process
印刷版ISSN:2231-007X
电子版ISSN:2230-9608
出版年度:2014
卷号:4
期号:5
页码:35
DOI:10.5121/ijdkp.2014.4503
出版社:Academy & Industry Research Collaboration Center (AIRCC)
摘要:The problem considered is that of finding frequent subpaths of a database of paths in a fixed undirectedgraph. This problem arises in applications such as predicting congestion in network and vehicular traffic.An algorithm, called AFS, based on the classic frequent itemset mining algorithm Apriori is developed, butwith significantly improved efficiency over Apriori from exponential in transaction size to quadraticthrough exploiting the underlying graph structure. This efficiency makes AFS feasible for practical inputpath sizes. It is also proved that a natural generalization of the frequent subpaths problem is not amenableto any solution quicker than Apriori.
关键词:AFS; Apriori; data mining; frequent subpath; frequent sub-structure; graph mining