Querying Imprecise Data in Moving Object Environments. Appeared in IEEE ICDE 2003 Conference. Reynold Cheng, Sunil Prabhakar, and Dmitri V. Kalashnikov Department of Computer Sciences Purdue University PLACE project (http://www.cs.purdue.edu/place/) Abstract 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 certain 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 such probabilistic, or imprecise, range and nearest-neighbor queries. The imprecision in queries is an inherent property of these applications due to uncertainty in the data, unlike the techniques for approximate nearest-neighbor processing that trade-off 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. Furthermore, we study approximate evaluation of these queries that allow a trade-off between execution time and accuracy. The use of indexes for efficient execution of approximate queries over large collections of moving objects is also presented. Keywords: Moving objects, querying imprecise data, uncertainty, uncertainty region, models of uncertainty, nearest neighbor query, NN query, probabilistic answer, handling uncertainty, location-aware computing Downloadable files: Extended version: ICDE03_dvk.ext.pdf See also our sensor environment solution to a similar problem. BibTeX entry: @inproceedings{ICDE03::dvk, author = {Reynold Cheng and Sunil Prabhakar and Dmitri V. Kalashnikov}, title = {Querying imprecise data in moving object environments}, booktitle = {Proc. of IEEE Int'l Conf. on Data Engineering (IEEE ICDE 2003)}, year = {2003}, month = {March 5--8}, address = {Bangalore, India} } Back to Kalashnikov's homepage