Evaluating Nearest-Neighbor Queries Based on Uncertainty Model

Evaluation of nearest-neighbor queries needs to know locations of all data objects and query object under consideration. But the locations are probably uncertain particularly when they are moving objects. In time between two consecutive location samplings conducted by GPS, moving objects are expected to travel with the deviation kept within a specified threshold from their expected locations. Pfoser et al. proposed an error ellipse model to represent the shape and extent of the uncertainty of locations based on maximum velocity. This paper extends that model by imposing additional constraint of minimum velocity, and proposes to evaluate nearest-neighbor queries using the extended model.