Restricted Continuous KNN Queries on Road Networks with Caching Enhancement
Maytham Safar, Dariush Ebrahimi, Mary Magdalene Jane F., R. Nadarajan
Journal of Digital Information Management, Vol. 6, No. 1, 2008.
DOI: 
Link: http://www.dirf.org/jdim/v6n1a5.asp
Abstract:
Using a Global Positioning System (GPS) in the car navigation system enables the driver to perform a wide range of queries, from locating the car position, to finding a route from a source to a destination, or dynamically selecting the best route in real time. With spatial network databases (SNDB), objects are restricted to move on pre-defined paths (e.g., roads) that are specified by an underlying network. In our previous work, we proposed a novel approach, termed Progressive Incremental Network Expansion (PINE), to efficiently support several spatial queries. In this work, we utilize our developed PINE system to efficiently support Restricted Continuous K Nearest Neighbors (RCKNNs) queries. RCKNN continuously finds the K nearest objects to a query point on a given path that are within a specified distance bound. Our solution addresses a new type of query that is plausible to many applications where the answer to the query not only depends on the distances of the nearest neighbors, but also on the user or application needs. By distinguishing between two types of split points, we reduce the number of computations required to retrieve the RCKNNs of a moving object. We further define a caching model to expedite RCKNN query response time.