Schema-assisted peer selection for XML querying in unstructured P2P systems

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: Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, and S. Shenker. Making Gnutella-like P2P systems scalable. In Proceedings of SIGCOMM'03, 2003.
• 4: A. Crespo and H. Garcia-Molina. Routing indices for peer-to-peer systems. In Proceedings of ICDCS'02, 2002.
• 5: C. Doulkeridis, K. Nørvåg, and M. Vazirgiannis. Schema caching for improved XML query processing in P2P systems. In Proceedings of IEEE P2P'06, 2006.
• 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: V. Kalogeraki, D. Gunopoulos, and D. Zeinalipour-Yazti. A Local Search Mechanism for Peer-to-Peer Networks. In Proceedings of CIKM'02, 2002.
• 8: M. Karnstedt, K. Hose, and K.-U. Sattler. Query routing and processing in schema-based P2P systems. In Proceedings of DEXA workshops 2004, 2004.
• 9: G. Koloniari and E. Pitoura. Content based routing of path queries in peer-to-peer systems. In Proceedings of EDBT'04, 2004.
• 10: G. Koloniari and E. Pitoura. Peer-to-peer management of XML data: issues and research challenges. SIGMOD Rec., 34(2):6--17, 2005.
• 11: N. Koudas, M. Rabinovich, D. Srivastava, and T. Yu. Routing XML queries. In Proceedings of ICDE'04, 2004.
• 12: Q. Lv, P. Cao, E. Cohen, K. Li and S. Shenker. Search and Replication in Unstructured Peer-to-Peer Networks. In Proceedings of ICS'02, 2002.
• 13: D. A. Menascé and L. Kanchanapalli. Probabilistic scalable P2P resource location services. SIGMETRICS Performance Evaluation Review, 30(2):48--58, 2002.
• 14: K. Nørvåg, C. Doulkeridis, and M. Vazirgiannis. Taxonomy caching: A scalable low-cost mechanism for indexing remote contents in peer-to-peer systems. In Proceedings of IEEE ICPS'06, 2006.
• 15: V. N. Padmanabhan and L. Qiu. The content and access dynamics of a busy web site: findings and implications. In Proceedings of SIGCOMM'00, 2000.
• 16: S. Patro and Y. C. Hu. Transparent query caching in peer-to-peer overlay networks. In Proceedings of IPDPS'03, 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: G. Skobeltsyn and K. Aberer. Distributed Cache Table: Efficient query-driven processing of multi-term queries in P2P networks. In Proceedings of P2PIR'06, 2006.
• 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: D. Tsoumakos and N. Roussopoulos. Adaptive Probabilistic Search for Peer-to-Peer Networks. In Proceedings of IEEE P2P'03, 2003.
• 21: C. Wang, L. Xiao, Y. Liu, and P. Zheng. DiCAS: an efficient distributed caching mechanism for p2p systems. IEEE Transactions on Parallel and Distributed Systems, 17(10):1097--1109, 2006.
• 22: B. Yang and H. Garcia-Molina. Improving search in peer-to-peer networks. In Proceedings of ICDCS'02, 2002.