Patent · US Active

Method for maintaining a sample synopsis under arbitrary insertions and deletions

US7827211B2 · kind B2 · utility

1Cited by

7References

19Claims

0Family size

Assignee

International Business Machines Corporation · US

Inventors

Rainer Gemulla · Riegelsberg, DE
Peter J. Haas · San Jose, US
Wolfgang Lehner · Dresden, DE

Key dates

Filing date	Mar 24, 2008
Grant date	Nov 2, 2010
Priority date	—
Expiry date	Apr 24, 2029

Classification

Technology area (CPC Y)Emerging Cross-Sectional Technologies
CPC primaryY10S707/99942
WIPO fieldComputer technology
WIPO sectorElectrical engineering

Abstract

A method of incrementally maintaining a stable, bounded, uniform random sample S from a dataset R, in the presence of arbitrary insertions and deletions to the dataset R, and without accesses to the dataset R, comprises a random pairing method in which deletions are uncompensated until compensated by a subsequent insertion (randomly paired to the deletion) by including the insertion's item into S if and only if the uncompensated deletion's item was removed from S (i.e., was in S so that it could be removed). A method for resizing a sample to a new uniform sample of increased size while maintaining a bound on the sample size and balancing cost between dataset accesses and transactions to the dataset is also disclosed. A method for maintaining uniform, bounded samples for a dataset in the presence of growth in size of the dataset is additionally disclosed.

Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.