SPOT Databases: Efficient Consistency Checking and Optimistic Selection in Probabilistic Spatial Databases

摘要

Spatial PrObabilistic Temporal (SPOT) databases are a paradigm for reasoning with probabilistic statements about where objects are now or in the future. They express statements of the form "Object O is in spatial region R at time t with some probability in the interval [L,U]." Past work on SPOT databases uses selection operators returning SPOT atoms entailed by the SPOT database - we call this "cautious" selection. In this paper, we study several problems. First, we introduce the notion of "optimistic" selection queries that return sets of SPOT atoms consistent with, rather than entailed by, the SPOT database. We then develop an approach to scaling SPOT databases that has three main contributions: (i) We substantially reduce the size of past work's linear programs via variable elimination. (ii) We rigorously prove how one can prune the space searched in optimistic selection. (iii) We 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 [30]. Second, the experiments - some using real world ship movement data - show substantially better performance than achieved in [30].