TY - JOUR
T1 - SPOT Databases: Efficient Consistency Checking and Optimistic Selection in Probabilistic Spatial Databases
JF - Knowledge and Data Engineering, IEEE Transactions on
Y1 - 2009
A1 - Parker,A.
A1 - Infantes,G.
A1 - Grant,J.
A1 - V.S. Subrahmanian
KW - Cartesian
KW - checking;database
KW - database;data
KW - databases;
KW - databases;visual
KW - indexing;inference
KW - indexing;linear
KW - integrity;database
KW - mechanisms;linear
KW - probabilistic
KW - problem;spatial
KW - problems;temporal
KW - processing;search
KW - program;optimistic
KW - programming;probability;query
KW - query;probabilistic
KW - reasoning;search
KW - selection
KW - selection;consistency
KW - space;cautious
KW - temporal
AB - 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. Second, our experiments, which are based on real-world data about ship movements, show that our algorithms are much more efficient than those in.
VL - 21
SN - 1041-4347
CP - 1
M3 - 10.1109/TKDE.2008.93
ER -