Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




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

URL of the conference:


URL for downloading the paper:


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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
ICDT03.pdf