Patent · US Active

Method for maintaining a sample synopsis under arbitrary insertions and deletions

US7536403B2 · kind B2 · utility

7Cited by

4References

1Claims

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	Dec 22, 2006
Grant date	May 19, 2009
Priority date	—
Expiry date	Jul 25, 2027

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.