Distributed classification in peer-to-peer networks

Ping Luo, Hui Xiong, Kevin Lü, Zhongzhi Shi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

63 Scopus citations

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') 0 for sending messages used in DPV 0 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 0 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 0 is significantly more communication-efficient than existing algorithms for distributed plurality voting.

Original languageEnglish (US)
Title of host publicationKDD-2007
Subtitle of host publicationProceedings of the Thirteenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Pages968-976
Number of pages9
DOIs
StatePublished - 2007
EventKDD-2007: 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - San Jose, CA, United States
Duration: Aug 12 2007Aug 15 2007

Publication series

NameProceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Other

OtherKDD-2007: 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Country/TerritoryUnited States
CitySan Jose, CA
Period8/12/078/15/07

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems

Keywords

  • Distributed classification
  • Distributed plurality voting
  • P2P networks

Fingerprint

Dive into the research topics of 'Distributed classification in peer-to-peer networks'. Together they form a unique fingerprint.

Cite this