On Efficiently Monitoring Continuous Aggregate k Nearest Neighbors in Road Networks

Given a set O of data objects, a set Q of query points, a positive integer k, and an aggregate function f (e.g., sum, max, and min), an aggregate k nearest neighbor query finds the k data objects from O that have the smallest aggregate distances with respect to the query points in Q. This query has a large application base such as location-based services, transportation scheduling, traffic monitoring, emergency management, etc. With the rapid development of positioning technologies, many real-life applications appeal to the continuous aggregate k nearest neighbor monitoring in road networks, where both the data objects and query points move along the networks, and the edge weights (e.g., the driving time) fluctuate overtime. In this paper, we study the problem of continuous aggregate k nearest neighbor monitoring (CAkNN monitoring for short) inroad networks. We propose an efficient generic CAkNN monitoring framework, termed as GMF, which is capable of processing three types of update, including data object update, query point update, and edge weight update. We introduce an essential concept, i.e., safe distance, into this framework, which helps to boost the update efficiency for CAkNN monitoring problem. Using an effective structure, termed as partial distance matrix, we identify the safe distance and form the candidate object set for CAkNN monitoring efficiently. Extensive experimental evaluation on real road networks demonstrates that, our proposed CAkNN monitoring framework is superior to the state-of-the-art method.