Continuous sampling from distributed streams

Abstract

A fundamental problem in data management is to draw and maintain a sample of a large data set, for approximate query answering, selectivity estimation, and query planning. With large, streaming data sets, this problem becomes particularly difficult when the data is shared across multiple distributed sites. The main challenge is to ensure that a sample is drawn uniformly across the union of the data while minimizing the communication needed to run the protocol on the evolving data. At the same time, it is also necessary to make the protocol lightweight, by keeping the space and time costs low for each participant. In this article, we present communication-efficient protocols for continuously maintaining a sample (both with and without replacement) from k distributed streams. These apply to the case when we want a sample from the full streams, and to the sliding window cases of only the W most recent elements, or arrivals within the last w time units. We show that our protocols are optimal (up to logarithmic factors), not just in terms of the communication used, but also the time and space costs for each participant.

References

1. Arackaparambil, C., Brody, J., and Chakrabarti, A. 2009. Functional monitoring without monotonicity. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP).
2. Babcock, B., Datar, M., and Motwani, R. 2002. Sampling from a moving window over streaming data. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 633--634.
3. Babcock, B. and Olston, C. 2003. Distributed top-k monitoring. In Proceedings of the ACM SIGMOD International Conference on Management of Data.
4. Braverman, V., Ostrovsky, R., and Zaniolo, C. 2009. Optimal sampling from sliding windows. In Proceedings of the ACM Principles of Database Systems.
5. Chazelle, B. 2000. The Discrepancy Method. Cambridge University Press.
6. Cormode, G. and Garofalakis, M. 2005. Sketching streams through the net: Distributed approximate query tracking. In Proceedings of the International Conference on Very Large Data Bases.
7. Cormode, G., Garofalakis, M., Muthukrishnan, S., and Rastogi, R. 2005. Holistic aggregates in a networked world: Distributed tracking of approximate quantiles. In Proceedings of the ACM SIGMOD International Conference on Management of Data.
8. Cormode, G., Muthukrishnan, S., and Yi, K. 2008. Algorithms for distributed, functional monitoring. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.
9. Cormode, G., Muthukrishnan, S., and Zhuang, W. 2006. What's different: Distributed, continuous monitoring of duplicate resilient aggregates on data streams. In Proceedings of the IEEE International Conference on Data Engineering.
10. Duffield, N., Lund, C., and Thorup, M. 2003. Estimating flow distributions from sampled flow statistics. In Proceedings of ACM SIGCOMM.
11. Efraimidis, P. S. and Spirakis, P. G. 2006. Weighted random sampling with a reservoir. Inf. Process. Lett. 97, 181--185.
12. Frahling, G., Indyk, P., and Sohler, C. 2005. Sampling in dynamic data streams and applications. In Proceedings of the Symposium on Computational Geometry.
13. Gemulla, R. and Lehner, W. 2008. Sampling time-based sliding windows in bounded space. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 379--392.
14. Gemulla, R., Lehner, W., and Haas, P. J. 2007. Maintaining Bernoulli samples over evolving multisets. In Proceedings of the ACM Principles of Database Systems. 93--102.
15. Gemulla, R., Lehner, W., and Haas, P. J. 2008. Maintaining bounded-size sample synopses of evolving datasets. VLDB J. 17, 2, 173--202.
16. Gibbons, P. 2001. Distinct sampling for highly-accurate answers to distinct values queries and event reports. In Proceedings of the International Conference on Very Large Data Bases. 541--550.
17. Gibbons, P. and Matias, Y. 1998. New sampling-based summary statistics for improving approximate query answers. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 331--342.
18. Greenwald, M. and Khanna, S. 2001. Space-efficient online computation of quantile summaries. In Proceedings of the ACM SIGMOD International Conference on Management of Data.
19. Haussler, D. and Welzl, E. 1987. Epsilon-nets and simplex range queries. Disc. Computat. Geom. 2, 127--151.
20. Huang, L., Nguyen, X., Garofalakis, M., Hellerstein, J., Joseph, A. D., Jordan, M., and Taft, N. 2007. Communication-efficient online detection of network-wide anomalies. In Proceedings of the IEEE INFOCOMM.
21. Keralapura, R., Cormode, G., and Ramamirtham, J. 2006. Communication-efficient distributed monitoring of thresholded counts. In Proceedings of the ACM SIGMOD International Conference on Management of Data.
22. Knuth, D. E. 1998. The Art of Computer Programming, Vol. 2, Seminumerical Algorithms 2nd Ed. Addison-Wesley.
23. Manjhi, A., Shkapenyuk, V., Dhamdhere, K., and Olston, C. 2005. Finding (recently) frequent items in distributed data streams. In Proceedings of the IEEE International Conference on Data Engineering. 767--778.
24. Metwally, A., Agrawal, D., and Abbadi, A. E. 2006. An integrated efficient solution for computing frequent and top-k elements in data streams. ACM Trans. Datab. Syst. 31, 3, 1095--1133.
25. Muthukrishnan, S. 2003. Data streams: Algorithms and applications. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.
26. Muthukrishnan, S. 2009. Stochastic data streams. In Proceedings of the Symposium on Mathematical Foundations of Computer Science.
27. Olken, F. 1997. Random sampling from databases. Ph.D. thesis, Berkeley.
28. Sharfman, I., Schuster, A., and Keren, D. 2006. A geometric approach to monitoring threshold functions over distributed data streams. In Proceedings of the ACM SIGMOD International Conference on Management of Data.
29. Sharfman, I., Schuster, A., and Keren, D. 2010. Shape sensitive geometric monitoring. In Proceedings of the Symposium on ACM Principles of Database Systems.
30. Vapnik, V. N. and Chervonenkis, A. Y. 1971. On the uniform convergence of relative frequencies of events to their probabilities. Theory Prob. Appl. 16, 264--280.
31. Vitter, J. S. 1985. Random sampling with a reservoir. ACM Trans. Math. Softw. 11, 1, 37--57.
32. Yi, K. and Zhang, Q. 2009. Optimal tracking of distributed heavy hitters and quantiles. In Proceedings of the Symposium on ACM Principles of Database Systems. 167--174.

Index Terms

• Information systems

  • Data management systems

    • Database management system engines

      • Parallel and distributed DBMSs

• Theory of computation

  • Design and analysis of algorithms