Flexible, efficient and scalable sampling

Details Flexible, efficient and scalable sampling Flexible, efficient and scalable sampling

2006-08-31

2009-06-02

Woo, Isaac M (Department: 2166)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

07543006

ABSTRACT:
A sampling infrastructure/scheme that supports flexible, efficient, scalable and uniform sampling is disclosed. A sample is maintained in a compact histogram form while the sample footprint stays below a specified upper bound. If, at any point, the sample footprint exceeds the upper bound, then the compact representation is abandoned, the sample purged to obtain a subsample. The histogram of the purged subsample is expanded to a bag of values while sampling remaining data values of the partitioned subset. The expanded purged subsample is converted to a histogram and uniform random samples are yielded. The sampling scheme retains the bounded footprint property and to a partial degree the compact representation of the Concise Sampling scheme, while ensuring statistical uniformity. Samples from at least two partitioned subsets are merged on demand to yield uniform merged samples of combined partitions wherein the merged samples also maintain the histogram representation and bounded footprint property.

REFERENCES:
patent: 5878426 (1999-03-01), Plasek et al.
patent: 6012064 (2000-01-01), Gibbons et al.
patent: 6049861 (2000-04-01), Bird et al.
patent: 6542886 (2003-04-01), Chaudhuri et al.
patent: 6564221 (2003-05-01), Shatdal
patent: 6889221 (2005-05-01), Luo et al.
patent: 2002/0198863 (2002-12-01), Anjur et al.
patent: 2003/0004944 (2003-01-01), Harper et al.
patent: 2003/0004973 (2003-01-01), Harper et al.
patent: 2004/0049492 (2004-03-01), Gibbons
patent: 2006/0101048 (2006-05-01), Mazzagatti et al.
Phillip Gibbons et al. “New Sampling-Based Summary Statistics for Improving Approximate Query Answers” International Conference on Management of Data, Proceedings of th 1998 ACM SIGMOD International Conference on Management of Data; 1998; pp. 331-342.
Jeffrey Vitter “Random Sampling with a Reservoir” ACM Transactions on Mathematical Software (TOMS), vol. 11, Issue ; Mar. 1985; pp. 37-57.

Affiliated with

Also associated with

Rating

Flexible, efficient and scalable sampling does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Flexible, efficient and scalable sampling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Flexible, efficient and scalable sampling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4072934