An efficient indexing scheme for multi-dimensional moving objects

Document Type

Article

Source of Publication

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Publication Date

1-1-2003

Abstract

We consider the problem of indexing a set of objects moving in d-dimensional space along linear trajectories. A simple disk-based indexing scheme is proposed to efficiently answer queries of the form: report all objects that will pass between two given points within a specified time interval. Our scheme is based on mapping the objects to a dual space, where queries about moving objects translate 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 can guarantee an average search time that almost 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.(logB 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. © Springer-Verlag Berlin Heidelberg 2003.

ISBN

3540003231

ISSN

0302-9743

Publisher

Springer Verlag

Volume

2572

First Page

425

Last Page

439

Disciplines

Computer Sciences

Keywords

Indexing (of information), Average Search Time, D-dimensional spaces, Disjoint regions, Indexing scheme, Linear trajectory, Moving objects, Multi dimensional, Time interval, Query processing

Scopus ID

35248869611

Indexed in Scopus

yes

Open Access

yes

Open Access Type

Green: A manuscript of this publication is openly available in a repository

Link to Full Text

Share

COinS