Optimized full-spectrum cardinality estimation based on unified counting and ordering estimation techniques
US10983976B2 · kind B2 · utility
Assignee
Inventor
Key dates
| Filing date | Jan 24, 2017 |
| Grant date | Apr 20, 2021 |
| Priority date | — |
| Expiry date | Oct 11, 2037 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/2255
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Systems and methods are disclosed for optimizing full-spectrum cardinality approximations on big data by exploiting an underlying relationship between LogLog counting estimation techniques and order statistics-based estimation techniques. To accomplish the foregoing, a multiset of objects that each corresponds to one of a plurality of objects associated with a resource are obtained by a computing device. A compound data object is populated by the computing device with data that is derived based on generated hash values that correspond to each object in the obtained multiset. The populated compound data object is processed utilizing a processor with a full-spectrum unified estimation operation that can accurately determine a cardinality estimate for the obtained multiset, utilizing considerably less resources when compared to traditional and state of the art techniques. The determination is made by the computing device without the need to employ linear counting for low cardinalities, bias correction operations, or angular correction terms, all while offering decreased memory usage, simpler implementation, improved performance, and comparable or improved accuracy. An estimated number…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.