In many applications, including location based services, queries may not be precise. In this paper, we study the problem of efficiently computing range aggregates in a multidimensional space when the query location is uncertain. Specifically, for a query point Q whose location is uncertain and a set S of points in a multi-dimensional space, we want to calculate the aggregate (e.g., count, average and sum) over the subset SI of S, Q has at least probability θ within the distance γ to p. We propose novel, efficient techniques to solve the problem following the filtering-and-verification paradigm. In particular, two novel filtering techniques are proposed to effectively and efficiently remove data points from verification. Our comprehensive experiments based on both real and synthetic data demonstrate the efficiency and scalability of our techniques. Efficient Multi-dimensional Fuzzy Search for Personal Information Management Systems
The existing techniques for processing location based spatial queries regarding certain query points and data points are not applicable or inefficient when uncertain queries are involved.
Our techniques will be presented based on the aggregate count. Nevertheless, they can be immediately extended to cover other aggregates, such as min, max, sum, avg, etc. In this application, the risk of civilian casualties may be measured by the total number n of civilian objects which are within γ distance away from a possible blast point with at least θ probability. It is important to avoid the civilian casualties by estimating the likelihood of damaging civilian objects once the aiming point of a distance (km) is determined.