An Efficient and Scalable Approach to CNN Queries in a Road Network

Professor Chin-Wan Chung is from KAIST and is one of the more successful graduates from the EECS Department at the University of Michigan.
A continuous search in a road network retrieves the
objects which satisfy a query condition at any point
on a path. For example, return the three nearest restaurants
from all locations on my route from point s to point e.
In this talk, we deal with NN queries as well as continuous
NN (CNN) queries in the context of moving objects databases.
The performance of existing approaches based on the
network distance such as the shortest path length depends
largely on the density of objects of interest. To overcome
this problem, we incorporate the use of precomputed NN lists
into Dijkstra's algorithm for NN queries. Also, a mathematical
rationale is employed to produce the final results of CNN queries.
Experimental results for real life datasets of various sizes show
that our approach outperforms its competitors by up to 3.5 times
for NN queries and 5 times for CNN queries depending on the
density of objects and the number of NNs required.