Scaling cautious selection in spatial probabilistic temporal databases

SPOT databases have been proposed as a paradigm for efficiently reasoning about probabilistic spatio-temporal data. A selection query asks for all pairs of objects and times such that the object is within a query region with a probability within a stated probability interval. Two alternative semantics have been introduced for selection queries: optimistic and cautious selection. It has been shown in past work that selection is characterized by a linear program whose solutions correspond to certain kinds of probability density functions (pdfs). In this chapter, we define a space called the SPOT PDF Space (SPS for short) and show that the space of solutions to a cautious selection query is a convex polytope in this space. This convex polytope can be approximated both by an interior region and a containing region. We show that both notions can be jointly used to prune the search space when answering a query. We report on experiments showing that cautious selection can be executed in about 4 seconds on databases containing 3 million SPOT atoms.