Monitoring data streams in a distributed system has attracted considerable interest in recent years. The task of feature selection (e.g., by monitoring the information gain of various features) requires a very high communication overhead when addressed using straightforward centralized algorithms. While most of the existing algorithms deal with monitoring simple aggregated values such as frequency of occurrence of stream items, motivated by recent contributions based on geometric ideas we present an alternative approach. The proposed approach enables monitoring values of an arbitrary threshold function over distributed data streams through stream dependent constraints applied separately on each stream. We report numerical experiments on a real-world data that detect instances where communication between nodes is required, and compare the approach and the results to those recently reported in the literature.
References
[1]
Madden, S.; Franklin, M.J. An Architecture for Queries Over Streaming Sensor Data. In Proceedings of the ICDE 02, San Jose, CA, 26 February–1 March 2002; pp. 555–556.
[2]
Dilman, M.; Raz, D. Efficient Reactive Monitoring. In Proceedings of the Twentieth Annual Joint Conference of the IEEE Computer and Communication Societies, Anchorage, Alaska, 2001; pp. 1012–1019.
[3]
Zhu, Y.; Shasha, D. Statestream: Statistical Monitoring of Thousands of Data Streamsin Real Time. In Proceeding of the 28th international conference on Very Large Data Bases (VLDB), Hong Kong, China, 2002; pp. 358–369.
[4]
Yi, B.-K.; Sidiropoulos, N.; Johnson, T.; Jagadish, H.V.; Faloutsos, C.; Biliris, A. Online Datamining for Co–Evolving Time Sequences. In Proceedings of ICDE 00IEEE Computer Society, San Diego, CA, 2000; pp. 13–22.
[5]
Manjhi, A.; Shkapenyuk, V.; Dhamdhere, K.; Olston, C. Finding (Recently) Frequent Items in Distributed Data Streams. In Proceedings of the 21st International Conference on Data Engineering (ICDE 05), Tokyo, Japan, 2005; pp. 767–778.
[6]
Wolff, R.; Bhaduri, K.; Kargupta, H. Local L2-Thresholding Based Data Mining in Peer-to-Peer Systems. In Proceedings of the SIAM International Conference on Data Mining (SDM 06), Bethesda, MD, USA, 2006; pp. 430–441.
[7]
Wolff, R.; Bhaduri, K.; Kargupta, H. A generic local algorithm with applications for data mining in large distributed systems. IEEE Trans. Knowl. Data Eng. 2009, 21, 465–478, doi:10.1109/TKDE.2008.169.
[8]
Sharfman, I.; Schuster, A.; Keren, D. A geometric approach to monitoring threshold functions over distributed data streams. ACM Trans. Database Syst. 2007, 23, 23–29.
[9]
Sharfman, I.; Schuster, A.; Keren, D. A Geometric Approach to Monitoring Threshold Functions over Distributed Data Streams. In Ubiquitous Knowledge Discovery; May, M., Saitta, L., Eds.; Springer–Verlag: New York, NY, USA, 2010; pp. 163–186.
[10]
Kogan, J. Feature Selection over Distributed Data Streams through Convex Optimization. In Proceedings of the Twelfth SIAM International Conference on Data Mining (SDM 2012), Anaheim, CA, USA, 2012; pp. 475–484.
Gray, R.M. Entropy and Information Theory; Springer–Verlag: New York, NY, USA, 1990; pp. 119–162.
[13]
Hinrichsen, D.; Pritchard, A.J. Real and Complex Stability Radii: A Survey. In Controlof Uncertain Systems; Hinrichsen, D., Pritchard, A.J., Eds.; Birkhauser: Boston, MA, USA, 1990; pp. 119–162.
[14]
Rudin, W. Principles of Mathematical Analysis; McGraw-Hill: New York, NY, USA, 1976.
[15]
Rockafellar, R.T. Convex Analysis; Princeton University Press: Princeton, NJ, USA, 1970.
[16]
Bottou, L. Home Page. Available online: leon.bottou.org/projects/sgd (accessed on 14 September 2012).
[17]
Mirkin, B. Clustering for Data Mining: A Data Recovery Approach; Chapman & Hall/CRC: Boca Raton, FL, USA, 2005.
