Sampling from Dense Streams without Penalty

摘要: We investigate the ability to sample relatively small amounts of data from a stream and approximately calculate statistics on original stream. McGregor et al. [29] provide worst case theoretical bounds that show space costs for sampling are inversely correlated with rate. Indeed, while lower bound cannot be improved in general case, we it is possible improve D domain n, when average positive frequency μ = F 1/F 0 sufficiently large. consider following range parameters: ≥ log(n) rate p C k − 1log(n), where constant. On these streams \(\tilde{O} ({1 \over p} n^{1-2/k})\) \( \tilde{O} (n^{1-2/k})\) thus giving polynomial improvement large 1.