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 language | English (US) |
---|---|
Article number | 4515871 |
Pages (from-to) | 92-107 |
Number of pages | 16 |
Journal | IEEE Transactions on Knowledge and Data Engineering |
Volume | 21 |
Issue number | 1 |
DOIs | |
State | Published - Jan 2009 |
Externally published | Yes |
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