Answering Queries on Massive Graphs with Index

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


PhD Thesis Defence


Title: "Answering Queries on Massive Graphs with Index"

By

Mr. Minhao JIANG


Abstract

Graph structure is interesting. Since the birth of computer science, 
researchers and engineers have been modeling numerous fundamental and useful 
applications on graphs. In recent years when we are stepping into the big data 
era, graphs are massive, attached with various useful information, and evolute 
very rapidly. It is extremely challenging to process efficient and effective 
queries on modern networks. Indexing is a practical approach in database. We 
focus on indexing path-related queries in massive graphs in this study, to 
support efficient and effective query processing solutions.

Specifically, we start with the problem of point-to-point distance querying for 
massive scale-free graphs. It is a fundamental graph operator, serving as a 
basic building block for many applications, including social network analysis, 
knowledge graph mining and product recommendation. Given a directed or 
undirected graph, we propose to build an index for answering these queries 
based on a novel hop-doubling labeling technique. We show that our method is 
much more efficient and effective compared to the state-of-the-art techniques, 
in terms of both querying time and indexing costs.

Then, we incorporate the hop-doubling labeling technique with a novel keyword 
indexing scheme to solve the top-k nearest keyword search problem in large 
graphs. The previous algorithms only give approximate results. We show that 
with the efficient graph indexing scheme, it is possible to query exact results 
very efficiently.

In the end, we study indexing a randomized query in massive graphs. 
Specifically, we improve SimRank querying with a randomized indexing scheme to 
support efficient, accurate and dynamic querying.


Date:			Thursday, 27 July 2017

Time:			10:00am - 12:00noon

Venue:			Room 2612B
 			Lifts 31/32

Chairman:		Prof. Ka-Ming Ng (CBME)

Committee Members:	Prof. Raymond Wong (Supervisor)
 			Prof. Lei Chen
 			Prof. Qiong Luo
 			Prof. Xueqing Zhang (CIVL)
 			Prof. Xiaokui Xiao (Comp. Sci. & Engg., NTU)


**** ALL are Welcome ****