Affiliations: Department of Computer Engineering, Ajou University,
Gyeonggi-Do, South Korea
Note: [] Corresponding author: Department of 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: hjcho@ajou.ac.kr
Abstract: Given two positive parameters k and
r, a constrained k-nearest neighbor (CkNN) query returns the
k closest objects within a network distance r of the query
location in road networks. In terms of the scalability of monitoring these CkNN
queries, existing solutions based on central processing at a server suffer from
a sudden and sharp rise in server load as well as messaging cost as the number
of queries increases. In this paper, we propose a distributed and scalable
scheme called DAEMON for the continuous monitoring of CkNN queries in road
networks. Our query processing is distributed among clients (query objects) and
server. Specifically, the server evaluates CkNN queries issued at intersections
of road segments, retrieves the objects on the road segments between
neighboring intersections, and sends responses to the query objects. Finally,
each client makes its own query result using this server response. As a result,
our distributed scheme achieves close-to-optimal communication costs and scales
well to large numbers of monitoring queries. Exhaustive experimental results
demonstrate that our scheme substantially outperforms its competitor in terms
of query processing time and messaging cost.
