Scalable Probabilistic Similarity Ranking in Uncertain Databases (Technical Report)

Details Scalable Probabilistic Similarity Ranking in Uncertain Databases (Technical Report) Scalable Probabilistic Similarity Ranking in Uncertain Databases (Technical Report)

2009-07-16

arxiv.org/abs/0907.2868v1

Computer Science

Databases

Scientific paper

This paper introduces a scalable approach for probabilistic top-k similarity ranking on uncertain vector data. Each uncertain object is represented by a set of vector instances that are assumed to be mutually-exclusive. The objective is to rank the uncertain data according to their distance to a reference object. We propose a framework that incrementally computes for each object instance and ranking position, the probability of the object falling at that ranking position. The resulting rank probability distribution can serve as input for several state-of-the-art probabilistic ranking models. Existing approaches compute this probability distribution by applying a dynamic programming approach of quadratic complexity. In this paper we theoretically as well as experimentally show that our framework reduces this to a linear-time complexity while having the same memory requirements, facilitated by incremental accessing of the uncertain vector instances in increasing order of their distance to the reference object. Furthermore, we show how the output of our method can be used to apply probabilistic top-k ranking for the objects, according to different state-of-the-art definitions. We conduct an experimental evaluation on synthetic and real data, which demonstrates the efficiency of our approach.

Affiliated with

Also associated with

No associations

Rating

Scalable Probabilistic Similarity Ranking in Uncertain Databases (Technical Report) 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 Scalable Probabilistic Similarity Ranking in Uncertain Databases (Technical Report), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scalable Probabilistic Similarity Ranking in Uncertain Databases (Technical Report) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-622420