A logical formulation of probabilistic spatial databases

Austin Parker*, V. S. Subrahmanian, John Grant

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

There are numerous applications where there is uncertainty over space and time. Examples of such uncertainty arise in vehicle tracking systems where we are not always sure where a vehicle is now (or may be in the future), and cell and satellite phone applications where we are not sure exactly where a phone may be, and so on. In this paper, we propose the concept of a Spatial Probabilistic Temporal (SPOT) database that contains statements of the form "Object O is in spatial region R at some time t with some probability in the Interval [L, U]." We define the syntax and a declarative semantics for SPOT databases based on a mix of logic and linear programming, as well as query algebra. We show alternative implementations of some of these query algebra operators when the SPOT database has a disjointness property. Though the declarative semantics of SPOT databases is rooted in linear programming, we have found very efficient algorithms that do not use linear programming methods. We report on experiments we have conducted that show that the system scales to large numbers of SPOT atoms, as well as to fairly fine temporal and spatial granularity.

Original languageEnglish (US)
Pages (from-to)1541-1556
Number of pages16
JournalIEEE Transactions on Knowledge and Data Engineering
Volume19
Issue number11
DOIs
StatePublished - Nov 2007
Externally publishedYes

Keywords

  • Probabilistic database
  • Spatial database

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'A logical formulation of probabilistic spatial databases'. Together they form a unique fingerprint.

Cite this