Variance-optimal sampling-based estimation of subset sums

Details Variance-optimal sampling-based estimation of subset sums Variance-optimal sampling-based estimation of subset sums

2011-08-23

2011-08-23

Chankong, Dohm (Department: 2452)

Electrical computers and digital processing systems: multicomput

Computer network managing

Computer network monitoring

C709S223000, C370S232000, C702S179000, C702S182000

Reexamination Certificate

active

08005949

ABSTRACT:
The present invention relates to a method of obtaining a generic sample of an input stream. The method is designated as VAROPTk. The method comprises receiving an input stream of items arriving one at a time, and maintaining a sample S of items i. The sample S has a capacity for at most k items i. The sample S is filled with k items i. An nthitem i is received. It is determined whether the nthitem i should be included in sample S. If the nthitem i is included in sample S, then a previously included item i is dropped from sample S. The determination is made based on weights of items without distinguishing between previously included items i and the nthitem i. The determination is implemented thereby updating weights of items i in sample S. The method is repeated until no more items are received.

REFERENCES:
patent: 5721896 (1998-02-01), Ganguly et al.
patent: 5870752 (1999-02-01), Gibbons et al.
patent: 6012064 (2000-01-01), Gibbons et al.
patent: 7191181 (2007-03-01), Chaudhuri et al.
patent: 7193968 (2007-03-01), Kapoor et al.
patent: 7287020 (2007-10-01), Chaudhuri et al.
patent: 7293037 (2007-11-01), Chaudhuri et al.
patent: 7293086 (2007-11-01), Duffield et al.
patent: 7536396 (2009-05-01), Johnson et al.
patent: 2005/0131946 (2005-06-01), Korn et al.
patent: 2007/0016666 (2007-01-01), Duffield et al.
patent: 2007/0226188 (2007-09-01), Johnson et al.
patent: 2008/0259809 (2008-10-01), Stephan et al.
Duffield, N., Lund, C., and Thorup, M., “Priority sampling for estimation of arbitrary subset sums”, J. ACM 54, 6 (Dec. 2007).
Duffield, N., Lund, C., and Thorup, M., “Learn more, sample less: Control of volume and variance in network measurement”, IEEE Transactions in Information Theory 51, 5 (2005), 1756-1775.
Alon, N., Duffield, N., Lund, C., and Thorup, M., “Estimating arbitrary subset sums with few probes”, in Proceedings of the Twenty-Fourth ACM SIGMOD-SIGART-SIGART Symposium on Principles of Database Systems (Baltimore, Maryland, Jun. 13-15, 2005).
Johnson, T., Muthukrishnan, S., and Rozenbaum, I. “Sampling algorithms in a stream operator”, in Proceedings of the 2005 ACM SIGMOND international Conference on Management of Data (Jun. 2005).
Steiner, Ralph, “Learn More, Sample Less: Control of volume and Variance in Network Measurement,” May 30, 2008, accessed from: http://www.dbis.ethz.ch/education/ss2008/ss08—dbs—algodbs/SteinerTalk.pdf.
Cohen, “Size-Estimation Framework with Applications to Transitive Closure and Reachability,”Journal of Computer and System Sciences5:441-453, 1997.
Cohen et al., “Sketching Unaggregated Data Streams for Subpopulation-Size Queries,”Proc of the 2007 ACM Symp. On Principles of Database Systems, 2007.
Cohen et al., “Bottom-k Sketches: Better and More Efficient Estimation of Aggregates,”SIGMETRIC'07Jun. 12-16, San Diego, CA, USA, 2007.
Cohen et al., “Spatially-Decaying Aggregation Over a Network: Model and Algorithms,”SIGMOND 2004, Jun. 13-18, Paris, France, pp. 707-718, 2004.
Cohen et al., “Summarizing Data Using Bottom-k Sketches,”PODC'07Aug. 12-15, 2007 Portland, Oregon, USA, 2007.
Cranor et al., “Gigascope: A Stream Database for Network Applications,”SIGMOD2003, Jun. 9-12, San Diego, CA, pp. 647-651, 2003.
Estan et al., “Building a Better NetFlow,”SIGCOMM'04Aug. 30-Sep. 3, Portland, Oregon, USA, pp. 245-256, 2004.
Estan et al., “New Directions in Traffic Measurement and Accounting,”SIGCOMM'02, Aug. 19-23, 2002 Pittsburgh, PA, USA, pp. 323-336, 2002.
Gibbons et al., “New Sampling-Based Summary Statistics for Improving Approximate Query Answers,”SIGMOD'98, Seattle, WA, USA, pp. 331-342, 1998.
Hellerstein et al., “Online Aggregation,”SIGMOD'97AZ, USA, pp. 171-182, 1997.
Hohn et al., “Inverting Sampled Traffic,”IMC'03Oct. 27-29, Miami Beach, FL, USA, 2003.
Keys et al., “A Robust System for Accurate Real-time Summaries of Internet Traffic,”SIGMETRICS'05, Jun. 6-10, Banff, Alberta, Canada, pp. 85-96, 2005.
Kumar, et al., “A Data Streaming Algorithm for Estimating Subpopulation Flow Size Distribution,”SIGMETRICS'05, Jun. 6-10, Banff, Alberta, Canada, pp. 61-72, 2005.
Ramabhadran et al., “Efficient Implementation of a Statistics Counter Architecture,”SIGMETRICS'03, Jun. 10-14, San Diego, CA, USA, 2003.
Ribeiro, et al., “Fisher Information of Sampled Packets: an Application to Flow Size Estimation,”IMC'06, Oct. 25-27, Rio de Janeiro, Brazil, 2006.
Shah et al., “Maintaining Statistics Counters in Router Line Cards,” 2002 IEEE, pp. 76-81.
Szegedy et al., “On the Variance of Subset Sum Estimation,” ESA 2007, LNCS 4698, pp. 75-86. 2007.

Affiliated with

Also associated with

Rating

Variance-optimal sampling-based estimation of subset sums does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Variance-optimal sampling-based estimation of subset sums, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Variance-optimal sampling-based estimation of subset sums will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2638319