Publication Type

Journal Article

Version

submittedVersion

Publication Date

12-2010

Abstract

There have been many studies on management of moving objects recently. Most of them try to optimize the performance of predictive window queries. However, not much attention is paid to two other important query types: the predictive range query and the predictive k nearest neighbor query. In this article, we focus on these two types of queries. The novelty of our work mainly lies in the introduction of the Transformed Minkowski Sum, which can be used to determine whether a moving bounding rectangle intersects a moving circular query region. This enables us to use the traditional tree traversal algorithms to perform range and kNN searches. We theoretically show that our algorithms based on the Transformed Minkowski Sum are optimal in terms of the number of tree node accesses. We also experimentally verify the effectiveness of our technique and show that our algorithms outperform alternative approaches.

Keywords

Transformed Minkowski Sum, Spatio-temporal databases, Moving objects, Range query, Nearest neighbor query, kNN

Discipline

Computer Sciences | Theory and Algorithms

Publication

Information Systems

Volume

35

Issue

8

First Page

911

Last Page

932

ISSN

0306-4379

Identifier

10.1016/j.is.2010.05.004

Publisher

Elsevier

Additional URL

http://dx.doi.org/10.1016/j.is.2010.05.004

Download

Share

COinS