臺灣博碩士論文加值系統

Peer-to-Peer (P2P) networks are useful and have applied to many fields. In order to quickly retrieve resources on a P2P network, a hierarchical search engine based, on three proposals: NICE protocol, parallel crawler, and distributed PageRank, is proposed. In our method, tasks of document fetching and indexing are distributed to nodes, and these nodes are organized into a hierarchical architecture. Since documents and their indexes are stored locally among nodes, updates on these documents are relatively. In addition, executing queries using the hierarchy can improve search efficiency. Through simulations, we find that our method can perform better than centralized method and flooding method. Also, we can have acceptable precision rate. By adapting several distributed techniques, we can construct a search engine with easier maintenances and higher usability.

Peer-to-Peer (P2P) networks are useful and have applied to many fields. In order to quickly retrieve resources on a P2P network, a hierarchical search engine based, on three proposals: NICE protocol, parallel crawler, and distributed PageRank, is proposed. In our method, tasks of document fetching and indexing are distributed to nodes, and these nodes are organized into a hierarchical architecture. Since documents and their indexes are stored locally among nodes, updates on these documents are relatively. In addition, executing queries using the hierarchy can improve search efficiency. Through simulations, we find that our method can perform better than centralized method and flooding method. Also, we can have acceptable precision rate. By adapting several distributed techniques, we can construct a search engine with easier maintenances and higher usability.

1. INTRODUCTION 5
1.1 BACKGROUND 5
1.2 MOTIVATIONS 7
1.3 OBJECTIVE 8
2. RELATED WORK 9
2.1 PEER-TO-PEER SEARCHING 9
2.2 SEARCH ENGINE COMPONENTS 10
3. SYSTEM ARCHITECTURE 15
3.1 OVERVIEW 15
3.2 NOTATIONS 15
3.3 ARCHITECTURE 16
3.3.1 New Node Joins 17
3.3.2 Node Leaves 19
3.3.3 Cluster Maintenance 19
3.4 PROCESSING FUNCTIONS 21
3.4.1 Parallel Crawlers 21
3.4.2 Distributed PageRank 22
3.4.3 Indexing web pages 23
3.4.4 Query 24
4. EXPERIMENTS AND IMPROVEMENTS 26
4.1 RESPONSE TIME 26
4.1.1 Original Method 26
4.1.2 Improvement Method for Query 27
4.2 SIZE OF INDEXES 28
4.3 COMPARING PROCESSING TIME WITH OTHER METHODS 29
4.4 COMPARING QUEUE LENGTH WITH OTHER METHODS 30
4.5 PRECISION RATE 32
5. CONCLUSION 34
REFERENCES 35

[1] S. Banerjee, B. Bhattacharjee, and C. Kommareddy. Scalable application layer multicast. In Proceedings of ACM SIGCOMM, pp. 205-217, Aug. 2002.
[2] P. Boldi, B. Codenotti, M. Santini, and S. Vigna. Ubicrawler: Scalability and fault-tolerance issues. In Poster Proceedings of Eleventh International World Wide Web Conference, Honolulu, USA, 2002.
[3] S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems, pp. 107-117, April 1998.
[4] J. Cho, H. Garcia-Molina. Parallel Crawlers. In Proceedings of the 11th international conference on World Wide Web, pp. 124-135, 2002.
[5] I. Clarke, O. Sandberg, B. Wiley, T.W. Hong, Freenet: a distributed anonymous information storage and retrieval system, in Proceedings of the 2000 International Workshop on Design Issues in Anonymity and Unobservability, Volume 2009 of Lecture Notes in Computer Science, Springer-Verlag, pp. 46–66, 2001.
[6] D. de Jager. PageRank: Three Distributed Algorithms. Master's thesis, Imperial College of Science, Technology and Medicine, London, Sept. 2004.
[7] S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Shenker, A scalable content-addressable network, in: Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, ACM Press, pp. 161–172, 2001.
[8] A. Rowstron, P. Druschel, Pastry: scalable, decentralized object location and routing for large-scale peer-to-peer systems, in: Proceedings of the 2001 IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001), Volume 2218 of Lecture Notes in Computer Science, Springer-Verlag, pp. 329–350, 2001.
[9] K. Sankaralingam, S. Sethumadhavan, and J. C. Browne. Distributed Pagerank for P2P Systems. In Proceedings of the 12th International Symposium on High Performance Distributed Computing, pp. 58–68, June 2003.
[10] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In Proceedings of the 2001 conference on applications, technologies, architectures, and protocols for computer communications, pp. 149-160. ACM Press, 2001.
[11] C. Tang, Z. Xu, and M. Mahalingam. pSearch: Information retrieval in structured overlays. In ACM SIGCOMM Computer Communications Review, Volume 33, Number 1, pp. 89-94, Jan. 2003.
[12] Y. Yang, R. Dunlap, M. Rexroad, and B. F. Cooper. Performance of full text search in structured and unstructured peer-to-peer systems. In INFOCOM 2006, April 2006.
[13] K.-H. Yang, J.-M. Ho. Proof: A DHT-based Peer-to-Peer Search Engine. In Proceedings of the 2006 IEEE/WIC/ACM International Conference on Web Intelligence, 2006.
[14] BitTorrent Home Web Page. http://www.bittorrent.com/.
[15] Einstein@home Home Web Page. http://einstein.phys.uwm.edu/.
[16] eMule Project Home Web Page. http://www.emule-project.net/.
[17] Gnutella Home Web Page. http://www.gnutella.com/.
[18] JXTA Community Projects Home Web Page https://jxta.dev.java.net/.
[19] MG4J Home Web Page http://mg4j.dsi.unimi.it/.
[20] PPStream Home Web Page. http://www.ppstream.com/.
[21] SETI@home Home Web Page. http://setiathome.berkeley.edu/.
[22] Skype Home Web Page. http://www.skype.com/.