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 kk, and an aggregate function ff (e.g., sum, max, and min), an aggregate kk nearest neighbor query finds the kk 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 kk 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 over time. In this paper, we study the problem of continuous aggregate kk nearest neighbor monitoring (CAkkNN monitoring for short) in road networks. We propose an efficient generic CAkkNN 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 bOst the update efficiency for CAkkNN monitoring problem. Using an effective structure, termed as partial distance matrix, we identify the safe distance and form the candidate object set for CAkkNN monitoring efficiently. Extensive experimental evaluation on real road networks demonstrates that, our proposed CAkkNN monitoring framework is superior to the state-of-the-art method.