CONTINUOUS SUBGRAPH PATTERN SEARCH OVER GRAPH STREAMS

MPhil Thesis Defence


Title: "CONTINUOUS SUBGRAPH PATTERN
SEARCH OVER GRAPH STREAMS"

By

Mr. Changliang Wang


Abstract

Search over graph databases has attracted much attention recently due to 
its usefulness in many fields, such as the analysis of chemical compounds, 
intrusion detection in network traffic data, and pattern matching over 
users' visiting logs. However, most of the existing works focus on search 
over static graph databases while in many real applications graphs are 
changing over time. In this thesis we investigate a new problem on 
continuous subgraph pattern search under the situation where multiple 
target graphs are constantly changing in a stream style, namely the 
subgraph pattern search over graph streams. Obviously the proposed problem 
is a continuous join between query patterns and graph streams where the 
join predicate is the existence of subgraph isomorphism. Due to the 
NP-completeness of subgraph isomorphism checking, to achieve the real-time 
monitoring of the existence of certain subgraph patterns, we would like to 
avoid using subgraph isomorphism verification to find the exact 
query-stream subgraph isomorphic pairs but to offer an approximate answer 
that could report all probable pairs without missing any actual answer 
pairs. Therefore, we propose a light-weight yet effective feature 
structure called Node-Neighbor Tree to filter out false candidate 
query-stream pairs. To reduce the computational cost, we propose a novel 
idea, projecting the feature structures into a numerical vector space and 
conducting dominant relationship checking in the projected space. We 
design two methods to efficiently verify dominant relationships, and thus 
answer the subgraph search over graph streams efficiently.  In addition to 
answering queries over certain graph streams, we propose a novel problem, 
detecting the appearance of subgraph patterns over uncertain graph streams 
with high probability (i.e. larger than the probability threshold 
specified by users). To address this problem, we not only extend the 
proposed solutions for certain graphs streams, but also propose a new 
pruning technique by utilizing the probability threshold.  We substantiate 
our methods with extensive experiments on both certain and uncertain graph 
streams.


Date:			Friday, 19 June 2009

Time:			10:00am-12:00noon

Venue:			Room 3501
 			Lifts 25-26

Committee Members:	Dr. Lei Chen (Supervisor)
 			Dr. Ke Yi (Chairperson)
 			Dr. Raymond Wong


**** ALL are Welcome ****