Publication Type

Journal Article

Version

acceptedVersion

Publication Date

6-2007

Abstract

Recent research has focused on continuous monitoring of nearest neighbors (NN) in highly dynamic scenarios, where the queries and the data objects move frequently and arbitrarily. All existing methods, however, assume the Euclidean distance metric. In this paper we study k-NN monitoring in road networks, where the distance between a query and a data object is determined by the length of the shortest path connecting them. We propose two methods that can handle arbitrary object and query moving patterns, as well as fluctuations of edge weights. The first one maintains the query results by processing only updates that may invalidate the current NN sets. The second method follows the shared execution paradigm to reduce the processing time. In particular, it groups together the queries that fall in the path between two consecutive intersections in the network, and produces their results by monitoring the NN sets of these intersections. We experimentally verify the applicability of the proposed techniques to continuous monitoring of large data and query sets.

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Publication

IEEE Transactions on Knowledge and Data Engineering

Volume

19

Issue

6

First Page

789

Last Page

803

ISSN

1041-4347

Identifier

10.1109/TKDE.2007.190617

Publisher

IEEE

Additional URL

http://dx.doi.org/10.1109/TKDE.2007.190617

Download

Share

COinS