Method of obtaining data samples from a data stream and of estimating the sortedness of the data stream based on the samples
US7797326B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 18, 2006 |
| Grant date | Sep 14, 2010 |
| Priority date | — |
| Expiry date | Nov 22, 2027 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/951
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Disclosed is a method of scanning a data stream in a single pass to obtain uniform data samples from selected intervals. The method comprises randomly selecting elements from the stream for storage in one or more data buckets and, then, randomly selecting multiple samples from the bucket(s). Each sample is associated with a specified interval immediately prior to a selected point in time. There is a balance of probabilities between the selection of elements stored in the bucket and the selection of elements included in the samples so that elements scanned during the specified interval are included in the sample with equal probability. Samples can then be used to estimate the degree of sortedness of the stream, based on counting how many elements in the sequence are the rightmost point of an interval such that majority of the interval's elements are inverted with respect to the interval's rightmost element.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.