AMS-Sampling in Distributed Monitoring, with Applications to Entropy.

摘要: Modern data management systems often need to deal with massive, dynamic and inherently distributed sources: we collect the using a network, at same time try maintain global view of central coordinator. Such applications have been captured by monitoring model, which has attracted lot attention recently in both theory database communities. However, all proposed algorithms provable guarantees are ad-hoc nature, each being designed for specific problem. In this paper propose first generic algorithmic approach, adapting celebrated AMS-sampling framework from streaming model monitoring. We also show how use monitor entropy functions. Our results significantly improve previous best Arackaparambil et al. [2]