Abstract:

A graph reachability query, as one of the primary tasks, is to find
whether two given data objects, u and v, are related in any ways in a
large and complex dataset. Formally, the query is about to find if v
is reachable from u in a directed graph which is large in size. In
this talk, we focus ourselves on building a reachability labeling for
a large directed graph, in order to process reachability queries
efficiently. Such a labeling needs to be minimized in size for the
efficiency of answering the queries, and needs to be computed fast for
the efficiency of constructing such a labeling.  As such a labeling,
2-hop cover was proposed for arbitrary graphs with theoretical bounds
on both the construction cost and the size of the resulting labeling.
However, in practice, as reported, the construction cost of 2-hop
cover is very high even with super power machines.  We propose a novel
geometry-based algorithm which computes high-quality 2-hop cover fast.
By utilizing the 2-hop cover, we show that we can support graph
pattern matching over a large data graph efficiently.

At the end of the talk, the speaker will also introduce some other
research activities in the Department of Systems Engineering and
Engineering Management, the Chinese University of Hong Kong.

Short Biography:

Jeffrey Xu Yu received his B.E., M.E. and Ph.D. in computer science,
from the University of Tsukuba, Japan, in 1985, 1987 and 1990,
respectively. Dr. Yu held teaching positions in the Institute of
Information Sciences and Electronics, University of Tsukuba, Japan,
and the Department of Computer Science, The Australian National
University. Currently, he is a Professor in the Department of Systems
Engineering and Engineering Management, the Chinese University of Hong
Kong. Dr. Yu is an ACM SIGMOD Information Director, an associate
editor of IEEE Transactions on Knowledge and Data Engineering, and a
VLDB Journal editorial board member. His current main research
interest includes graph database, XML database, data mining, data
warehouse and OLAP, Web-technology, and query processing and query
optimization. He has published over 140 papers including papers
published in TKDE, VLDBJ, SIGMOD, SIGKDD, VLDB, ICDE, and EDBT.