Efficient top-K query evaluation on probabilistic data
US7814113B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Nov 5, 2007 |
| Grant date | Oct 12, 2010 |
| Priority date | — |
| Expiry date | Dec 19, 2028 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/3346
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.