An Adaptive Method for Selecting Items from High Volume Streams
Arthur H. Becker, Steven J. Colombo · 2010
This paper describes two algorithms for sequential adaptive selectors. The objective of an adaptive selector is to optimize the selection of items from an incoming stream without knowing the statistical properties of the stream. The first algorithm assumes the statistical properties of the incoming stream are fixed, but unknown. The second considers the more realistic situation where the statistics of the incoming stream change over time. The algorithms are restricted to cases where items belong to a finite number of categories or classes, the value of items are binary (i.e. items are either "good" or "bad") and the resource constraints are such that only a fixed portion of items may be selected and examined. Both algorithms use a biased estimator for the unknown statistics of the input stream, which forces the selector to sample all classes while maintaining performance.