An efficient and scalable approach to CNN queries in a road network

Abstract

A continuous search in a road network re-trieves the objects which satisfy a query con-dition 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 paper, we deal with NN queries as well as continuous NN queries in the context of moving objects databases. The performance of existing approaches based on the network distance such as the shortest path length de-pends largely on the density of objects of in-terest. To overcome this problem, we propose UNICONS (a unique continuous search algo-rithm) for NN queries and CNN queries per-formed on a network. We incorporate the use of precomputed NN lists into Dijkstra’s algo-rithm for NN queries. A mathematical ratio-nale is employed to produce the final results of CNN queries. Experimental results for real-life datasets of various sizes show that UNI-CONS 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. 1