Efficient top-K query evaluation on probabilistic data

Details Efficient top-K query evaluation on probabilistic data Efficient top-K query evaluation on probabilistic data

2007-11-05

2010-10-12

Mofiz, Apu M (Department: 2161)

Data processing: database and file management or data structures

Database and file access

Record, file, and data search and comparisons

C707S713000, C707S780000

Reexamination Certificate

active

07814113

ABSTRACT:
A novel approach that computes and efficiently ranks the top-k answers to a query on a probabilistic database. The approach identifies the top-k answers, since imprecisions in the data often lead to a large number of answers of low quality. The algorithm is used to run several Monte Carlo simulations in parallel, one for each candidate answer, and approximates the probability of each only to the extent needed to correctly determine the top-k answers. The algorithm is provably optimal and scales to large databases. A more general application can identify a number of top-rated entities of a group that satisfy a condition, based on a criteria or score computed for the entities. Also disclosed are several optimization techniques. One option is to rank the top-rated results; another option provides for interrupting the iteration to return the number of top-rated entities that have thus far been identified.

REFERENCES:
patent: 5675819 (1997-10-01), Schuetze
patent: 6370525 (2002-04-01), Kaufman
patent: 6801909 (2004-10-01), Delgado et al.
patent: 6947934 (2005-09-01), Chen et al.
patent: 7047242 (2006-05-01), Ponte
patent: 7251648 (2007-07-01), Chaudhuri et al.
patent: 2008/0033915 (2008-02-01), Chen et al.
Das et al., Answering Top-k Queries Using Views, Sep. 2006, VLDB Endowment, pp. 451-462.
Marian et al., Evaluating Top-k Queries Over Web-Accessible Databases, Jun. 2004, ACM, vol. 29, Issue 2, pp. 319-362.
Nambiar et al., Mining Approximate Functional Dependencies and Concept Similarities to Answer Imprecise Queries, Jun. 2004, ACM, pp. 73-78.

Affiliated with

Also associated with

Rating

Efficient top-K query evaluation on probabilistic data does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient top-K query evaluation on probabilistic data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient top-K query evaluation on probabilistic data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4194740