4 Search Results for "Othman, Walied"

Document
Short Paper
DOI: 10.4230/LIPIcs.TIME.2025.16
Solutions to the Generalised Alibi Query in Moving Object Databases (Short Paper)

Authors: Arthur Jansen and Bart Kuijpers

Published in: LIPIcs, Volume 355, 32nd International Symposium on Temporal Representation and Reasoning (TIME 2025)

Abstract
Space-time prisms provide a framework to model the uncertainty on the space-time points that a moving object may have visited between measured space-time locations, provided that a bound on the speed of the moving object is given. In this model, the alibi query asks whether two moving objects, given by their respective measured space-time locations and speed bound, may have met. An analytical solution to this problem was first given by Othman [Kuijpers et al., 2011]. In this paper, we address the generalised alibi query that asks the same question for an arbitrary number 𝗇 ≥ 2 of moving objects. We provide several solutions (mainly via the spatial and temporal projection) to this query with varying time complexities. These algorithmic solutions rely on techniques from convex and semi-algebraic geometry. We also address variants of the generalised alibi query where the question is asked for a given spatial location or a given moment in time.
Cite as

Arthur Jansen and Bart Kuijpers. Solutions to the Generalised Alibi Query in Moving Object Databases (Short Paper). In 32nd International Symposium on Temporal Representation and Reasoning (TIME 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 355, pp. 16:1-16:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.TIME.2025.16,
  author =	{Jansen, Arthur and Kuijpers, Bart},
  title =	{{Solutions to the Generalised Alibi Query in Moving Object Databases}},
  booktitle =	{32nd International Symposium on Temporal Representation and Reasoning (TIME 2025)},
  pages =	{16:1--16:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-401-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{355},
  editor =	{Vidal, Thierry and Wa{\l}\k{e}ga, Przemys{\l}aw Andrzej},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2025.16},
  URN =		{urn:nbn:de:0030-drops-244622},
  doi =		{10.4230/LIPIcs.TIME.2025.16},
  annote =	{Keywords: Convex geometry, Semi-algebraic geometry, Space-time prism, Geographic information systems, Quantifier elimination}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.TIME.2025.17
Visit Probability in Space-Time Prisms for Moving Object Data (Short Paper)

Authors: Arthur Jansen and Bart Kuijpers

Published in: LIPIcs, Volume 355, 32nd International Symposium on Temporal Representation and Reasoning (TIME 2025)

Abstract
Space-time prisms have been extensively studied as a model to describe the uncertainty of the spatio-temporal location of a moving object in between measured space-time locations. In many applications, the desire has been expressed to provide an internal structure to these prisms, that includes what has been called "visit probability". Although several proposals have been studied in the past decades, a precise definition of this concept has been missing. The contribution of this paper is to provide such a specification by means of a formal framework for visit probability. Once this concept is established, we are able to derive on which parts of a prism, visit probability can be seen to give rise to a probability space.
Cite as

Arthur Jansen and Bart Kuijpers. Visit Probability in Space-Time Prisms for Moving Object Data (Short Paper). In 32nd International Symposium on Temporal Representation and Reasoning (TIME 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 355, pp. 17:1-17:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.TIME.2025.17,
  author =	{Jansen, Arthur and Kuijpers, Bart},
  title =	{{Visit Probability in Space-Time Prisms for Moving Object Data}},
  booktitle =	{32nd International Symposium on Temporal Representation and Reasoning (TIME 2025)},
  pages =	{17:1--17:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-401-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{355},
  editor =	{Vidal, Thierry and Wa{\l}\k{e}ga, Przemys{\l}aw Andrzej},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2025.17},
  URN =		{urn:nbn:de:0030-drops-244633},
  doi =		{10.4230/LIPIcs.TIME.2025.17},
  annote =	{Keywords: Spatio-temporal databases, moving object databases, space-time prisms, probability spaces}
}
Document
DOI: 10.4230/DagSemProc.08471.2
Propagating and measuring anchor uncertainty in space-time prisms on road networks

Authors: Bart Kuijpers, Harvey J. Miller, Tijs Neutens, and Walied Othman

Published in: Dagstuhl Seminar Proceedings, Volume 8471, Geographic Privacy-Aware Knowledge Discovery and Delivery (2009)

Abstract
Space-time prisms capture all possible spatio-temporal locations of a moving object between sample points given speed limit constraints on its movement. These sample points are usually considered to be perfect measurements. In this paper we restrict ourselves to a road network and extend the notion of sample points to sample regions, which are bounded, sometimes disconnected, subsets of space-time wherein each point is a possible location, with its respective probability, where a moving object could have originated from or arrived in. This model allows us to model measurement errors, multiple possible simultaneous locations and even flexibility of a moving object. We develop an algorithm that computes the envelope of all space-time prisms that have an anchor in these sample regions and we developed an algorithm that computes for any spatio-temporal point the probability with which a space-time prism, with anchors in these sample regions, contains that point. We implemented these algorithms in Mathematica to visualise all these newly-introduced concepts.
Cite as

Bart Kuijpers, Harvey J. Miller, Tijs Neutens, and Walied Othman. Propagating and measuring anchor uncertainty in space-time prisms on road networks. In Geographic Privacy-Aware Knowledge Discovery and Delivery. Dagstuhl Seminar Proceedings, Volume 8471, pp. 1-35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{kuijpers_et_al:DagSemProc.08471.2,
  author =	{Kuijpers, Bart and Miller, Harvey J. and Neutens, Tijs and Othman, Walied},
  title =	{{Propagating and measuring anchor uncertainty in space-time prisms on road networks}},
  booktitle =	{Geographic Privacy-Aware Knowledge Discovery and Delivery},
  pages =	{1--35},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8471},
  editor =	{Bart Kuijpers and Dino Pedreschi and Yucel Saygin and Stefano Spaccapietra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08471.2},
  URN =		{urn:nbn:de:0030-drops-20072},
  doi =		{10.4230/DagSemProc.08471.2},
  annote =	{Keywords: Space-time prisms, beads, prisms, uncertainty, flexibility, time-geography}
}
Document
DOI: 10.4230/DagSemProc.07212.4
An analytic solution to the alibi query in the bead model for moving object data

Authors: Bart Kuijpers and Walied Othman

Published in: Dagstuhl Seminar Proceedings, Volume 7212, Constraint Databases, Geometric Elimination and Geographic Information Systems (2007)

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.
Cite as

Bart Kuijpers and Walied Othman. An analytic solution to the alibi query in the bead model for moving object data. In Constraint Databases, Geometric Elimination and Geographic Information Systems. Dagstuhl Seminar Proceedings, Volume 7212, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@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/entities/document/10.4230/DagSemProc.07212.4},
  URN =		{urn:nbn:de:0030-drops-12864},
  doi =		{10.4230/DagSemProc.07212.4},
  annote =	{Keywords: Beads, uncertainty, alibi, query, solution, quantifier elimination, constraint database}
}
  • Refine by Type
  • 4 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2009
  • 1 2007

  • Refine by Author
  • 4 Kuijpers, Bart
  • 2 Jansen, Arthur
  • 2 Othman, Walied
  • 1 Miller, Harvey J.
  • 1 Neutens, Tijs

  • Refine by Series/Journal
  • 2 LIPIcs
  • 2 DagSemProc

  • Refine by Classification
  • 2 Information systems → Spatial-temporal systems
  • 1 Information systems → Query languages
  • 1 Mathematics of computing → Probability and statistics

  • Refine by Keyword
  • 2 uncertainty
  • 1 Beads
  • 1 Convex geometry
  • 1 Geographic information systems
  • 1 Quantifier elimination
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact