27-11-2012, 03:59 PM
EFFICIENT COMPUTING OF RANGE AGGREGATES AGAINST UNCERTAIN LOCATION BASED QUERIES
ABSTRACT
In many applications, including location based services, queries are not precise. In this paper, we study the problem of efficiently computing range aggregates in a multi-dimensional space when the query location is uncertain.
That is, for a set of data points P, an uncertain location based query Q with location described by a probabilistic density function, we want to calculate the aggregate information (e.g., count, average} and sum) of the data points within distance gamma to Q with probability at least theta. We propose novel, efficient techniques to solve the problem based on a filtering-and-verification framework.
In particular, two novel filtering techniques are proposed to effectively and efficiently remove data points from verification. Finally, we show that our techniques can be immediately extended to solve the range query problem. Comprehensive experiments conducted on both real and synthetic data demonstrate the efficiency and scalability of our techniques.