SKIP: an efficient search mechanism in unstructured P2P networks

doi:10.1016/S1005-8885(09)60509-4

中国邮电高校学报(英文) ›› 2010, Vol. 17 ›› Issue (5): 64-71.doi: 10.1016/S1005-8885(09)60509-4

SKIP: an efficient search mechanism in unstructured P2P networks

申文武¹,双锴³,苏森²,杨放春²

1. 北京邮电大学网络技术研究院国家重点实验室交换与智能控制技术中心
2. 北京邮电大学网络与交换技术国家重点实验室
3. 北京邮电大学

收稿日期:2010-01-29 修回日期:2010-05-17 出版日期:2010-10-30 发布日期:2010-10-31
通讯作者: 申文武 E-mail:sky3290@gmail.com

SKIP: an efficient search mechanism in unstructured P2P networks

State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China

Received:2010-01-29 Revised:2010-05-17 Online:2010-10-30 Published:2010-10-31

摘要/Abstract

摘要：

Search efficiency and accuracy of resource are important considerations for search algorithm in peer-to-peer (P2P) network. Most search algorithms use flooding among neighbor nodes to search relevant resource. However, this usually causes great amount of redundant messages, which results in high search costs and low search precision. In this paper, we use vector space model (VSM) and relevance ranking algorithms to construct overlay network, and a novel search mechanism search with K-iteration preference (SKIP) based on semantic group for P2P networks is proposed to efficiently solve these problems. The key idea of SKIP is to reorder the semantic neighbors of nodes according to relevant scores and to utilize preference selection during the process of query. We analysis and implement the scheme and reveal that the SKIP provides a low overhead on topology maintenance, which can be effectively used in P2P searching and verify it outperformance in higher precision and lower search cost by comparing with current semantic-based searching mechanism gnutella-like efficient searching system (GES).

关键词:

K-iteration, preference, SKIP, P2P networks

Abstract:

Key words:

K-iteration, preference, SKIP, P2P networks

参考文献

1. Risson J, Moors T. Survey of research towards robust peer-to-peer networks: search methods. Computer Networks, 2006, 50(17): 3485-3521

2. Yang B, Garcia-Molina H. Improving search in peer-to-peer networks. Proceedings of the 22nd International Conference on Distributed Computing Systems (ICDCS’02), Jul 2-5, 2002, Vienna, Austria. Piscataway, NJ, USA: IEEE, 2002: 5-14

3. Lü Q, Cao P, Cohen E. Search and replication in unstructured peer-to-peer networks. Proceedings of the 16th International Conference on Supercomputing (ICS’02), Jun 22-26, New York, NY, USA. New York, NY, USA: ACM, 2002: 84-95

4. Cohen E, Kaplan H, Fiat A. Associative search in peer to peer networks: Harnessing latent semantics. Proceedings of the IEEE 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’03): Vol 2, Mar 30-Apr 3, 2003, San Francisco, CA, USA. Piscataway, NJ, USA: IEEE, 2003: 1261-1271

5. Spripanidkulchai K, Maggs B, Zhang H. Efficient content location using Interest-based locality in peer-to-peer systems. Proceedings of the IEEE 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’03): Vol 3, Mar 30-Apr 3, 2003, San Francisco, CA, USA. Piscataway, NJ, USA: IEEE, 2003: 2166-2176

6. Bawa M, Manku G, Raghavan P. SETS: Search enhanced by topic segmentation. Proceedings of the Annual ACM Conference on Research and Development in Information Retrieval (SIGIR’03), Jul 28-Aug 1, 2003, Toronto, Canada. New York, NY, USA: ACM, 2003: 306-313.

7. Ratnasamy S, Francis P, Handley M, et al. A scalable content addressable network. Proceedings of the International Conference of the Special Interest Group on Data Communication (SIGCOMM’01), Aug 27-31, 2001, San Diego, CA, USA. New York , NY, USA: ACM, 2001: 161-172

8. Rowstron A, Druschel P. Pastry: scalable, distributed object location and routing for large-scale peer-to-peer systems. Proceedings of the 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware’01), Nov 12-16, 2001, Heidelberg, Germany. LNCS 2218. Berlin, Germany: Springer-Verlag, 2001: 329-350

9. Stoica I, Morris R, Karger D, et al. Chord: a scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Transactions on Networking, 2003, 11(1): 17–32

10. Crespo A, Garcia-Molina H. Routing indices for peer-to-peer systems. Proceedings of the 22nd International Conference on Distributed Computing Systems (ICDCS’02), Jul 2-5, 2002, Vienna, Austria. Piscataway, NJ, USA: IEEE, 2002: 23-30

11. Berry M. W, Drmac Z, Jessup E. R. Matrices, vector spaces, and information retrieval. SIAM Review, 1999, 41(2): 335-362

12. Zhu Y, Hu Y. Enhancing search performance on Gnutella-like P2P systems. IEEE Transactions on Parallel and Distributed Systems, 2006, 17(12): 1482-1495

13. Huang J, Li X, Wu J. A Class-based search system in unstructured P2P networks. Proceedings of the 21st International Conference on Advanced Information Networking and Applications (AINA’07), May 21-23, 2007, Niagara Falls, Canada. Piscataway, NJ, USA: IEEE, 2007: 76-83

14. Guo L, Jiang S, Xiao L, et al. Exploiting content localities for efficient search in P2P systems. Proceedings of the 18th International Symposium on Distributed Computing (DISC’04), Oct 4-8, 2004, Amsterdam, The Netherlands. LNCS 3274. Berlin, Germany: Springer-Verlag, 2004: 349-364

15. Guo L, Jiang S, Xiao L, et al. Fast and low cost search schemes by exploiting localities in P2P networks. Journal of Parallel and Distributed Computing, 2005, 65(6): 729-742

16. Crespo A, Garcia-Molina H. Semantic overlay networks for P2P systems. Technical Report. Stanford, CA, USA: University of Stanford, 2004

SKIP: an efficient search mechanism in unstructured P2P networks

SKIP: an efficient search mechanism in unstructured P2P networks

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价