An indexing method for answering queries on moving objects

Document Type

Article

Source of Publication

Distributed and Parallel Databases

Publication Date

3-1-2005

Abstract

We consider the problem of indexing a set of objects moving in d-dimensional spaces along linear trajectories. A simple external-memory indexing scheme is proposed to efficiently answer general range queries. The following are examples of the queries that can be answered by the proposed method: report all moving objects that will (i) pass between two given points within a specified time interval; (ii) become within a given distance from some or all of a given set of other moving objects. Our scheme is based on mapping the objects to a dual space, where queries about moving objects are transformed into polyhedral queries concerning their speeds and initial locations. We then present a simple method for answering such polyhedral queries, based on partitioning the space into disjoint regions and using a B+-tree to index the points in each region. By appropriately selecting the boundaries of each region, we guarantee an average search time that matches a known lower bound for the problem. Specifically, for a fixed d, if the coordinates of a given set of N points are statistically independent, the proposed technique answers polyhedral queries, on the average, in O((N/B)1-1/d ·(log B N)1/d +K/B) I/O's using O(N/B) space, where B is the block size, and K is the number of reported points. Our approach is novel in that, while it provides a theoretical upper bound on the average query time, it avoids the use of complicated data structures, making it an effective candidate for practical applications. The proposed index is also dynamic in the sense that it allows object insertion and deletion in an amortized update cost of log B (N) I/O's. Experimental results are presented to show the superiority of the proposed index over other methods based on R-trees. © 2005 Springer Science + Business Media, Inc.

ISSN

0926-8782

Publisher

Springer Science and Business Media LLC

Volume

17

Issue

3

First Page

215

Last Page

249

Disciplines

Computer Sciences

Keywords

B+-trees, Indexing, Mobile database management, Mobile objects, Query processing

Scopus ID

18144393103

Indexed in Scopus

yes

Open Access

no

Link to Full Text

Share

COinS