Indexing moving objects: A real time approach

George Lagogiannis1, Nikos Lorentzos1 and Alexander B. Sideridis1

  1. Agricultural University of Athens
    Iera Odos 75, 11855 Athens, Greece
    {lagogian, lorentzos, as}@aua.gr
  2. CIAPACA,
    25 Rue de la Petite Duranne, 13857, Aix en Provence, France
    Izza.said@laposte.net
  3. University of Sciences and Technologie Houari Boumediene, Computer science department
    LSI, Bab-Ezzouar, Algeirs, Algeria.
    anacer@mail.cerist.dz

Abstract

Indexing moving objects usually involves a great amount of updates, caused by objects reporting their current position. In order to keep the present and past positions of the objects in secondary memory, each update introduces an I/O and this process is sometimes creating a bottleneck. In this paper we deal with the problem of minimizing the number of I/Os in such a way that queries concerning the present and past positions of the objects can be answered efficiently. In particular we propose two new approaches that achieve an asymptotically optimal number of I/Os for performing the necessary updates. The approaches are based on the assumption that the primary memory suffices for storing the current positions of the objects.

Key words

Persistence, I/O complexity, Indexing structures

Digital Object Identifier (DOI)

https://doi.org/10.2298/CSIS111127040L

Publication information

Volume 10, Issue 1 (Januar 2013)
Year of Publication: 2013
ISSN: 1820-0214 (Print) 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

DownloadAvailable in PDF
Portable Document Format

How to cite

Lagogiannis, G., Lorentzos, N., Sideridis, A. B.: Indexing moving objects: A real time approach. Computer Science and Information Systems, Vol. 10, No. 1, 173-195. (2013)