Scaling cautious selection in spatial probabilistic temporal databases

Francesco Parisi*, Austin Parker, John Grant, V. S. Subrahmanian

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapter

11 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationMethods for Handling Imperfect Spatial Information
EditorsRobert Jeansoulin
Pages307-340
Number of pages34
DOIs
StatePublished - 2010
Externally publishedYes

Publication series

NameStudies in Fuzziness and Soft Computing
Volume256
ISSN (Print)1434-9922

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Scaling cautious selection in spatial probabilistic temporal databases'. Together they form a unique fingerprint.

Cite this