MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Elbassioni, Khaled M.
Elmasry, Amr
Kamel, Ibrahim		dblp
dblp
dblp
Not MPG Author(s):
Elmasry, Amr
Kamel, Ibrahim
Editor(s):
Not MPII Editor(s):
Diego Calvanese,
Maurizio Lenzerini,
Rajeev Motwani
BibTeX cite key*:
Elbassioni2003dz
Title, Booktitle
Title*:
An Efficient Indexing Scheme for Multi-dimensional Moving Objects
ICDT03.pdf (308.42 KB)
Booktitle*:
Database Theory - ICDT 2003, 9th International Conference
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Siena, Italy
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
8 January 2003
Event End Date:
10 January 2003
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
2572
Number:
Month:
January
Pages:
425-439
Year*:
2003
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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}.(\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.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Elbassioni2003dz,
AUTHOR = {Elbassioni, Khaled M. and Elmasry, Amr and Kamel, Ibrahim},
 TITLE = {An Efficient Indexing Scheme for Multi-dimensional Moving Objects},
 BOOKTITLE = {Database Theory - ICDT 2003, 9th International Conference},
 PUBLISHER = {Springer},
 YEAR = {2003},
 VOLUME = {2572},
 PAGES = {425--439},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Siena, Italy},
 MONTH = {January},
}

Entry last modified by Stephanie Müller, 11/21/2014
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]		Created
02/22/2005 07:55:54 PM
Revisions
4.
3.
2.
1.
0.		Editor(s)
Stephanie Müller
Christine Kiesel
Christine Kiesel
Khaled Elbassioni
Khaled Elbassioni		Edit Dates
21.11.2014 12:49:13
02.05.2007 15:40:42
02.06.2006 15:19:06
04/20/2006 06:38:36 PM
02/22/2005 07:55:54 PM

File Attachment Icon
ICDT03.pdf