Efficient Query Processing on Graph Databases

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Efficient Query Processing on Graph Databases"

By

Mr. Sheung-Chak Cheng


Abstract

Graph is a powerful modeling tool for representing and understanding
objects and their relationships. It is used to model concepts in every
area from science to industry and from theory to everyday life. In recent
years, we have observed a rapid increase in the volume of graph data,
especially in the scientific domains and various social networks. However,
the performance of query processing on large graph databases is still
inadequate.

In this thesis, we develop efficient methods for processing queries on
large graph databases. Our work mainly focuses on two types of most
popular graph databases: transaction graph databases that consist of a
large set of small graphs (e.g., chemistry and bio-informatics databases)
and large graphs (e.g., the Web and social networks). We develop a novel
index that supports efficient query processing on large transaction graph
databases. We apply the concept of frequent subgraphs and develop a
clustering technique to build the index, which is shown to be orders of
magnitude more efficient than other existing graph indexes. We also devise
an efficient update strategy for the index. On querying large graphs, we
propose a novel partition-and-conquer paradigm that first partitions a
large graph into a set of small communities and then processes a query by
the integration of intra-community information flow and inter-community
hierarchical relation. This method is particularly useful and practical
since an algorithm of complexity O(n^2) already does not scale on such
large graphs. Our experimental results show that our method obtains the
same high-quality results as the state-of-the-art method, but the speed is
three orders of magnitudes faster and the memory consumption is also
significantly lower.


Date:			Monday, 14 July 2008

Time:			2:00p.m.-4:00p.m.

Venue:			Room 3501
			Lifts 25-26

Chairman:		Prof. Limin ZHANG (CIVL)

Committee Members:	Prof. Wilfred NG (Supervisor)
			Prof. Dik Lun LEE
			Prof. Dimitrios PAPADIAS
			Prof. Bilian Ni SULLIVAN (MGTO)
			Prof. Ada Waichee FU (Comp. Sci. & Engg., CUHK)


**** ALL are Welcome ****