Please use this identifier to cite or link to this item:
Title: An analytic solution to the alibi query in the bead model for moving object data
Authors: KUIJPERS, Bart 
OTHMAN, Walied 
Issue Date: 2007
Publisher: Dagstuhl
Source: BANK, Bernd & EGENHOFER, Max & KUIJPERS, Bart (Ed.) Constraint Databases, Geometric Elimination and Geographic Information Systems.
Series/Report: Dagstuhl Seminar Proceedings
Series/Report no.: 07212
Abstract: Moving ob jects 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 [1, 6, 9] can be used to model the uncertainty about the ob ject’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 ob jects 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.
Document URI:
Link to publication:
Category: C1
Type: Proceedings Paper
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
07212.OthmanWalied.Paper.1286.pdfPublished version366.3 kBAdobe PDFView/Open
Show full item record

Page view(s)

checked on May 18, 2022


checked on May 18, 2022

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.