SPOT databases: Efficient consistency checking and optimistic selection in probabilistic spatial databases

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

Abstract

Spatial PrObabilistic Temporal (SPOT) databases are a paradigm for reasoning with probabilistic statements about where a vehicle may be now or in the future. They express statements of the form "Object O is in spatial region R at some time t with some probability in the interval [L, U]." Past work on SPOT databases has developed selection operators based on selecting SPOT atoms that are entailed by the SPOT database - we call this "cautious" selection. In this paper, we study several problems. First, we note that the runtime of consistency checking and cautious selection algorithms in past work is influenced greatly by the granularity of the underlying Cartesian space. In this paper, we first introduce the notion of "optimistic" selection, where we are interested in returning all SPOT atoms in a database that are consistent with respect to a query, rather than having an entailment relationship. We then develop an approach to scaling SPOT databases that has three main contributions: 1) We develop methods to eliminate variables from the linear programs used in past work, thus greatly reducing the size of the linear programs used-the resulting advances apply to consistency checking, optimistic selection, and cautious selection. 2) We develop a host of theorems to show how we can prune the search space when we are interested in optimistic selection. 3) We use the above contributions to build an efficient index to execute optimistic selection queries over SPOT databases. Our approach is superior to past work in two major respects: First, it makes fewer assumptions than all past works on this topic except that in [30]. Second, our experiments, which are based on real-world data about ship movements, show that our algorithms are much more efficient than those in [30].

Original languageEnglish (US)
Article number4515871
Pages (from-to)92-107
Number of pages16
JournalIEEE Transactions on Knowledge and Data Engineering
Volume21
Issue number1
DOIs
StatePublished - Jan 2009
Externally publishedYes

Funding

Researchers funded in part by Grant N6133906C0149, ARO Grant DAAD190310202, AFOSR Grants FA95500610405 and FA95500510298, and US National Science Foundation Grant 0540216. The authors are very grateful to the editor, the reviewers, and Francesco Parisi for many helpful comments.

Keywords

  • Probabilistic database
  • Spatial database
  • Uncertainty management

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'SPOT databases: Efficient consistency checking and optimistic selection in probabilistic spatial databases'. Together they form a unique fingerprint.

Cite this