Estimating the range of a function in an online setting
Consider an unknown function L(.):{1,..., d}-->{1,..., r}with range R = {L(i)\i = 1,..., d}. Given d, r, epsilon, delta > 0 we show how to compute an estimate (p) over tilde such that with probability at least 1 - delta we have \\R\/r-(p) over tilde\ less than or equal to epsilon (p) over tilde. This is an estimate with a fixed relative error, which is stronger than finding an estimate with a fixed absolute error. This calculation can be performed efficiently in one pass through the domain of L (allowing the the method to be used in online situations) using only O(logr(loglogr + log 1/delta)/epsilon(2)) words of storage. The method is based on pairwise-independent pseudo-random variables. (C) 1999 Elsevier Science B.V. All rights reserved.
analysis of algorithms online algorithms pairwise independence pseudo-random generation randomized algorithms sampling