TY - JOUR
T1 - A logical formulation of probabilistic spatial databases
AU - Parker, Austin
AU - Subrahmanian, V. S.
AU - Grant, John
N1 - Funding Information:
The authors would like to thank the referees and the editor for their many helpful comments and suggestions. This research was funded in part by Grant N6133906C0149, US Army Research Office (ARO) Grant DAAD190310202, US Air Force Office of Scientific Research (AFOSR) Grants FA95500610405 and FA95500510298, and US NSF Grant 0540216.
PY - 2007/11
Y1 - 2007/11
N2 - 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.
AB - 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.
KW - Probabilistic database
KW - Spatial database
UR - http://www.scopus.com/inward/record.url?scp=35348822069&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35348822069&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2007.190631
DO - 10.1109/TKDE.2007.190631
M3 - Article
AN - SCOPUS:35348822069
SN - 1041-4347
VL - 19
SP - 1541
EP - 1556
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 11
ER -