Method for summarizing data in unaggregated data streams
US8195710B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 18, 2009 |
| Grant date | Jun 5, 2012 |
| Priority date | — |
| Expiry date | Aug 3, 2030 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L43/04
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A method for producing a summary A of data points in an unaggregated data stream wherein the data points are in the form of weighted keys (a, w) where a is a key and w is a weight, and the summary is a sample of k keys a with adjusted weights wa. A first reservoir L includes keys having adjusted weights which are additions of weights of individual data points of included keys and a second reservoir T includes keys having adjusted weights which are each equal to a threshold value τ whose value is adjusted based upon tests of new data points arriving in the data stream. The summary combines the keys and adjusted weights of the first reservoir L with the keys and adjusted weights of the second reservoir T to form the sample representing the data stream upon which further analysis may be performed. The method proceeds by first merging new data points in the stream into the reservoir L until the reservoir contains k different keys and thereafter applying a series of tests to new arriving data points to determine what keys and weights are to be added to or removed the reservoirs L and T to provide a summary with a variance that approaches the minimum possible for aggregated data sets. Th…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.