A method for improving graph queries processing using positional inverted index (P.I.I) idea in search engines and parallelization techniques

Abstract

The idea of positional inverted index is exploited for indexing of graph database. The main idea is the use of hashing tables in order to prune a considerable portion of graph database that cannot contain the answer set. These tables are implemented using column-based techniques and are used to store graphs of database, frequent sub-graphs and the neighborhood of nodes. In order to exact checking of remaining graphs, the vertex invariant is used for isomorphism test which can be parallel implemented. The results of evaluation indicate that proposed method outperforms existing methods.

Keywords

graph query processing / frequent subgraph / graph mining / data mining / positional inverted index

References

[1] ChengJ, KeY, NgW, LuA. FG-index: Towards verification-free query processing on graph databases [C]//. International Conference on Management of Data, 2007857-872

[2] BerendtB, HothoA, StummeG. Semantic web mining [C]//. Conference International Semantic Web (ISWC), 2002264-278

[3] MisraS, BarthwalR, ObaidatM S. Communication detection in an integrated internet of things and social network architecture [C]//. Communication QOS, Reliability and Modeling Syposium, 20122787-2805

[4] WassermanS, IacobucciF. Social network analysis: Methods and applications [M]. Cambridge University Press, 1994

[5] YanL, WangJ. Extracting regular behaviors from social media networks [C]//. Third International Conference on Multimedia Information Networking and Security, 2011

[6] CalvinK. Logic induction of valid behavior specifications for intrusion detection [C]//. IEEE Symposium on Security and Privacy (S&P), 2000142-155

[7] HilmiY, ZakiM J. Graph indexing for reachability queries [C]//. 26th International Conference on Data Engineering Workshops (ICDEW), 2010321-324

[8] XiaogangY, YeT, TaoP, CanfengC, JianM. Semantic-based graph index for mobile photo search [C]//. Second International Workshop on Education Technology and Computer Science, 2010193-197

[9] PengT, WangW, GongX, TianY, YangX. A graph indexing approach for content-based recommendation system [C]//. IEEE Second International Conference on Multimedia and Information Technology (MMIT), 201093-97

[10] YanX-f, YuS P, HanJ. Graph indexing: A frequent structure-based approach [C]//. ACM SIGMOD International Conference on Management of Data (SIGOM), 2004335-346

[11] XuG, ZhangY, LiLWeb mining and social networking [M], 2010MelbournSpringer

[12] IvancsY, RenataI, VajkI. Clustering XML documents using frequent subtrees [J]. Advances in Focused Retrieval, 2009, 3: 436-445

[13] YuanJ, LiX, MaL. An improved XML document clustering using path features [C]//. Fifth International Conference on Fuzzy Systems and Knowledge Discovery, 2008

[14] RajaramaN, UllmanJ DMining of massive datasets [M], 20122nd edCambridgeCambridge University Press

[15] AggarwalC, WangH-xunManaging and mining graph data [M], 2010

[16] HanJ, KamberM. Data mining concepts and techniques [M]. USA, Diane Cerra, 2006

[17] DinariH, NaderiH. A survry of frequent subgraphs snd subtree mining methods [J]. International Journal of Computer Science and Business Informatics (IJSCBI), 2014, 14(1): 39-57

[18] HuanJ, WangW, PrinsJ. Efficient mining of frequent subgraphs in the presence of isomorphism [C]//. Third IEEE International Conference on Data Mining, 2003

[19] KuramochiM, KarypisG. An efficient algorithm for discovering frequent subgraphs [J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 9: 1038-1054

[20] UllmannJ R. An algorithm for subgraph isomorphism [J]. ACM, 197631-42

[21] SakrS, PardedeE. Graph data management: Techniques and applications [C]//. United States of America: Information Science Reference (An Imprint of IGI Global), 2012

[22] RosalbaG, ShashaD. Graphgrep: A fast and universal method for querying graphs [C]//. IEEE Proceedings 16th International Conference on Pattern Recognition, 2002112-115

[23] HeH-h, SinghA K. Closure-tree: An index structure for graph queries [C]//. 22nd International Conference on Data Engineering (ICDE’06), 200638-48

[24] YanX-f, HanJ. CloseGraph: Mining closed frequent graph patterns [C]//. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003286-295

[25] YanX-f, ZhouX, HanJ. Mining closed relational graphs with connectivity constraints [C]//. ACM SIGKDD International Conference on KNOWLEDGE DISCovery in Data Mining (SIG), 2005324-333

[26] YanX-f, HanJ-wei. Gspan: Graph-based substructure pattern mining [C]//. IEEE International Conference on Data Mining (ICDM), 2002721-724

[27] MichihiroK, KarypisG. An efficient algorithm for discovering frequent subgraphs [J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(9): 1038-1054