Querying structured data in an unstructured P2P system

ABSTRACT

Peer-to-Peer networking has become a major research topic over the last few years. Sharing of structured data in such decentralized environments is a challenging problem, especially in the absence of a global schema. The standard practice of answering a query that is consecutively rewritten along the propagation path often results in significant loss of information. In this paper, we present an adaptive and bandwidth-efficient solution to the problem in the context of an unstructured, purely decentralized system. Our method allows peers to individually choose which rewritten version of a query to answer and discover information-rich sources left hidden otherwise. Utilizing normal query traffic only, we describe how efficient query routing and clustering of peers can be used to produce high quality answers. Simulation results show that our technique is both effective and bandwidth-efficient in a variety of workloads and network sizes.

REFERENCES

• 1: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, ACM SIGCOMM Computer Communication Review, v.31 n.4, p.161-172, October 2001
• 2: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 3: V. Kantere, I. Kiringa, J. Mylopoulos, A. Kementsientidis, and M. Arenas. Coordinating P2P Databases Using ECA Rules. In DBISP2P, 2003.
• 4: A. Halevy, Z. Ives, D. Suciu, and I. Tatarinov. Schema Mediation in Peer Data Management Systems. In ICDE, 2003.
• 5: Anastasios Kementsietsidis , Marcelo Arenas , Renée J. Miller, Mapping data in peer-to-peer systems: semantics and algorithmic issues, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872798]
• 6: Erhard Rahm , Philip A. Bernstein, A survey of approaches to automatic schema matching, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.334-350, December 2001 [doi>10.1007/s007780100057]
• 7: B. Ooi, Y. Shu, K.L. Tan, and A.Y. Zhou. PeerDB: A P2P-based System for Distributed Data Sharing. In ICDE, 2003.
• 8: Alberto Medina , Anukool Lakhina , Ibrahim Matta , John Byers, BRITE: An Approach to Universal Topology Generation, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'01), p.346, August 15-18, 2001
• 9: C. Jin, Q. Chen, and S. Jamin. Inet: Internet Topology Generator. Technical Report CSE-TR443-00, Department of EECS, University of Michigan, 2000.
• 10: Matei Ripeanu , Ian T. Foster, Mapping the Gnutella Network: Macroscopic Properties of Large-Scale Peer-to-Peer Systems, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.85-93, March 07-08, 2002
• 11: Gnutella website: http://gnutella.wego.com.
• 12: Igor Tatarinov , Alon Halevy, Efficient query reformulation in peer data management systems, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007629]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

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

General Terms:
Algorithms

Keywords:
peer-to-peer, query reformulation, structured data