Probabilistic lossy counting
US7937388B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Aug 20, 2008 |
| Grant date | May 3, 2011 |
| Priority date | — |
| Expiry date | Oct 29, 2029 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L43/16
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A method for probabilistic lossy counting includes: for each element in a current window, determining whether an entry corresponding to a current element is present in a table; in the event an entry corresponding to the current element is present in the table, incrementing a frequency counter associated with the current element; otherwise, inserting an entry into a table, wherein inserting an entry comprises: calculating a probabilistic error bound Δ based on an index i of the current window; and inserting the probabilistic error bound Δ and a frequency counter into an entry corresponding to the current element in the table; and at the end of the current window, removing all elements from the table wherein the sum of the frequency counter and probabilistic error bound Δ associated with the element is less than or equal to the index of the current window.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.