Method for maintaining a sample synopsis under arbitrary...

Details Method for maintaining a sample synopsis under arbitrary... Method for maintaining a sample synopsis under arbitrary...

2008-03-24

2010-11-02

Lewis, Cheryl (Department: 2167)

Data processing: database and file management or data structures

Database design

Database and data structure management

C707S609000

Reexamination Certificate

active

07827211

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.

REFERENCES:
patent: 6012064 (2000-01-01), Gibbons et al.
patent: 6317752 (2001-11-01), Lee et al.
patent: 6532458 (2003-03-01), Chaudhuri et al.
patent: 6542886 (2003-04-01), Chaudhuri et al.
patent: 7373359 (2008-05-01), Hill et al.
patent: 7536403 (2009-05-01), Gemulla et al.
patent: 7543006 (2009-06-01), Brown et al.
patent: 2004/0249810 (2004-12-01), Das et al.
patent: 2005/0223019 (2005-10-01), Das et al.
Office Action from U.S. Appl. No. 11/615,481 dated Oct. 10, 2008.
Notice of Allowance dated Jan. 14, 2009 from U.S. Appl. No. 11/615,481.
P.B. Gibbons and Y. Matias, New sampling-based summary statistics for improving approximate query answers. In Proc. ACM SIGMOD, 1998, pp. 331-342, ACM, Seattle, WA, USA.

Affiliated with

Also associated with

Rating

Method for maintaining a sample synopsis under arbitrary... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for maintaining a sample synopsis under arbitrary..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for maintaining a sample synopsis under arbitrary... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4166544