TY - GEN
T1 - An efficient and scalable approach to CNN queries in a road network
AU - Cho, Hyung Ju
AU - Chung, Chin Wan
PY - 2005
Y1 - 2005
N2 - 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 5 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 depends largely on the density of objects of interest. To overcome this problem, we propose UNICONS (a unique continuous search algorithm) for NN queries and CNN queries performed on a network. We incorporate the use of precomputed NN lists into Dijkstra's algorithm for NN queries. A mathematical rationale 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.
AB - 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 5 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 depends largely on the density of objects of interest. To overcome this problem, we propose UNICONS (a unique continuous search algorithm) for NN queries and CNN queries performed on a network. We incorporate the use of precomputed NN lists into Dijkstra's algorithm for NN queries. A mathematical rationale 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.
UR - http://www.scopus.com/inward/record.url?scp=33745630711&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:33745630711
SN - 1595931546
SN - 9781595931542
T3 - VLDB 2005 - Proceedings of 31st International Conference on Very Large Data Bases
SP - 865
EP - 876
BT - VLDB 2005 - Proceedings of 31st International Conference on Very Large Data Bases
T2 - VLDB 2005 - 31st International Conference on Very Large Data Bases
Y2 - 30 August 2005 through 2 September 2005
ER -