Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/10633
Title: | An analytic solution to the alibi query in the space-time prisms model for moving object data | Authors: | GRIMSON, Rafael KUIJPERS, Bart OTHMAN, Walied |
Issue Date: | 2010 | Publisher: | Taylor & Francis | Source: | INTERNATIONAL JOURNAL OF GEOGRAPHICAL INFORMATION SCIENCE, 25(2), p. 293-322 | 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, space-time prisms (also called beads) (Egenhofer 2003, Miller 2005, Pfoser and Jensen 1999) can be used to model the uncertainty about an 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 chains of space-time prisms (also called necklaces of beads) of these objects intersect. This problem can be reduced to deciding whether two space-time prisms intersect. The alibi query can be seen as a constraint database query. In the constraint database model, spatial and spatio-temporal data are stored by boolean combinations of polynomial equalities and inequalities over the real numbers. The relational calculus augmented with polynomial constraints is the standard first-order query language for constraint databases and the alibi query can be expressed in it. The evaluation of the alibi query in the constraint database model relies on the elimination of a block of three existential quantifiers. Implementations of general purpose elimination algorithms, such as provided by QEPCAD, Redlog and Mathematica, are, for practical purposes, too slow in answering the alibi query for two specific space-time prisms. These software packages fail completely to answer the alibi query in the parametric case (that is, when it is formulated in terms of parameters representing the sample points and speed constraints). The main contribution of this paper is an analytical solution to the parametric alibi query, which can be used to answer the alibi query on two specific space-time prisms in constant time (a matter of milliseconds in our implementation). It solves the alibi query for chains of space-time prisms in time proportional to the sum of the lengths of the chains. To back this claim up we implemented our method in Mathematica alongside the traditional quantifier elimination method. Our solutions we propose are based on geometric argumentation and they illustrate the fact that some practical problems require creative solutions, where at least in theory, existing systems could provide a solution. | Document URI: | http://hdl.handle.net/1942/10633 | ISSN: | 1365-8816 | e-ISSN: | 1362-3087 | ISI #: | 000288492300007 | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2012 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
An analytic solution to the alibi query in the space time prisms model for moving object data.pdf Restricted Access | Published version | 612.61 kB | Adobe PDF | View/Open Request a copy |
WEB OF SCIENCETM
Citations
21
checked on Oct 7, 2024
Page view(s)
56
checked on Sep 7, 2022
Download(s)
76
checked on Sep 7, 2022
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.