Uncertainty Management in Spatio-temporal Database

Kai Zheng (2012). Uncertainty Management in Spatio-temporal Database PhD Thesis, School of Information Technology and Electrical Engineering, The University of Queensland.

       
Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
s4186377_phd_abstract.pdf abstract application/pdf 48.98KB 0
s4186377_phd_finalthesis.pdf final thesis application/pdf 1.87MB 11
Author Kai Zheng
Thesis Title Uncertainty Management in Spatio-temporal Database
School, Centre or Institute School of Information Technology and Electrical Engineering
Institution The University of Queensland
Publication date 2012-05
Thesis type PhD Thesis
Supervisor Xiaofang Zhou
Total pages 185
Total colour pages 6
Total black and white pages 179
Language eng
Subjects 080604 Database Management
Abstract/Summary Spatio-temporal databases have been generating significant influences on the landmark of database community, due to its powerful capability to map, express and reason about our real world spatially. While ongoing research efforts are made along this direction, traditional spatial queries have been challenged by the rapidly increasing availability of uncertain data in various modern applications including mobile computing, location-based service, RFID systems and so on. The essential difference between uncertain and traditional database requires more complex models and novel algorithms to be designed. In this thesis, we identify a set of challenging problem about uncertainty management in spatio-temporal databases, and provide efficient solution for them under various settings. Below is a brief description of our contributions. We study the popular K nearest neighbor query in the context of fuzzy objects that have indeterministic boundaries. Fuzzy objects play an important role in many areas, such as biomedical image databases and GIS. To improve the query performance, we optimize the basic best-first search algorithm by deriving more accurate approximations for the distance function between fuzzy object and the query object. We also propose effective pruning rules and efficient refinement strategy to further reduce the computation cost. We are the first to study the uncertain-awareness continuous range queries over trajectories in spatial networks. We propose an intuitive model for uncertain trajectories representing the motion along a road network, and provide a unified probability distribution function for the possible locations of a moving object at a given time-instant. An effective indexing structure, UTH, and a series of efficient processing algorithms have been developed, the superior of which is demonstrated by our extensive experiments. We make some efforts on reducing the uncertainty embedded in the trajectories, especially the ones with low-sampling-rates. We develop a systematic solution, called history based route inference system (HRIS), to infer the possible route for a low-sampling-rate trajectory by leveraging the information from historical trajectories. Based on the real-world trajectory dataset generated by 33,000+ taxis of Beijing, our system can advise the original route of a low-sampling-rate trajectory, which is highly close to the ground truth. We also investigate a novel type of query, namely top-k influential sites query (TkIS), in the context of uncertain database. Since it is not so straightforward to precisely define the semantics of ranking query with uncertainty data, we introduce a novel and intuitive formulation based upon the expected rank semantics. To address the efficiency issue caused by exponential possible worlds exploration, we propose effective pruning rules and a divide-and-conquer paradigm such that the number of candidates as well as the number of possible worlds to be considered can be significantly reduced.
Keyword spatio-temporal database
uncertainty
trajectory
algorithm
performance
index
Additional Notes 62, 64, 107, 115, 120, 123

 
Citation counts: Google Scholar Search Google Scholar
Access Statistics: 90 Abstract Views, 10 File Downloads  -  Detailed Statistics
Created: Wed, 06 Jun 2012, 13:21:53 EST by Kai Zheng on behalf of Library - Information Access Service