The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Jul. 26, 2011
Filed:
Jan. 30, 2008
Kevin Scott Beyer, San Jose, CA (US);
Rainer Gemulla, Dresden, DE;
Peter Jay Haas, San Jose, CA (US);
Berthold Reinwald, San Jose, CA (US);
John Sismanis, San Jose, CA (US);
Kevin Scott Beyer, San Jose, CA (US);
Rainer Gemulla, Dresden, DE;
Peter Jay Haas, San Jose, CA (US);
Berthold Reinwald, San Jose, CA (US);
John Sismanis, San Jose, CA (US);
International Business Machines Corporation, Armonk, NY (US);
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.