PPDQ-BG: Parallel Partition and Distributed Query Processing for Big Graphs

In recent years, there has been an explosive growth of the linked data of a global information space that often requires expensive computations to perform big graph analysis and query processing. Graph data represent irregular and unstructured relationships that usually result in a lack of locality so that it is often difficult to extract relevant information from big graphs. Although there have been advances in graph processing in centralized, as well as distributed environments, there was a lack of an efficient method of handling large scale graphs for the task of finding relevant relations from big graphs or partitioning a big graph into several meaningful inter-connected graph partitions. In this thesis, we propose a scalable framework, “Parallel Partition and Distributed Query Processing for Big Graphs” (PPDQ-BG) that aims to achieve a parallel partition of large scale RDF graph and distributed query processing on the partitioned data. In this thesis, we propose a PPDQ-BG framework to make the previous centralized approach, “A Big Graph Analytics Framework for Knowledge Discovery”, a distributed model by proposing new partitioning algorithms. The proposed framework also has parallel computation of relevant information by determining neighborhood relationships among predicates of large RDF graphs in a parallel manner by computing the similarity of predicates in large scale graphs. It has the design of parallel algorithms for partitioning of graphs in a distributed dataflow framework by proposing new clustering algorithms, Similarity based Fuzzy C-Means Partitioning and Hierarchical Predicate Based Clustering. The framework also has implementation of an interactive tool using Neo4j graph databases for executing a distributed query process from partitioned graphs, experimental evaluations including correlation coefficient matrix evaluations to validate the proposed framework and comparison of proposed partitioning methods with existing partitioning algorithms using multiple datasets including medical ontology datasets, DBPedia, YAGO, and Bio2RDF datasets, experimental results of distributed query processing for efficient data retrieval for various complex queries against large scale datasets including DBPedia, YAGO, and Bio2RDF datasets.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Computer Science (UMKC)

Grantor dc:publisher

University of Missouri--Kansas City

Year dc:date.issued

2016

Author dc:creator

• Kandula, Lema

Advisor dc:contributor.advisor

• Lee, Yugyung, 1960-

Language dc:language.iso

en_US

Handle dc:identifier.uri

https://hdl.handle.net/10355/60055

OAI identifier oai:identifier

oai:mospace.umsystem.edu:10355/60055