Efficient Query Algorithms for Uncertain Graph Databases


Grant Data
Project Title
Efficient Query Algorithms for Uncertain Graph Databases
Principal Investigator
Dr Cheng, Chun Kong   (Principal investigator)
Co-Investigator(s)
Dr Fan Wei   (Co-Investigator)
Dr Senellart Pierre   (Co-Investigator)
Duration
24
Start Date
2015-11-01
Completion Date
2017-10-31
Amount
462528
Conference Title
Presentation Title
Keywords
uncertain data, uncertain graph database, database queries, query algorithms
Discipline
Database and data science
Panel
Engineering (E)
Sponsor
RGC General Research Fund (GRF)
HKU Project Code
17205115
Grant Type
General Research Fund (GRF)
Funding Year
2015/2016
Status
On-going
Objectives
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.