Distributed classification in peer-to-peer networks

ABSTRACT

This work studies the problem of distributed classification in peer-to-peer(P2P) networks. While there has been a significant amount of work in distributed classification, most of existing algorithms are not designed for P2P networks. Indeed, as server-less and router-less systems, P2P networks impose several challenges for distributed classification: (1) it is not practical to have global synchronization in large-scale P2P networks; (2)there are frequent topology changes caused by frequent failure and recovery of peers; and (3) there are frequent on-the-fly data updates on each peer.

In this paper, we propose an ensemble paradigm for distributed classification in P2P networks. Under this paradigm, each peer builds its local classifiers on the local data and the results from all local classifiers are then combined by plurality voting. To build local classifiers, we adopt the learning algorithm of pasting bites to generate multiple local classifierson each peer based on the local data. To combine local results, we propose a general form of Distributed Plurality Voting (DPV) protocol in dynamic P2P networks. This protocol keeps the single-site validity for dynamic networks, and supports the computing modes of both one-shot query and continuous monitoring. We theoretically prove that the condition (BOB CHECK THIS 'C')ω₀ for sending messages used in DPV₀ is locally communication-optimal to achieve the above properties. Finally, experimental results on real-world P2P networks show that: (1) the proposed ensemble paradigm is effective even if there are thousands of local classifiers; (2) in most cases, the DPV₀ algorithm is local in the sense that voting is processed using information gathered from a very small vicinity, whose size is independent of the network size; (3) DPV₀ is significantly more communication-efficient than existing algorithms for distributed plurality voting.

REFERENCES

• 1: Shoukat Ali , Howard Jay Siegel , Muthucumaru Maheswaran , Sahra Ali , Debra Hensgen, Task Execution Time Modeling for Heterogeneous Computing Systems, Proceedings of the 9th Heterogeneous Computing Workshop, p.185, May 01-01, 2000
• 2: A.-L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286(5439):509--512, 1999.
• 3: Mayank Bawa , Aristides Gionis , Hector Garcia-Molina , Rajeev Motwani, The price of validity in dynamic networks, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007627]
• 4: Joel Branch , Boleslaw Szymanski , Chris Giannella , Ran Wolff , Hillol Kargupta, In-Network Outlier Detection in Wireless Sensor Networks, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.51, July 04-07, 2006 [doi>10.1109/ICDCS.2006.49]
• 5: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 6: Leo Breiman, Pasting Small Votes for Classification in Large Databases and On-Line, Machine Learning, v.36 n.1-2, p.85-103, July-August 1999 [doi>10.1023/A:1007563306331]
• 7: P. Chan and S. Stolfo. A comparative evaluation of voting and meta-learning on partitioned data. In ICML, pages 90--98, 1995.
• 8: Nitesh V. Chawla , Lawrence O. Hall , Kevin W. Bowyer , W. Philip Kegelmeyer, Learning Ensembles from Bites: A Scalable and Accurate Approach, The Journal of Machine Learning Research, 5, p.421-451, 12/1/2004
• 9: Souptik Datta , Kanishka Bhaduri , Chris Giannella , Ran Wolff , Hillol Kargupta, Distributed Data Mining in Peer-to-Peer Networks, IEEE Internet Computing, v.10 n.4, p.18-26, July 2006 [doi>10.1109/MIC.2006.74]
• 10: S. Datta, C. Giannella, and H. Kargupta. K-means clustering over a large, dynamic network. In SDM, pages 153--164, 2006.
• 11: Saso Džeroski , Bernard Ženko, Is Combining Classifiers with Stacking Better than Selecting the Best One?, Machine Learning, v.54 n.3, p.255-273, March 2004 [doi>10.1023/B:MACH.0000015881.36452.6e]
• 12: M. Demrekler and H. Altincay. Plurality voting-based multiple classifier systems: statistically independent with respect to dependent classifier sets. Pattern Recognition, 35(11):2365--2379, 2002.
• 13: Janez Demšar, Statistical Comparisons of Classifiers over Multiple Data Sets, The Journal of Machine Learning Research, 7, p.1-30, 12/1/2006
• 14: Y. Freund and R. E. Schapire. Experiments with a new boosting algorithm. In ICML, pages 148--156, 1996.
• 15: Aleksandar Lazarevic , Zoran Obradovic, The distributed boosting algorithm, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.311-316, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502557]
• 16: Xiaofan Lin , Sherif Yacoub , John Burns , Steven Simske, Performance analysis of pattern classifier combination by plurality voting, Pattern Recognition Letters, v.24 n.12, p.1959-1969, August 2003 [doi>10.1016/S0167-8655(03)00035-7]
• 17: Mortada Mehyar , Demetri Spanos , John Pongsajapan , Steven H. Low , Richard M. Murray, Asynchronous distributed averaging on communication networks, IEEE/ACM Transactions on Networking (TON), v.15 n.3, p.512-520, June 2007 [doi>10.1109/TNET.2007.893226]
• 18: Christopher J. Merz, Using Correspondence Analysis to Combine Classifiers, Machine Learning, v.36 n.1-2, p.33-58, July-August 1999 [doi>10.1023/A:1007559205422]
• 19: Márk Jelasity , Alberto Montresor , Ozalp Babaoglu, Gossip-based aggregation in large dynamic networks, ACM Transactions on Computer Systems (TOCS), v.23 n.3, p.219-252, August 2005 [doi>10.1145/1082469.1082470]
• 20: S. Siersdorfer and S. Sizov. Automatic document organization in a p2p environment. In ECIR, pages 265--276, 2006.
• 21: Ljupčo Todorovski , Sašo Džeroski, Combining Classifiers with Meta Decision Trees, Machine Learning, v.50 n.3, p.223-249, March 2003 [doi>10.1023/A:1021709817809]
• 22: G. Tsoumakas and I. Vlahavas. Effective stacking of distributed classifiers. In Proc. of the 15th European Conf. on AI, pages 340--344, 2002.
• 23: D. Watts and S. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393(6684):440--442, 1998.
• 24: R. Wolff, K. Bhaduri, and H. Kargupta. Local l2 thresholding based data mining in peer-to-peer systems. In SDM, pages 430--441, 2006.
• 25: R. Wolff and A. Schuster. Association rule mining in peer-to-peer systems. IEEE Transactions on Systems, Man and Cybernetics - Part B, 34(6), 2004.
• 26: J. Zhao, R. Govindan, and D. Estrin. Computing aggregates for monitoring wireless sensor networks. In Proc. of the 1st IEEE Int'l Workshop on Sensor Network Protocols and Applications, 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Experimentation

Keywords:
P2P networks, distributed classification, distributed plurality voting