Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

XML is emerging as the de-facto standard for semistructured contents and metadata. Searching this content in mobile environments is challenging, since centralized approaches are not appropriate in a very dynamic environment with limited resources available for keeping a centralized index up-to-date. A more appropriate solution is to organize the mobile devices in an unstructured peer-to-peer (P2P) network. The main challenge in the context of unstructured P2P is to determine the peers that might store documents matching a query, i.e., peer selection. In this paper, we propose a summary caching method for increasing the efficiency and recall of peer selection during XML querying. Our approach is based on caching parts of XML schemas along the query path, to enable subsequent jumps to remote peers storing content relevant to the query. We evaluate the performance improvements of our search strategy in terms of completeness of the search and reduced latency. The results show that our approach can significantly enhance a naive query mechanism such as flooding, and consistently outperform a baseline path caching technique similar to techniques used in related work.

REFERENCES

• 1: B. Bhattacharjee, S. Chawathe, V. Gopalakrishnan, P. Keleher, and B. Silaghi. Efficient Peer-to-Peer Searches Using Result-caching. In Proceeding of IPTPS'03, 2003.
• 2: I. Brunkhorst, H. Dhraief, A. Kemper, W. Nejdl, and C. Wiesner. Distributed queries and query optimization in schema-based P2P-systems. In Proceedings of DBISP2P'03, 2003.
• 3: Yatin Chawathe , Sylvia Ratnasamy , Lee Breslau , Nick Lanham , Scott Shenker, Making gnutella-like P2P systems scalable, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.864000]
• 4: Arturo Crespo , Hector Garcia-Molina, Routing Indices For Peer-to-Peer Systems, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.23, July 02-05, 2002
• 5: Christos Doulkeridis , Kjetil Norvag , Michalis Vazirgiannis, Schema Caching for Improved XML Query Processing in P2P Systems, Proceedings of the Sixth IEEE International Conference on Peer-to-Peer Computing, p.73-74, September 06-June 08, 2006 [doi>10.1109/P2P.2006.35]
• 6: L. Galanis, Y. Wang, S. Jeffery, and D. DeWitt. Processing queries in a large peer-to-peer system. In Proceedings of CAISE'03, 2003.
• 7: Vana Kalogeraki , Dimitrios Gunopulos , D. Zeinalipour-Yazti, A local search mechanism for peer-to-peer networks, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584842]
• 8: Marcel Karnstedt , Katja Hose , Kai-Uwe Sattler, Query Routing and Processing in Schema-Based P2P Systems, Proceedings of the Database and Expert Systems Applications, 15th International Workshop, p.544-548, August 30-September 03, 2004 [doi>10.1109/DEXA.2004.135]
• 9: G. Koloniari and E. Pitoura. Content based routing of path queries in peer-to-peer systems. In Proceedings of EDBT'04, 2004.
• 10: Georgia Koloniari , Evaggelia Pitoura, Peer-to-peer management of XML data: issues and research challenges, ACM SIGMOD Record, v.34 n.2, June 2005 [doi>10.1145/1083784.1083788]
• 11: Nick Koudas , Michael Rabinovich , Divesh Srivastava , Ting Yu, Routing XML Queries, Proceedings of the 20th International Conference on Data Engineering, p.844, March 30-April 02, 2004
• 12: Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514206]
• 13: Daniel A. Menascé , Lavanya Kanchanapalli, Probabilistic scalable P2P resource location services, ACM SIGMETRICS Performance Evaluation Review, v.30 n.2, September 2002 [doi>10.1145/588160.588167]
• 14: Norvag , Doulkeridis , Vazirgiannis, Taxonomy Caching: A Scalable Low-Cost Mechanism for Indexing Remote Contents in Peer-to-Peer Systems, Proceedings of the 2006 ACS/IEEE International Conference on Pervasive Services, p.213-221, June 26-29, 2006 [doi>10.1109/PERSER.2006.1652227]
• 15: Venkata N. Padmanabhan , Lili Qiu, The content and access dynamics of a busy Web site: findings and implications, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.111-123, August 28-September 01, 2000, Stockholm, Sweden
• 16: Sunil Patro , Y. Charlie Hu, Transparent Query Caching in Peer-to-Peer Overlay Networks, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.32.1, April 22-26, 2003
• 17: C. Sartiani, P. Manghi, G. Ghelli, and G. Conforti. XPeer: A self-organizing XML P2P database system. In Proceedings of EDBT Workshops 2004, 2004.
• 18: 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]
• 19: K. Sripanidkulchai, B. Maggs, and H. Zhang. Efficient content location using interest-based locality in peer-to-peer systems. In Proceedings of INFOCOM'03, 2003.
• 20: Dimitrios Tsoumakos , Nick Roussopoulos, Adaptive Probabilistic Search for Peer-to-Peer Networks, Proceedings of the 3rd International Conference on Peer-to-Peer Computing, p.102, September 01-03, 2003
• 21: Chen Wang , Li Xiao , Yunhao Liu , Pei Zheng, DiCAS: An Efficient Distributed Caching Mechanism for P2P Systems, IEEE Transactions on Parallel and Distributed Systems, v.17 n.10, p.1097-1109, October 2006 [doi>10.1109/TPDS.2006.137]
• 22: Beverly Yang , Hector Garcia-Molina, Improving Search in Peer-to-Peer Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.5, July 02-05, 2002

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation

          Nouns: XML

General Terms:
Algorithms, Design, Management, Performance