Range and kNN Query Processing for Moving Objects in Grid Model

With the growing popularity of mobile computing devices and wireless communications, managing dynamically changing information about moving objects is becoming feasible. In this paper, we implement a system that manages such information and propose two query algorithms: a range query algorithm and a k nearest neighbor algorithm. The range query algorithm is combined with an efficient filtering technique which determines if a polyline corresponding to the trajectory of a moving object intersects with a given range. We study the performance of the system, which shows that despite the filtering step, for moderately large ranges, the range query algorithm we propose outperforms the algorithm without filtering.