Method for maintaining a sample synopsis under arbitrary insertions and deletions

1. 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.

2. The method of claim 1 , further comprising steps of:

keeping a count of uncompensated deletions; and

removing, in response to a deletion wherein the deletion deletes a deleted item from the dataset R, the deleted item from S if and only if the deleted item is in S; and incrementing the count of uncompensated deletions.

3. The method of claim 1 , further comprising steps of:

keeping a first count, c 1 , of uncompensated deletions of items in sample S;

keeping a second count, c 2 , of uncompensated deletions of items not in sample S; and wherein:

said determining step comprises determining that there is at least one uncompensated deletion if c 1 +c 2 >0; and

said compensating step comprises including the first item into S with probability c 1 /(c 1 +c 2 ).

4. The method of claim 1 , further comprising steps of:

keeping a count of uncompensated deletions, said count starting at zero in response to there having been no deletions to the dataset R, said count being incremented in response to a deletion, and said count being decremented, only in the case that said count is greater than zero, in response to an insertion;

performing, in response to said count being greater than zero, said compensating step in response to the insertion; and

including, in response to said count being equal to zero and to the insertion, the first item into the sample S with probability equal to a bound M on the size |S| of S divided by a size |R| of R.

5. The method of claim 1 , further comprising steps of:

keeping a first count, c 1 , of uncompensated deletions of items in sample S;

keeping a second count, c 2 , of uncompensated deletions of items not in sample S;

performing, in response to (c 1 +c 2 ) being greater than zero, said compensating step wherein the first item is included into S with probability c 1 /(c 1 +c 2 );

replacing a random item of S, in response to (c 1 +c 2 ) being equal to zero, by the first item with probability, M/max(M, |R|), equal to a bound M on the size |S| of S divided by the maximum of M and a size |R| of R.

6. The method of claim 1 , further comprising steps of:

incrementing a first count, c 1 , of uncompensated deletions of items in sample S, in response to a deleted item being removed from S;

incrementing a second count, c 2 , of uncompensated deletions of items not in sample S, in response to the deleted item not being removed from S;

replacing a random item of S, in response to (c 1 +c 2 ) being equal to zero, by the first item with probability, M/max(M, |R|), equal to a bound M on the size |S| of S divided by the maximum of M and a size |R| of R;

performing, in response to (c 1 +c 2 ) being greater than zero, said compensating step wherein the first item is included into S with probability c 1 /(c 1 +c 2 ) while decrementing c 1 in response to the first item being included into S and decrementing c 2 in response to the first item not being included into S.

7. The method of claim 1 , further comprising steps of:

determining whether a size |S| of the sample S has decreased by a pre-determined criterion; and

refilling the sample S in response to the pre-determined criterion being satisfied.

8. A database system, the database system including a dataset R having size |R| and a sample S from the dataset R, the sample S bounded by M, the database system executing steps for:

creating an initial Bernoulli sample, wherein:

an item of said initial Bernoulli sample is sampled from one of S or R\S; and

said initial Bernoulli sample is bounded by M′, with M<M′<|R|; and

increasing the size of said initial Bernoulli sample to a resized sample by sampling from a stream of transactions on R using Bernoulli sampling, wherein said resized sample is bounded by M′.

9. The database system of claim 8 , wherein said creating step further comprises:

generating a bound U for said initial Bernoulli sample size from a binomial distribution; and

creating said initial Bernoulli sample using as many items from S as possible to make up the initial Bernoulli sample having size U, while accessing base dataset R only if U>|S|.

10. The database system of claim 8 , wherein:

said creating step further comprises generating a bound U for said initial Bernoulli sample size from a binomial distribution with parameters |R| and q; and

said increasing step comprises Bernoulli sampling with probability q from said stream of transactions.

11. The database system of claim 8 , wherein:

said creating step further comprises generating a bound U for said initial Bernoulli sample size from a binomial distribution with parameters |R| and q;

said increasing step comprises Bernoulli sampling with probability q from said stream of transactions; and further comprising a step of:

optimizing q relative to said creating step and said increasing step.

12. The database system of claim 8 , wherein:

said creating step further comprises generating a bound U for said initial Bernoulli sample size from a binomial distribution with parameters |R| and q;

said increasing step comprises Bernoulli sampling with probability q from said stream of transactions; and further comprising a step of:

choosing q in the interval of real numbers from M/|R| to M′/|R| so as to minimize a total cost T(q) of computing said creating step and said increasing step.

13. The database system of claim 8 , wherein said increasing step includes:

including, in response to an insertion transaction to dataset R, an inserted item with probability q, while said resized sample remains bounded by M′;

removing, in response to a deletion transaction to dataset R, a deleted item from said resized sample if the deleted item was in said resized sample; and

terminating in response to said resized sample having size M′.

14. A computer program product comprising a computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:

maintain a bounded sample S from a dataset R, wherein said bounded sample is bounded by a pre-determined integer M;

determine a new bound M′ in response to growth of the dataset R;

increase the sample S to a resized sample S wherein said resized sample S is bounded by a new bound M′; and

continue maintaining the bounded resized sample S from the dataset R, wherein said bounded resized sample S is bounded by M′.

15. The computer program product of claim 14 , wherein:

the computer maintains the bounded sample S using a random pairing method.

16. The computer program product of claim 14 , wherein:

the computer increases the sample S in two phases, wherein:

a first phase comprises choosing an initial sample size U, sampling from S; sampling from R\S if U>|S|; passing an initial Bernoulli sample to a second phase if U<M′; and providing the initial Bernoulli sample of size M′ as the resized sample S if U≧M′; and

the second phase comprises increasing the initial Bernoulli sample by Bernoulli sampling from a stream of transactions to the dataset R if the resized sample S has size |S|<M′.

17. The computer program product of claim 14 , wherein:

the computer continues maintaining the bounded resized sample S using a random pairing method.

18. The computer program product of claim 14 , wherein:

the computer periodically determines whether the dataset size |R| has exceeded a specified growth condition.

19. The computer program product of claim 14 , wherein:

the computer periodically determines a new upper bound M′ according to a pre-determined resizing condition.