Managing uncertainty and imprecision in spatio-temporal databases.

摘要

Miniaturization of computing devices, and advances in wireless communication and sensor technology force to propagate computing from the stationary desktop to the mobile scenario in which spatio-temporal information is generated and managed. There exist much ineluctable uncertainty and imprecision in the spatio-temporal information management. Four of them are covered.; The first uncertainty problem is that the raw data is noisy and error prone. In most cases, the motion of a vehicle occurs on a road network, and thus the error can be corrected by matching/snapping it onto the road in the map. We propose a 3D weight-based map matching algorithm for this purpose. This algorithm is applicable to both the offline and online cases, and superior to the straightforward snapping method.; The second uncertainty problem is that, given that the location of a moving object changes continuously, but the central database cannot be updated continuously. To address this problem, distance and deviation update policies are presented which use less updates to enable the same accuracy of the location information in the database. And a method of generating realistic synthetic spatio-temporal points is developed to test these two policies.; The third uncertainty problem arises when we manage the spatio-temporal information in MObile Peer-to-peer NETworks (MOPNET's). Several inherent characteristics of MOPNET's, i.e., dynamic network topology, limited communication throughput, and lack of global knowledge, challenge the uncertainty management. We develop broadcast-based data dissemination algorithms to disseminate the most relevant queries and resource information (namely reports) while maximizing the communication throughput. We demonstrate that our algorithms outperform existing data dissemination methods, periodic flooding and PSTree.; The final uncertainty problem occurs in using resource information to discover local competitive resources, that is, an object has the information of many different resources, which one it should choose to acquire. To address this problem, we rank the resource reports based on the availability of the resource; design a strategy that objects always go to the resource with the largest rank value; and quantify the benefits of using reports to discover resources.