Method for estimating the number of distinct values in a partitioned dataset
US7987177B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jan 30, 2008 |
| Grant date | Jul 26, 2011 |
| Priority date | — |
| Expiry date | Apr 11, 2029 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/24545
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The task of estimating the number of distinct values (DVs) in a large dataset arises in a wide variety of settings in computer science and elsewhere. The present invention provides synopses for DV estimation in the setting of a partitioned dataset, as well as corresponding DV estimators that exploit these synopses. Whenever an output compound data partition is created via a multiset operation on a pair of (possibly compound) input partitions, the synopsis for the output partition can be obtained by combining the synopses of the input partitions. If the input partitions are compound partitions, it is not necessary to access the synopses for all the base partitions that were used to construct the input partitions. Superior (in certain cases near-optimal) accuracy in DV estimates is maintained, especially when the synopsis size is small. The synopses can be created in parallel, and can also handle deletions of individual partition elements.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.