Distributed reservoir sampling for web applications

Details Distributed reservoir sampling for web applications Distributed reservoir sampling for web applications

2007-12-11

2007-12-11

Leroux, Etienne (Department: 2161)

Data processing: database and file management or data structures

Database design

Data structure types

Reexamination Certificate

active

11212301

ABSTRACT:
Random samples without replacement are extracted from a distributed set of items by leveraging techniques for aggregating sampled subsets of the distributed set. This provides a uniform random sample without replacement representative of the distributed set, allowing statistical information to be gleaned from extremely large sets of distributed information. Subset random samples without replacement are extracted from independent subsets of the distributed set of items. The subset random samples are then aggregated to provide a uniform random sample without replacement of a fixed size that is representative of a distributed set of items of unknown size. In one instance, a multivariate hyper-geometric distribution is sampled by breaking up the multivariate hyper-geometric distribution into a set of univariate hyper-geometric distributions. Individual items of a uniform random sample without replacement are then determined utilizing a normal approximation of the univariate hyper-geometric distributions and a finite population correction factor.

REFERENCES:
patent: 6374297 (2002-04-01), Wolf et al.
patent: 7269157 (2007-09-01), Klinker et al.
patent: 2005/0149940 (2005-07-01), Calinescu et al.
C. Jermaine, et al., “Online Maintenance Of Very Large Random Samples”, in SIGMOD Conference, 2004, pp. 299-310.
V. Kachitvichyanukul, et al., “Sampling From The Hypergeometric Distribution”, ACM Transactions on Mathematical Software, Dec. 1988, 14(4):397-398.
J. S. Vitter, “Random Sampling With A Reservoir. ACM Transactions on Mathematical Software”, Mar. 1985, 11(1):37-57.
A. McLeod, et al., “A Convenient Algorithm For Drawing A Simple Random Sample. Applied Statistics”, 1983, 32(2):182-184.
J. Pitman, “Probability”, Springer-Verlag, New York, 1997.
D. E. Knuth, “The Art Of Computer Programming: vol. 2, Seminumerical Algorithms. Addison-Wesley”, 1981. Third Edition.

Affiliated with

Also associated with

Rating

Distributed reservoir sampling for web applications does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Distributed reservoir sampling for web applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed reservoir sampling for web applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3868519