GDL

Journal from gdlhub / 2020-04-08 09:47:01
By : Shaik Fathimabi, R.B.V. Subramanyam, D.V.L.N. Somayajulu, King Saud University
Created : 2019-01-08, with 1 files

Keyword : Graph database, Big data, Structure based graph partitioning, Parallel processing, Map-Reduce, Integrated Graph Index
Url : http://www.sciencedirect.com/science/article/pii/S1319157816301161
Document Source : WEB

In a distributed environment, the volume of graph database increases quickly because graphs emerge from several autonomous sources. Sub-graph query processing is a challenging problem in distributed environment. Centralized approaches proposed many algorithms, they mine frequent subgraphs from the graph database and construct an index which is very expensive. These algorithms require more number of database scans to mine frequent subgraphs and they use filter and verify approach, which requires many subgraph isomorphism tests. In this paper, we design a novel Map-Reduce based multiple subgraph query processing framework, namely MSP. MSP processes multiple graph queries using distributed index. The framework completely relies on the graph partition and indexing. Moreover, in order to improve its performance, we propose several solutions to balance the workload and reduce the size of Integrated Graph Index. We propose a structure-based partitioning technique and distributed way of building Integrated Graph Index. This work uses two Map-Reduce rounds, the first Map-Reduce round partitions the graphs and creating index for each partition, second Map-Reduce round processes sub-graph queries and index maintenance. A good partitioning will reduce the index size by distributing the load equally to the machines in the cluster and improves the performance of query evaluation. This graph partition and Integrated Graph Index reduces the search space of query graphs. Our approach allows to add data graphs incrementally to Integrated Graph Index while doing query processing. We experimentally show that our approach decreases remarkably the execution time and scales the subgraph query processing to large graph databases.

Give Comment ?#(0) | Bookmark

Property	Value
Publisher ID	gdlhub
Organization	King Saud University
Contact Name	Herti Yani, S.Kom
Address	Jln. Jenderal Sudirman
City	Jambi
Region	Jambi
Country	Indonesia
Phone	0741-35095
Fax	0741-35093
Administrator E-mail	elibrarystikom@gmail.com
CKO E-mail	elibrarystikom@gmail.com