Representative Query Answers on Uncertain Data
Klaus Arthur Schmid, Andreas E Züfle · 2019
Our goal is to incorporate uncertainty information in the querying process to enhance results with probabilistic guarantees. Existing probabilistic querying solutions can not be scaled to realistic data sets due to #P-complete nature of querying uncertain data. We present a new approach to query uncertain sets of spatial data by sampling the possible database worlds, each resulting in a possible query result. The main challenge is to find a consensus of the retrieved results. We tackle this by finding query results that are representative. A representative query result is associated with a probabilistic guarantee, stating that with a guaranteed probability, the true (but unknown) query result is sufficiently similar. Our experiments show that our sampling approach provides probabilistic guarantees while scaling to large data sets, thus allowing to perform queries such as range queries, kNN queries, RkNN queries and ranking queries, where state-of-the-art solutions do not scale.