A Novel Probabilistic Pruning Approach to Speed Up Similarity Queries in Uncertain Databases

Details A Novel Probabilistic Pruning Approach to Speed Up Similarity Queries in Uncertain Databases A Novel Probabilistic Pruning Approach to Speed Up Similarity Queries in Uncertain Databases

2011-01-13

arxiv.org/abs/1101.2613v2

Computer Science

Databases

Scientific paper

In this paper, we propose a novel, effective and efficient probabilistic pruning criterion for probabilistic similarity queries on uncertain data. Our approach supports a general uncertainty model using continuous probabilistic density functions to describe the (possibly correlated) uncertain attributes of objects. In a nutshell, the problem to be solved is to compute the PDF of the random variable denoted by the probabilistic domination count: Given an uncertain database object B, an uncertain reference object R and a set D of uncertain database objects in a multi-dimensional space, the probabilistic domination count denotes the number of uncertain objects in D that are closer to R than B. This domination count can be used to answer a wide range of probabilistic similarity queries. Specifically, we propose a novel geometric pruning filter and introduce an iterative filter-refinement strategy for conservatively and progressively estimating the probabilistic domination count in an efficient way while keeping correctness according to the possible world semantics. In an experimental evaluation, we show that our proposed technique allows to acquire tight probability bounds for the probabilistic domination count quickly, even for large uncertain databases.

Affiliated with

Also associated with

No associations

Rating

A Novel Probabilistic Pruning Approach to Speed Up Similarity Queries in Uncertain Databases does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Novel Probabilistic Pruning Approach to Speed Up Similarity Queries in Uncertain Databases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Novel Probabilistic Pruning Approach to Speed Up Similarity Queries in Uncertain Databases will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-66971