XPath lookup queries in P2P networks

ABSTRACT

We address the problem of querying XML data over a P2P network. In P2P networks, the allowed kinds of queries are usually exact-match queries over file names. We discuss the extensions needed to deal with XML data and XPath queries. A single peer can hold a whole document or a partial/complete fragment of the latter. Each XML fragment/document is identified by a distinct path expression, which is encoded in a distributed hash table. Our framework differs from content-based routing mechanisms, biased towards finding the most relevant peers holding the data. We perform fragments placement and enable fragments lookup by solely exploiting few path expressions stored on each peer. By taking advantage of quasi-zero replication of global catalogs, our system supports fast full and partial XPath querying. To this purpose, we have extended the Chord simulator and performed an experimental evaluation of our approach.

REFERENCES

• 1: Serge Abiteboul , Angela Bonifati , Grégory Cobéna , Ioana Manolescu , Tova Milo, Dynamic XML documents with distribution and replication, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872821]
• 2: Sihem Amer-Yahia , SungRan Cho , Laks V. S. Lakshmanan , Divesh Srivastava, Minimization of tree pattern queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.497-508, May 21-24, 2001, Santa Barbara, California, United States
• 3: Sihem Amer-Yahia , Laks V. S. Lakshmanan , Shashank Pandit, FleXPath: flexible structure and full-text querying for XML, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007581]
• 4: J.-M. Bremer and M. Gertz. On Distributing XML Repositories. In Proc. of WebDB, 2003.
• 5: A. Broder. Some Applications of Rabin's Fingerprinting Method. Springer-Verlag, 1993.
• 6: Andrei Z. Broder , Marc Najork , Janet L. Wiener, Efficient URL caching for world wide web crawling, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775247]
• 7: Emma Brunskill, Building Peer-to-Peer Systems with Chord, a Distributed Lookup Service, Proceedings of the Eighth Workshop on Hot Topics in Operating Systems, p.81, May 20-22, 2001
• 8: Adina Crainiceanu , Prakash Linga , Johannes Gehrke , Jayavel Shanmugasundaram, Querying peer-to-peer networks using P-trees, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France [doi>10.1145/1017074.1017082]
• 9: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 10: L. Galanis, Y. Wang, S. Jeffery, and D. DeWitt. Locating Data Sources in Large Distributed Systems. In Proc. of VLDB, 2003.
• 11: Gnutella homepage. http://www.gnutella.com/.
• 12: G. Gottlob, C. Koch, and R. Pichler. Efficient Algorithms for Processing XPath Queries. In Proc. of VLDB, pages 95--106, 2002.
• 13: S. D. Gribble, A. Y. Halevy, Z. G. Ives, M. Rodrig, and D. Suciu. What Can Database Do for Peer-to-Peer? In Proc. of WebDB, 2001.
• 14: A. Gupta, D. Agrawal, and A. E. Abbadi. Approximate Range Selection Queries in Peer-to-Peer Systems. In Proc. of CIDR, 2003.
• 15: R. Huebsch, J. M. Hellerstein, N. Lanham, B. T. Loo, S. Shenker, and I. Stoica. Querying the Internet with PIER. In Proc. of VLDB, 2003.
• 16: The Kazaa Homepage. http://www.kazaa.com.
• 17: 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]
• 18: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 19: G. Koloniari and E. Pitoura. Content-Based Routing of Path Queries in Peer-to-Peer Systems. In Proc. of EDBT, 2004.
• 20: Y. Li and C. Y. andH. V. Jagadish. Schema-Free XQuery. In Proc. of VLDB, 2004.
• 21: B. T. Loo, R. Huebsch, J. M. Hellerstein, I. Stoica, and S. Shenker. Enhancing P2P File-Sharing with an Internet-Scale Query Processor. In Proc. of VLDB (To appear), 2004.
• 22: M. Tamer Özsu , Patrick Valduriez, Principles of distributed database systems (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 23: M. Rabin. Fingerprinting by Random Polynomials. In CRCT TR-15-81, Harvard University, 1981.
• 24: C. Sartiani, P. Manghi, G. Ghelli, and G. Conforti. XPeer: A self-organizing XML P2P database system. In Proc. of P2PDB Workshop, co-held with EDBT, 2004.
• 25: A. Schmidt, F. Waas, M. Kersten, M. Carey, I. Manolescu, and R. Busse. XMark: A benchmark for XML data management. In Proc. of VLDB, 2002.
• 26: 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
• 27: Dan Suciu, Distributed query evaluation on semistructured data, ACM Transactions on Database Systems (TODS), v.27 n.1, p.1-62, March 2002 [doi>10.1145/507234.507235]
• 28: 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]
• 29: Website. Berkeley DB Data Store, 2003. http://www.sleepycat.com/pro-ducts/data.shtml.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design

Keywords:
P2P networks, XML querying, XPath, distributed XML indexes