Cooperative XPath caching

ABSTRACT

Motivated by the fact that XML is increasingly being used in distributed applications, we propose building a cooperative caching scheme for XML documents. Our scheme allows sharing cache content among a number of peers. To facilitate sharing, a distributed prefix-based index is built based on the queries whose results are cached. In the loosely-coupled sharing approach, each peer stores in its local cache results of its own queries and just publishes the associated queries to the index. In the tightly-coupled approach, each peer is assigned a specific part of the query space and stores in its local cache the results of the corresponding queries. Both approaches result in a dynamic organization of content that evolves over time based on the query load, the number of peers and the overall storage available. We present a number of associated design choices such as using a DHT for distributing the prefix-based index and a proactive cache replacement policy. We also report on a number of experiments that show the benefits of cooperative caching and highlight the pros and cons of loosely and tightly coupled cache sharing.

REFERENCES

• 1: Karl Aberer, P-Grid: A Self-Organizing Access Structure for P2P Information Systems, Proceedings of the 9th International Conference on Cooperative Information Systems, p.179-194, September 05-07, 2001
• 2: A. Aboulnaga, J. Naughton, and C. Zhang. Generating Synthetic Complex-Structured XML Data. In WebDB, 2001.
• 3: Sihem Amer-Yahia , Divesh Srivastava , Dan Suciu, Distributed Evaluation of Network Directory Queries, IEEE Transactions on Knowledge and Data Engineering, v.16 n.4, p.474-486, April 2004 [doi>10.1109/TKDE.2004.1269671]
• 4: Andrey Balmin , Fatma Özcan , Kevin S. Beyer , Roberta J. Cochrane , Hamid Pirahesh, A framework for using materialized XPath views in XML query processing, Proceedings of the Thirtieth international conference on Very large data bases, p.60-71, August 31-September 03, 2004, Toronto, Canada
• 5: Angela Bonifati , Ugo Matrangolo , Alfredo Cuzzocrea , Mayank Jain, XPath lookup queries in P2P networks, Proceedings of the 6th annual ACM international workshop on Web information and data management, November 12-13, 2004, Washington DC, USA [doi>10.1145/1031453.1031464]
• 6: Yatin Chawathe , Sriram Ramabhadran , Sylvia Ratnasamy , Anthony LaMarca , Scott Shenker , Joseph Hellerstein, A case study in building layered DHT applications, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 7: Li Chen , Song Wang , Elizabeth Cash , Burke Ryder , Ian Hobbs , Elke A. Rundensteiner, A fine-grained replacement strategy for XML query cache, Proceedings of the 4th international workshop on Web information and data management, November 08-08, 2002, McLean, Virginia, USA [doi>10.1145/584931.584947]
• 8: Shaul Dar , Michael J. Franklin , Björn Þór Jónsson , Divesh Srivastava , Michael Tan, Semantic Data Caching and Replacement, Proceedings of the 22th International Conference on Very Large Data Bases, p.330-341, September 03-06, 1996
• 9: Amol Deshpande , Suman Nath , Phillip B. Gibbons , Srinivasan Seshan, Cache-and-query for wide area sensor databases, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872818]
• 10: Leonidas Galanis , Yuan Wang , Shawn R. Jeffery , David J. DeWitt, Locating data sources in large distributed systems, Proceedings of the 29th international conference on Very large data bases, p.874-885, September 09-12, 2003, Berlin, Germany
• 11: Sitaram Iyer , Antony Rowstron , Peter Druschel, Squirrel: a decentralized peer-to-peer web cache, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571861]
• 12: H. V. Jagadish , Beng Chin Ooi , Quang Hieu Vu, BATON: a balanced tree structure for peer-to-peer networks, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 13: G. Koloniari and E. Pitoura. Content-Based Routing of Path Queries in Peer-to-Peer Systems. In EDBT, 2004.
• 14: Bhushan Mandhani , Dan Suciu, Query caching and view selection for XML databases, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 15: Gerome Miklau , Dan Suciu, Containment and equivalence for a fragment of XPath, Journal of the ACM (JACM), v.51 n.1, p.2-45, January 2004 [doi>10.1145/962446.962448]
• 16: Gleb Skobeltsyn , Karl Aberer, Distributed cache table: efficient query-driven processing of multi-term queries in P2P networks, Proceedings of the international workshop on Information retrieval in peer-to-peer networks, November 11-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183579.1183586]
• 17: G. Skobeltsyn, M. Hauswirth, and K. Aberer. Efficient Processing of XPath Queries with Structured Overlay Networks. In ODBASE, 2005.
• 18: 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
• 19: Liang Huai Yang , Mong Li Lee , Wynne Hsu, Efficient mining of XML query patterns for caching, Proceedings of the 29th international conference on Very large data bases, p.69-80, September 09-12, 2003, Berlin, Germany

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems; Performance evaluation (efficiency and effectiveness)

General Terms:
Performance

Keywords:
cache, peer-to-peer systems, xml