Affiliations: Department of Information & Computer
Engineering, Ajou University Woncheon-dong, Suwon Si Yeongtong-gu, Gyeonggi-Do, South Korea
Note: [] Corresponding author: Hyung-Ju Cho, Department of Information
& Computer Engineering, Ajou University Woncheon-dong, Suwon Si
Yeongtong-gu, Gyeonggi-Do, 443-749, South Korea. Tel.: +82 31 219 2535; Fax:
+82 31 219 1834; E-mail: [email protected]
Abstract: Query processing in road networks has been studied extensively in
recent years. However, the processing of moving queries in road networks has
received little attention. In this paper, we introduce a new algorithm called
the Safe Exit Algorithm (SEA), which can efficiently compute the safe exit
points of a moving nearest neighbor (NN) query on road networks. The safe
region of a query is an area where the query result remains unchanged, provided
that the query remains inside the safe region At each safe exit point, the safe
region of a query and its non-safe region meet so that a set of safe exit
points represents the border of the safe region. Before reaching a safe exit
point, the client (query object) does not have to request the server to
re-evaluate the query This significantly reduces the server processing costs
and the communication costs between the server and moving clients. Extensive
experimental results show that SEA outperforms a conventional algorithm by up
to two orders of magnitude in terms of communication costs and computation costs
