Approximate Continuous K-Nearest Neighbor Queries for Uncertain Objects in Road Networks

Continuous K nearest neighbor queries (CKNN) on moving objects retrieves among all moving objects the K-Nearest Neighbors (KNNs) of a moving query point within a given time interval. Since the frequent updates of object locations make it complicated to process CKNN, the cost for retrieving the exact CKNN data set is expensive, particularly in highly dynamic spatio-temporal applications. In some applications (e.g. finding my nearest taxies while I am moving within the next 5 minutes), it is not necessary to obtain the accurate result set. For these applications, we introduce a novel technique, Moving state based Approximate CKNN (MACKNN), to approximate the CKNN query results with certain accuracy to make the query process more efficient by using Moving State of Uncertain Object (MSUO) Model and guarantee certain accuracy. We evaluate the MACKNN technique with simulations and compare it with a traditional approach. Experimental results are presented to demonstrate the utility of our new approach.