Variance-optimal sampling-based estimation of subset sums
US8005949B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 1, 2008 |
| Grant date | Aug 23, 2011 |
| Priority date | — |
| Expiry date | Jul 11, 2029 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L43/16
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
The present invention relates to a method of obtaining a generic sample of an input stream. The method is designated as VAROPTk. The method comprises receiving an input stream of items arriving one at a time, and maintaining a sample S of items i. The sample S has a capacity for at most k items i. The sample S is filled with k items i. An nth item i is received. It is determined whether the nth item i should be included in sample S. If the nth item i is included in sample S, then a previously included item i is dropped from sample S. The determination is made based on weights of items without distinguishing between previously included items i and the nth item i. The determination is implemented thereby updating weights of items i in sample S. The method is repeated until no more items are received.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.