Approximate Aggregate Spatial Queries over Multidimensional Uncertain Databases

Uncertain data is inherent in LBS, sensor network and so on. Although a considerable amount of research has been dedicated to answering queries on uncertain data, how to process spatial queries over multidimensional uncertain data is still a challenge due to the prohibitive time cost when the dimensionality is high. This work focuses on seeking efficient approximate answers for the spatial queries. Specifically, given a spatial query over multidimensional uncertain objects and an error bound, we propose effective synopses to return answers with a bounded error efficiently. The existing synopses for uncertain databases are mainly designed for one dimensional databases, which cannot offer efficient answers for queries over multidimensional data. Aiming to solve this problem, we formally define Possible World Synopses (PWS) which achieve data reduction on the original possible worlds for multidimensional uncertain objects. Furthermore, PWS retain the possible worlds semantics of uncertain objects, allowing for more accurate representation of original data and query results. Based on PWS, we present a framework to answer approximate spatial queries with different precision constraints. The effectiveness of our framework is illustrated by extensive experiments. The framework proposed can efficiently and approximately handle various types of complex queries in many applications like location selection for urban planning.