Query Processing in Uncertain Graphs

PhD Thesis Proposal Defence


Title: "Query Processing in Uncertain Graphs"

by

Mr. Panagiotis PARCHAS


Abstract:

Data in several applications can be represented as an uncertain graph, whose 
edges are labeled with a probability of existence. Exact query processing on 
uncertain graphs is prohibitive for most applications, as it involves 
evaluation over an exponential number of instantiations. Thus, typical 
approaches employ Monte-Carlo sampling, which i) draws a number of possible 
graphs (samples), ii) evaluates the query on each of them, and iii) aggregates 
the individual answers to generate the final result. However, this approach can 
also be extremely time consuming for large uncertain graphs commonly found in 
practice. To facilitate efficiency, we study the problem of extracting a single 
representative instance from an uncertain graph. Conventional processing 
techniques can then be applied on this representative to closely approximate 
the result on the original graph.

In order to maintain data utility, the representative instance should preserve 
structural characteristics of the uncertain graph. We start with 
representatives that capture the expected vertex degrees, as this is a 
fundamental property of the graph topology. We then generalize the notion of 
vertex degree to the concept of n-clique cardinality, i.e., the number of 
cliques of size n that contain a vertex. For the first problem, we propose two 
methods: Average Degree Rewiring (ADR), which is based on random edge rewiring, 
and Approximate B-matching (ABM), which applies graph matching techniques. For 
the second problem, we develop a greedy approach and a game theoretic 
framework. We experimentally demonstrate, with real uncertain graphs, that 
indeed the representative instances can be used to answer, efficiently and 
accurately, queries based on several metrics such as shortest path distance, 
clustering coefficient and betweenness centrality.


Date:			Wednesday, 27 January 2016

Time:                  	2:00pm - 4:00pm

Venue:                  Room 3584
                         Lifts 27/28

Committee Members:	Prof. Dimitris Papadias (Supervisor)
 			Prof. Dik-Lun Lee (Chairperson)
 			Dr. Pedro Sander
 			Dr. Raymond Wong


**** ALL are Welcome ****