Efficient Query Algorithms for Uncertain Graph Databases

Professor Cheng, Chun Kong Reynold   (Principal Investigator (PI))

Dr Fan Wei   (Co-Investigator)

Dr Senellart Pierre   (Co-Investigator)

30

2015-11-01

462528

Efficient Query Algorithms for Uncertain Graph Databases

database queries, query algorithms, uncertain data, uncertain graph database

Database and data science

Engineering (E)

17205115

General Research Fund (GRF)

2015

Completed

1) [To develop query solutions for uncertain graphs.] We will invent novel techniques enabling the execution of two common classes of queries on uncertain graphs. Specifically, the ""Q-index"", a data structure derived from a given uncertain graph G and query q, produces a ""query-dependent i-graph"" G(q), such that the answer to q when executed on G(q) is the same as the result of running q on G. We will examine how the Q-index enables efficient and effective query evaluation. We will also explore approximate solutions for building the Q-index, as well as graph queries that return path information; 2) [To study the graph event model.] We will investigate the handling of events that occur on one or more edges of an uncertain graph. For example, consider a train route that connects several nodes of an uncertain graph and has stopped because of a strike. The occurrence of this strike affects the travel times on one or more roads. More generally, the probability distributions among the edges are inter-related or correlated. We propose a graph event model to capture this information. Because this makes uncertain graphs more difficult to query, we will investigate efficient and effective solutions. We will also explore situations in which events are given at query time, and we will develop methods that can handle update, insertion, and removal of events efficiently.