Shape sensitive geometric monitoring

ABSTRACT

A fundamental problem in distributed computation is the distributed evaluation of functions. The goal is to determine the value of a function over a set of distributed inputs, in a communication efficient manner. Specifically, we assume that each node holds a time varying input vector, and we are interested in determining, at any given time, whether the value of an arbitrary function on the average of these vectors crosses a predetermined threshold.

In this paper, we introduce a new method for monitoring distributed data, which we term shape sensitive geometric monitoring. It is based on a geometric interpretation of the problem, which enables to define local constraints on the data received at the nodes. It is guaranteed that as long as none of these constraints has been violated, the value of the function does not cross the threshold. We generalize previous work on geometric monitoring, and solve two problems which seriously hampered its performance: as opposed to the constraints used so far, which depend only on the current values of the local input vectors, here we incorporate their temporal behavior into the constraints. Also, the new constraints are tailored to the geometric properties of the specific function which is being monitored, while the previous constraints were generic.

Experimental results on real world data reveal that using the new geometric constraints reduces communication by up to three orders of magnitude in comparison to existing approaches, and considerably narrows the gap between existing results and a newly defined lower bound on the communication complexity.

REFERENCES

• 1: Shipra Agrawal, Supratim Deb, K. V. M. Naidu, and Rajeev Rastogi. Efficient detection of distributed constraint violations. In ICDE '07, pages 1320--1324.
• 2: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 3: Arvind Arasu , Gurmeet Singh Manku, Approximate counts and quantiles over sliding windows, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055598]
• 4: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 5: Brian Babcock , Chris Olston, Distributed top-k monitoring, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872764]
• 6: Don Carney , Uǧur Çetintemel , Mitch Cherniack , Christian Convey , Sangdon Lee , Greg Seidman , Michael Stonebraker , Nesime Tatbul , Stan Zdonik, Monitoring streams: a new class of data management applications, Proceedings of the 28th international conference on Very Large Data Bases, p.215-226, August 20-23, 2002, Hong Kong, China
• 7: Amit Chakrabarti , Graham Cormode , Andrew McGregor, A near-optimal algorithm for computing the entropy of a stream, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.328-335, January 07-09, 2007, New Orleans, Louisiana
• 8: Moses Charikar , Kevin Chen , Martin Farach-Colton, Finding Frequent Items in Data Streams, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.693-703, July 08-13, 2002
• 9: Edith Cohen , Martin J. Strauss, Maintaining time-decaying stream aggregates, Journal of Algorithms, v.59 n.1, p.19-36, April 2006 [doi>10.1016/j.jalgor.2005.01.006]
• 10: Ram Keralapura , Graham Cormode , Jeyashankher Ramamirtham, Communication-efficient distributed monitoring of thresholded counts, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142507]
• 11: Graham Cormode , Minos Garofalakis, Sketching streams through the net: distributed approximate query tracking, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 12: Graham Cormode , Minos Garofalakis , S. Muthukrishnan , Rajeev Rastogi, Holistic aggregates in a networked world: distributed tracking of approximate quantiles, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066161]
• 13: Graham Cormode, S. Muthukrishnan, and Wei Zhuang. Conquering the divide: Continuous clustering of distributed data streams. In ICDE '07, pages 1036--1045.
• 14: Graham Cormode , S. Muthukrishnan , Wei Zhuang, What's Different: Distributed, Continuous Monitoring of Duplicate-Resilient Aggregates on Data Streams, Proceedings of the 22nd International Conference on Data Engineering, p.57, April 03-07, 2006 [doi>10.1109/ICDE.2006.173]
• 15: Abhinandan Das , Sumit Ganguly , Minos Garofalakis , Rajeev Rastogi, Distributed set-expression cardinality estimation, Proceedings of the Thirtieth international conference on Very large data bases, p.312-323, August 31-September 03, 2004, Toronto, Canada
• 16: Mayur Datar , Aristides Gionis , Piotr Indyk , Rajeev Motwani, Maintaining stream statistics over sliding windows: (extended abstract), Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.635-644, January 06-08, 2002, San Francisco, California
• 17: Mark Dilman and Danny Raz. Efficient reactive monitoring. In INFOCOM '01, pages 1012--1019.
• 18: Gereon Frahling , Piotr Indyk , Christian Sohler, Sampling in dynamic data streams and applications, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064116]
• 19: Ling Huang , Minos Garofalakis , Joseph Hellerstein , Anthony Joseph , Nina Taft, Toward sophisticated detection with distributed triggers, Proceedings of the 2006 SIGCOMM workshop on Mining network data, p.311-316, September 11-15, 2006, Pisa, Italy [doi>10.1145/1162678.1162684]
• 20: Ling Huang , Minos Garofalakis , Joseph Hellerstein , Anthony Joseph , Nina Taft, Toward sophisticated detection with distributed triggers, Proceedings of the 2006 SIGCOMM workshop on Mining network data, p.311-316, September 11-15, 2006, Pisa, Italy [doi>10.1145/1162678.1162684]
• 21: Ankur Jain, Joseph M. Hellerstein, Sylvia Ratnasamy, and David Wetherall. A wakeup call for internet monitoring systems: The case for distributed triggers. In Proc. 3rd ACM SIGCOMM Workshop on Hot Topics in Networks (HotNets), 2004.
• 22: David D. Lewis , Yiming Yang , Tony G. Rose , Fan Li, RCV1: A New Benchmark Collection for Text Categorization Research, The Journal of Machine Learning Research, 5, p.361-397, 12/1/2004
• 23: David D. Lewis , Yiming Yang , Tony G. Rose , Fan Li, RCV1: A New Benchmark Collection for Text Categorization Research, The Journal of Machine Learning Research, 5, p.361-397, 12/1/2004
• 24: 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]
• 25: Amit Manjhi , Vladislav Shkapenyuk , Kedar Dhamdhere , Christopher Olston, Finding (Recently) Frequent Items in Distributed Data Streams, Proceedings of the 21st International Conference on Data Engineering, p.767-778, April 05-08, 2005 [doi>10.1109/ICDE.2005.68]
• 26: Gurmeet Singh Manku , Rajeev Motwani, Approximate frequency counts over data streams, Proceedings of the 28th international conference on Very Large Data Bases, p.346-357, August 20-23, 2002, Hong Kong, China
• 27: Gurmeet Singh Manku , Rajeev Motwani, Approximate frequency counts over data streams, Proceedings of the 28th international conference on Very Large Data Bases, p.346-357, August 20-23, 2002, Hong Kong, China
• 28: P.A. Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical Programming, 96(2):293--320, 2003.
• 29: T.G. Rose, M. Stevenson, and M. Whitehead. The Reuters Corpus Volume 1 - from Yesterday's News to Tomorrow's Language Resources. In LREC '02, pages 827--832.
• 30: Izchak Sharfman , Assaf Schuster , Daniel Keren, A geometric approach to monitoring threshold functions over distributed data streams, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142508]
• 31: Yiming Yang , Jan O. Pedersen, A Comparative Study on Feature Selection in Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.412-420, July 08-12, 1997
• 32: Online Data Mining for Co-Evolving Time Sequences, Proceedings of the 16th International Conference on Data Engineering, p.13, February 28-March 03, 2000
• 33: Yonggang Jerry Zhao, Ramesh Govindan, and Deborah Estrin. Computing aggregates for monitoring wireless sensor networks. In SNPA 03.
• 34: Yunyue Zhu , Dennis Shasha, StatStream: statistical monitoring of thousands of data streams in real time, Proceedings of the 28th international conference on Very Large Data Bases, p.358-369, August 20-23, 2002, Hong Kong, China

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Performance

Keywords:
stream systems