License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.07212.4
URN: urn:nbn:de:0030-drops-12864
URL: https://drops.dagstuhl.de/opus/volltexte/2007/1286/
Go to the corresponding Portal

Kuijpers, Bart ; Othman, Walied

An analytic solution to the alibi query in the bead model for moving object data

pdf-format:
07212.OthmanWalied.Paper.1286.pdf (0.4 MB)

Abstract

Moving objects produce trajectories, which are stored in databases by means of finite samples of time-stamped locations. When
also speed limitations in these sample points are known,
beads can be used to model the
uncertainty about the object's location in between sample points.

In this setting, a query of particular interest, that has been
studied in the literature of geographic information systems (GIS),
is the alibi query. This boolean query asks whether two
moving objects can have physically met. This adds up to deciding
whether the necklaces of beads of these objects intersect. This
problem can be reduced to deciding whether two beads intersect.
Since, existing software to solve this problem fails to answer this
question within a reasonable time, we propose an analytical solution
to the alibi query, which can be used to answer the alibi query in
constant time, a matter of milliseconds or less, for two single
beads and in time proportional to the product of their lengths for
necklaces of beads.


BibTeX - Entry

@InProceedings{kuijpers_et_al:DagSemProc.07212.4,
  author =	{Kuijpers, Bart and Othman, Walied},
  title =	{{An analytic solution to the alibi query in the bead model for moving object data}},
  booktitle =	{Constraint Databases, Geometric Elimination and Geographic Information Systems},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7212},
  editor =	{Bernd Bank and Max J. Egenhofer and Bart Kuijpers},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/1286},
  URN =		{urn:nbn:de:0030-drops-12864},
  doi =		{10.4230/DagSemProc.07212.4},
  annote =	{Keywords: Beads, uncertainty, alibi, query, solution, quantifier elimination, constraint database}
}

Keywords: Beads, uncertainty, alibi, query, solution, quantifier elimination, constraint database
Collection: 07212 - Constraint Databases, Geometric Elimination and Geographic Information Systems
Issue Date: 2007
Date of publication: 17.12.2007

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI