Restricted continuous KNN queries on road networks with caching enhancement

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 continously finds the K nearest objects to a query point an 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 an the distances of the nearest neighbors, but also on the user ar application needs. By distinguishing between two types of split points, we reduce the number of computations required to retreive the RCKNNs of moving object. We futher define a caching model to expedite RCKNN query response time.