Adaptive distinct counting for network-traffic monitoring and other applications
US8931088B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 26, 2010 |
| Grant date | Jan 6, 2015 |
| Priority date | — |
| Expiry date | Apr 27, 2032 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L43/00
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
In one embodiment, a counting method of the invention uses an adaptive sketching-update process to compress an unknown cardinality into a counter value that counts the number of binary ones in a hashed bitmap vector. The sketching-update process is probabilistic in nature and uses bit-flip probabilities that are adaptively decreased as the counter value increases. Parameters of the sketching-update process are selected so that the relative error of cardinality estimates obtained based on the counter values is relatively small and substantially constant over a relatively wide range of cardinalities, e.g., from one to about one million. Due to the latter property, the counting method can advantageously be implemented in the form of embedded software that relies on a relatively small, fixed amount of memory.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.