Querying Imprecise Data in Moving Object Environments.

Appeared in IEEE TKDE, vol. 16(9), 2004.

Reynold Cheng, Dmitri V. Kalashnikov, and Sunil Prabhakar

Department of Computer Sciences
Purdue University
PLACE project (http://www.cs.purdue.edu/place/)


In moving object environments it is infeasible for the database tracking the movement of objects to store the exact locations of objects at all times. Typically the location of an object is known with certainty only at the time of the update. The uncertainty in its location increases until the next update. In this environment, it is possible for queries to produce incorrect results based upon old data. However, if the degree of uncertainty is controlled, then the error of the answers to queries can be reduced. More generally, query answers can be augmented with probabilistic estimates of the validity of the answer. In this paper we study the execution of probabilistic range and nearest-neighbor queries. The imprecision in answers to queries is an inherent property of these applications due to uncertainty in data, unlike the techniques for approximate nearest-neighbor processing that trade accuracy for performance. Algorithms for computing these queries are presented for a generic object movement model, and detailed solutions are discussed for two common models of uncertainty in moving object databases. We also study approximate evaluation of these queries to reduce their computation time.


Data Uncertainty, Probabilistic Queries, Range and Nearest-Neighbor queries.

Downloadable files:

Paper : TKDE04_dvk.pdf
See also our sensor environment solution to a similar problem.

BibTeX entry:

   author    = {Reynold Cheng and Dmitri V. Kalashnikov and Sunil Prabhakar},
   title     = {Querying Imprecise Data in Moving Object Environments},
   journal   = {IEEE Transactions on Knowledge and Data Engineering (IEEE TKDE)},
   volume    = 16,
   number    = 9,
   month     = sep, year = 2004

Back to Kalashnikov's homepage