Variance-optimal sampling-based estimation of subset sums Patent uri icon


  • 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 nth item i is received. It is determined whether the nth item i should be included in sample S. If the nth item 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 nth item i. The determination is implemented thereby updating weights of items i in sample S. The method is repeated until no more items are received.

author list (cited authors)

  • Duffield, N., Lund, C., Thorup, M., Cohen, E., & Kaplan, H.

complete list of authors

  • Duffield, N||Lund, C||Thorup, M||Cohen, E||Kaplan, H

publication date

  • June 2010