Event dissemination via group-aware stream filtering

ABSTRACT

We consider a distributed system that disseminates high-volume event streams to many simultaneous monitoring applications over a low-bandwidth network. For bandwidth efficiency, we propose a group-aware stream filtering approach, used together with multicasting, that exploits two overlooked, yet important, properties of monitoring applications: 1) many of them can tolerate some degree of "slack" in their data quality requirements, and 2) there may exist multiple subsets of the source data satisfying the quality needs of an application. We can thus choose the "best alternative" subset for each application to maximize the data overlap within the group to best benefit from multicasting. We provide a general framework that treats the group-aware stream filtering problem completely; we prove the problem NP-hard and thus provide a suite of heuristic algorithms that ensure data quality (specifically, granularity and timeliness) while preserving bandwidth. Our evaluation shows that group-aware stream filtering is effective in trading CPU time for bandwidth savings, compared with self-interested filtering.

REFERENCES

• 1: Suresh Aryangat , Henrique Andrade , Alan Sussman, Time and space optimization for processing groups of multi-dimensional scientific queries, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006224]
• 2: Brian Babcock , Mayur Datar , Rajeev Motwani, Sampling from a moving window over streaming data, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.633-634, January 06-08, 2002, San Francisco, California
• 3: Ziv Bar-Yossef , Ravi Kumar , D. Sivakumar, Sampling algorithms: lower bounds and applications, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.266-275, July 2001, Hersonissos, Greece [doi>10.1145/380752.380810]
• 4: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, On random sampling over joins, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.263-274, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 5: G. Chen, M. Li, and D. Kotz. Design and implementation of a large-scale context fusion network. In Proceedings of the First Annual International Conference on Mobile and Ubiquitous Systems (MobiQuitous), pages 246--255. ACM Press, 2004.
• 6: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
• 7: Reynold Cheng , Ben Kao , Sunil Prabhakar , Alan Kwan , Yicheng Tu, Adaptive stream filters for entity-based queries with non-value tolerance, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 8: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 9: Theodore Johnson , S. Muthukrishnan , Irina Rozenbaum, Sampling algorithms in a stream operator, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066159]
• 10: M. Li. Group-Aware Stream Filtering. PhD thesis, Dartmouth College Computer Science, Hanover, NH, May 2008. Available as Technical Report TR2008-621.
• 11: Samuel Madden , Mehul Shah , Joseph M. Hellerstein , Vijayshankar Raman, Continuously adaptive continuous queries over streams, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564698]
• 12: Don P. Mitchell, Consequences of stratified sampling in graphics, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.277-280, August 1996 [doi>10.1145/237170.237265]
• 13: Chris Olston , Jing Jiang , Jennifer Widom, Adaptive filters for continuous queries over distributed data streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872825]
• 14: R. Strom, G. Banavar, T. Chandra, M. Kaplan, K. Miller, B. Mukherjee, D. Sturman, and M. Ward. Gryphon: An information flow based approach to message brokering. In International Symposium on Software Reliability Engineering (ISSRE), 1998.
• 15: Yuanyuan Zhao , Rob Strom, Exploitng event stream interpretation in publish-subscribe systems, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.219-228, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384023]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

General Terms:
Design, Performance