Mining maximal frequent patterns is significant in many fields, but the mining efficiency is often low. The bottleneck lies in too many candidate subgraphs and extensive subgraph isomorphism tests. In this paper we propose an efficient mining algorithm. There are two key ideas behind the proposed methods. The first is to divide each edge of every certain graph (converted from equivalent uncertain graph) and build search tree, avoiding too many candidate subgraphs. The second is to search the tree built in the first step in order, avoiding extensive subgraph isomorphism tests. The evaluation of our approach demonstrates the significant cost savings with respect to the state-of-the-art approach not only on the real-world datasets as well as on synthetic uncertain graph databases.
AsthanaS., KingO.D., GibbonsF.D. and RothF.P., Predicting protein complex membership using probabilistic network reliability, Genome Research14(6) (2004), 1170–1175.
2.
GhoshJ., NgoH.Q., YoonS. and QiaoC., On a routing problem within probabilistic graphs and its application to intermittently connected networks, Infocom IEEE International Conference on Computer Communications (2007), 1721–1729.
3.
SuciuD. and DalviN., Foundations of probabilistic answers to queries, ACM SIGMOD International Conference on Management of Data (1) (2005), 125–153.
4.
DalviN. and SuciuD., Management of probabilistic data: Foundations and challenges, ACMSIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (5) (2007), 1–12.
5.
YuanY., WangG., WangH. and ChenL., Efficient subgraph search over large uncertain graphs, Proceedings of the VLDB Endowment4(11) (2011), 876–886.
6.
AgrawalR. and SrikantR., Fast Algorithms for Mining Association Rules, 20th International Conference on Very Large Data Bases (1994), 487–499.
7.
HanJ., PeiJ., YinY. and MaoR., Mining frequent patterns without candidate generation: A frequent-pattern tree approach, Data Mining and Knowledge Discovery8(1) (2004), 53–87.
8.
BhatiaV. and RaniR., Ap-FSM: A parallel algorithm for approximate frequent subgraph mining using Pregel, Expert Systems With Applications106 (2018), 217–232.
9.
BerneckerT., KriegelH.P., RenzM., VerheinF. and ZuefleA., Probabilistic frequent itemset mining in uncertain databases, ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2009), 119–127.
10.
ChuiC.K., KaoB. and HungE., Mining frequent itemsets from uncertain data, Lecture Notes in Computer Science (2007), 47–58.
11.
LeungC.K.S. and HaoB., Mining of frequent itemsets from streams of uncertain data, International Conference on Data Engineering (2009), 1663–1670.
12.
SunL., ChengR., CheungD.W. and ChengJ., Mining uncertain datawith probabilistic guarantees, ACMSIGKDD International Conference on Knowledge Discovery and Data Mining (2010), 273–282.
13.
WangL., FengL. and WuM., Uds-fim: An efficient algorithm of frequent itemsets mining over uncertain transaction data streams, Journal of Software9(1) (2014), 44–56.
14.
ZhangQ., LiF. and YiK., Finding frequent items in probabilistic data, Proceedings of the ACM SIGMOD International Conference on Management of Data (2008), 819–831.
15.
CormodeG. and GarofalakisM., Sketching probabilistic data streams, Advances in Database Technology-11th International Conference on Extending Database Technology (2008), 145–190.
16.
SunX., LimL. and WangS., An approximation algorithm of mining frequent itemsets from uncertain dataset, International Journal of Advancements in Computing Technology4(3) (2012), 42–49.
17.
WangL., CheungD.W.L., ChengR., LeeS.D. and YangX.S., Efficient mining of frequent item sets on large uncertain databases, IEEE Transactions on Knowledge and Data Engineering24(12) (2012), 2170–2183.
18.
LeungC.K.S., MateoM.A.F. and BrajczukD.A., A tree-based approach for frequent pattern mining from uncertain data, Lecture Notes in Computer Science (2008), 653–661.
19.
LeungC.K.S., CarmichaelC.L. and HaoB., Efficient mining of frequent patterns from uncertain data, Proceedings of IEEE International Conference on Data Mining (2007), 489–494.
20.
LinC.W. and HongT.P., A new mining approach for uncertain databases using CUFP trees, Expert Systems with Applications39(4) (2012), 4084–4093.
21.
YuanY., WangG., ChenL. and NingB., Efficient pattern matching on big uncertain graphs, Information Sciences339(2016), 369–394.
22.
ChenL., PengJ., RaoC. and RosyidaI., Cycle index of uncertain random graph, 34(2018), 4249–4259.
23.
GaoX., GuoC., YinX. and YuX., The computation on α- connectedness index of uncertain graph, Cluster Computing (2017), 123–134.
24.
ZouZ., LiJ., GaoH. and ZhangS., Frequent subgraph pattern mining on uncertain graph data, International Conference on Information and Knowledge Management, Proceedings (2009), 583–592.
25.
ZouZ., LiJ., GaoH. and ZhangS., Mining frequent subgraph patterns from uncertain graph data, IEEE Transactions on Knowledge and Data Engineering22(9) (2010), 1203–1218.
26.
LiJ., ZouZ. and GaoH., Mining frequent subgraphs over uncertain graph databases under probabilistic semantics, VLDB Journal21(6) (2012), 753–777.
27.
PapapetrouO., IoannouE. and SkoutasD., Efficient discovery of frequent subgraph patterns in uncertain graph databases, ACM International Conference Proceeding Series (2011), 355–366.
28.
MoussaouiM., ZaghdoudM. and AkaichiJ., A New Framework of Frequent Uncertain Subgraph Mining, Procedia Computer Science126 (2018), 413–422.
29.
JiangR., TuZ., ChenT. and SunF., Network motif identification in stochastic networks, Proceedings of the National Academy of Sciences of the United States of America103(25) (2006), 9404–9409.
30.
ValiantL.G., The complexity of computing the permanent, Theoretical Computer Science8(2) (1979), 189–201.
31.
GaurD., ShastriA. and BiswasR., Graph-Based Substructure Pattern Mining, International Conference on Advanced Computer Theory and Engineering (2008), 865–869.
