US 2008/0177696 A1 · METHOD FOR MAINTAINING A SAMPLE SYNOPSIS UNDER ARBITRARY INSERTIONS AND DELETIONS

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.

Claims19

Dependent claims

A computer-implemented 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, comprising the steps of:

determining whether or not there is an uncompensated deletion among the deletions to the dataset R;
and
in response to an insertion of a first item into the dataset R, and in the case that there is at least one uncompensated deletion of a second item from the dataset R;
compensating, in S, the uncompensated deletion by the insertion by including the first item into S if and only if the second item was in S.

1 more element

Dependencies are inferred from the claim text.

Method for maintaining a sample synopsis under arbitrary insertions and deletions

Life of this patent

Method for maintaining a sample synopsis under arbitrary insertions and deletions

Life of this patent

Abstract

Claims19