International Journal of Modern Education and Computer Science (IJMECS)
IJMECS Vol. 9, No. 2, 8 Feb. 2017
Cover page and Table of Contents: PDF (size: 810KB)
A New Method for Graph Queries Processing without Index Reconstruction on Dynamic Graph Databases
Full Text (PDF, 810KB), PP.47-54
Views: 0 Downloads: 0
Author(s)
Hamed Dinari
1,*
Index Terms
Graph query processing, Graph mining, Data mining, Dynamic graph database
Abstract
Graphs play notable role in daily life. For instance, they are used in variety fields such as social networks, malware detection, and biological networks. Graph data processing performed to extract useful information is known as graph mining. A critical field of graph mining is graph containment problem, in which all graphs containing the query are returned by a graph query q. Scanning the whole database (graph query as a subgraph) for a query is a time consuming process. To improve query performance, an inverted index is constructed on the graph database and then the query is performed based on the query. The problem in this process is that when a graph is added to or removed from a database, the inverted index must be reconstructed. The present study proposes a method in which index updating is not needed upon a change in the database. This feature enables simultaneous inverted index updating and querying. The assessment results showed optimum and satisfactory performance of the proposed method.
Cite This Paper
Hamed Dinari, "A New Method for Graph Queries Processing without Index Reconstruction on Dynamic Graph Databases", International Journal of Modern Education and Computer Science(IJMECS), Vol.9, No.2, pp.47-54, 2017. DOI:10.5815/ijmecs.2017.02.06
Reference
[1]Wasserman, S., Faust, K., and Iacobucci. "Social network analysis: Methods and applications". Cambridge university Press, 1994.
[2]S.Misra, R.Barthwal, M.S.Obaidat. "Communication Detection in an Integrated Internet of Things and Social Network Architecture" Communication QOS, Reliability and Modeling Syposium, no. IEEE, pp. 2787-2805. 2012.
[3]L.YAN, J.WANG. "Extracting regular behaviors from social media networks," in Third International Conference on Multimedia Information Networking and Security, 2011.
[4]Cheng, James, Y.Ke, W.Ng, and An Lu. "FG-Index: Towards Verification-Free Query Processing on Graph Databases," in international conference on Management of data, Beijing, pp. 857-872, 2007.
[5]Ivancsy,I. Renata, I.Vajk. "Clustering XML documents using frequent subtrees," Advances in Focused Retrieval, vol. 3, pp. 436-445, 2009.
[6]J.Yuan, X.Li, L.Ma. "An Improved XML Document Clustering Using Path Features" in Fifth International Conference on Fuzzy Systems and knowledge Discovery,vol 2, 2008.
[7]Rajaraman, J.D.Ullman. "Mining of Massive Datasets", 2nd editon, 2012.
[8]C.C.Aggarwal,Wang, Haixun. "Managing and Mining Graph Data". Springer, 2010
[9]J.Han, M.Kamber. "Data Mining Concepts and Techniques" USA: Diane Cerra, 2006.
[10]H.dinari, H.naderi. "A survry of frequent subgraphs snd subtree mining methods", International Journal of Computer Science and Business Informatics(IJSCBI), vol. 14(1), 39-57, 2014.
[11]S.Sakr, E.Pardede. "Graph Data Management: Techniques and Applications". United States of America: Information Science Reference (an imprint of IGI Global), 2012.
[12]Peng, Tao, et al "A Graph Indexing Approach for Content-Based Recommendation System" in IEEE Second International Conference on Multimedia and Information Technology (MMIT),pp. 93-97, 2010.
[13]Yildirim, Hilmi, and M.J.Zaki. "Graph indexing for reachability queries", in 26th International Conference on Data Engineering Workshops (ICDEW), pp. 321-324, 2010.
[14]Swati C. Manekar, M.Narnaware. "Indexing Frequent Subgraphs in Large graph Database using Parallelization" International Journal of Science and Research (IJSR),2(no 5), pp. 426-430, 2013.
[15]Ranu, Sayan, and Ambuj K. Singh. "Indexing and mining topological patterns for drug discovery" in Proceedings of the 15th International Conference on Extending Database Technology, pp. 562-565, 2012.
[16]Kramer, S, De Raedt, L, and Helma, C, "Molecular feature mining in HIV data", in In Proc. of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-01),pp.136–143, 2001.
[17]Giugno, Rosalba, and D.Shasha. 2002. "Graphgrep: A fast and universal method for querying graphs," in IEEE Proceedings 16th International Conference on Pattern Recognition, vol. 2, pp. 112-115, 2002.
[18]Yan, Xifeng, and Jiawei Han. "gspan: Graph-based substructure pattern mining" in IEEE International Conference on Data Mining (ICDM), pp. pp. 721-724, 2002.
[19]He, Huahai, Ambuj K. Singh. "Closure-tree: An index structure for graph queries," in 22nd International Conference on Data Engineering (ICDE), pp. 38-48, 2006.
[20]Yan, Xifeng, S.Philip Yu, and J.Han. "Graph indexing: a frequent structure-based approach" in ACM SIGMOD international conference on Management of data(SIGOM), pp. 335-346, 2004.
[21]Yan, Xifeng, X. Zhou, and J.Han."Mining closed relational graphs with connectivity constraints", in ACM SIGKDD international conference on Knowledge discovery in data mining (SIG), pp. 324-333, 2005.
[22]M.Kuramochi, and G.Karypis, and et al. "An efficient algorithm for discovering frequent subgraphs" IEEE Transactions on Knowledge and Data Engineering, vol. 9, pp. 1038-1054, 2004.
[23]Christodorescu, M., Jha, S., Seshia, S. A., Song, & Bryant. "Semantics-aware malware detection" IEEE Symposium on Security and Privacy, pp. 32-46, 2005
[24]Elhadi, Ammar AE, Mohd A. Maarof, and Ahmed H. Osman."Malware detection based on hybrid signature behaviour application programming interface call graph" American Journal of Applied Sciences, Vol. 9(no.3), 2012.
[25]Hu, Xin, Tzi-cker Chiueh, and Kang G. Shin. "Large-scale malware indexing using function-call graphs" in 16th ACM conference on Computer and communications security. pp. 611-620, 2009.
[26]G.XU, Y.zhang, L.li. "Web mining and Social Networking". melbourn: Springer, 2010.
[27]Ko, Calvin. "Logic induction of valid behavior specifications for intrusion detection", in In IEEE Symposium on Security and Privacy (S&P), pp. 142–155, 2000.
[28]Berendt, Hotho, and Stumme. "semantic web mining," in Conference International Semantic Web (ISWC), pp. 264–278, 2002.