오디세우스 대용량 검색 엔진을 위한 병렬 웹 크롤러의 구현 = Implementation of a Parallel Web Crawler for the Odysseus Large-Scale Search Engine

국문 초록 (Abstract)

웹의 크기가 폭발적으로 증가함에 따라 인터넷에서 정보를 얻는 수단으로서 검색 엔진의 중요성이 부각되고 있다. 검색 엔진은 사용자에게 최신의 정보를 검색 결과로서 제공하기 위해 웹 페이지를 주기적으로 수집하고 이를 데이타베이스에 저장한다. 웹 크롤러는 이러한 목적으로 웹 페이지를 수집하는 프로그램이다. 대부분의 검색 엔진은 제한된 시간 내에 많은 수의 웹 페이지를 수집하기 위해 다수의 머신을 사용하는 병렬 웹 크롤러를 이용한다. 그러나, 병렬 웹 크롤러의 아키텍처와 세부 구현 방법이 잘 알려져 있지 않기 때문에 실제로 병렬 웹 크롤러를 구현하는 데에 어려움이 많다.
본 논문에서는 병렬 웹 크롤러(parallel web crawler)의 아키텍처와 세부 구현 방법을 제시한다. 병렬웹 크롤러는 다수의 머신에서 웹 페이지를 병렬적으로 수집하기 위해 조정자(coordinator) 대리자(agent) 구조의 2-티어(tier) 모델을 사용한다. 조정자/대리자 모델은 각 머신에서 웹 페이지를 수집하기 위한 다수의 대리자들과 이 대리자들을 관리하기 위한 하나의 조정자로 구성된다. 병렬 웹 크롤러는 웹 페이지를 수집하기 위한 크롤링(crawling) 모듈, 수집한 웹 페이지를 데이타베이스 로딩 포맷으로 변환하기 위한 컨버팅(converting) 모듈, 수집된 웹 페이지의 중요도를 계산하기 위한 랭킹(ranking) 모듈로 구성된다. 본 논문에서는 병렬 웹 크롤러의 각 모듈들을 설명하고, 세부 구현 방법을 설명한다. 마지막으로, 실험을 통해 병렬 웹 크롤러의 성능을 평가하였다. 실험 결과, 제안된 병렬 웹 크롤러가 수집해야할 웹 페이지 개수와 머신 개수에 따라 확장 가능함을 보였다.

다국어 초록 (Multilingual Abstract)

As the size of the web is growing explosively, search engines are becoming increasingly important as the primary means to retrieve information from the Internet. A search engine periodically downloads web pages and stores them in the database to provide readers with up-to-date search results. The web crawler is a program that downloads and stores web pages for this purpose. A large-scale search engines uses a parallel web crawler to retrieve the collection of web pages maximizing the download rate. However, the service architecture or experimental analysis of parallel web crawlers has not been fully discussed in the literature.
In this paper, we propose an architecture of the parallel web crawler and discuss implementation issues in detail. The proposed parallel web crawler is based on the coordinator/agent model using multiple machines to download web pages in parallel. The coordinator/agent model consists of multiple agent machines to collect web pages and a single coordinator machine to manage them. The parallel web crawler consists of three components: a crawling module for collecting web pages, a converting module for transforming the web pages into a database-friendly format, a ranking module for rating web pages based on their relative importance. We explain each component of the parallel web crawler and implementation methods in detail. Finally, we conduct extensive experiments to analyze the effectiveness of the parallel web crawler. The experimental results clarify the merit of our architecture in that the proposed parallel web crawler is scalable to the number of web pages to crawl and the number of machines used.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구
• 3. 병렬 웹 크롤러의 설계
• 4. 병렬 웹 크롤러의 구현
• 5. 병렬 웹 크롤러의 성능 평가
• 6. 결론
• 참고문헌

참고문헌 (Reference)

• 1 김계정, "커뮤니티 제한 검색을 위한 웹 크롤링 및 PageRank 계산" 32 (32): 1-3, 2005
• 2 황규영, "오디세우스/IR: 정보 검색 기능과 밀결합된고성능 객체 관계형 DBMS" 한국정보과학회 11 (11): 209-215, 2005
• 3 신은정, "대용량 검색 엔진을 위한 병렬 웹 크롤러의 설계 및 구현" KAIST 2007
• 4 "Yahoo"
• 5 Jie Xu, "Towards a Content-Provider-Friendly Web Page Crawler" In Proc. 10th Int'l ACM Workshop on the Web and Databases 2007
• 6 Page, L, "The PageRank Citation Ranking: Bringing Order to the Web" Technical Report, Stanford University 1998
• 7 Cho,J, "Technical Report" Stanford WebBase Components and Applications, Technical Report, Stanford University 2004
• 8 "Secure Hash Standard"
• 9 Chau, H, "Parallel Crawling for Online Social Netw" In Proc. 16th Int'l Conf. on World Wide Web 1283-1284, 2007
• 10 Cho, J, "Parallel Crawlers" Technical Report, Stanford University 2001
• 11 "Naver"
• 12 Heydon,A, "Mercator: A Scalable, Extensible Web Crawler" In Proc. 2nd Int'l Conf. on World Wide Web 219-229, 1999
• 13 A Standard for Robot Exclusion, "Koster, M"
• 14 "Internet Archive"
• 15 "Google"
• 16 Kamvar, S, "Exploiting the Block Structure of the Web for Computing PageRank" Technical Report, Stanford University 2003
• 17 Castillo, C, "Effective Web Crawling" 39 (39): 55-56, 2005
• 18 Dong, S, "A Parallel Crawling Schema Using Dynamic Partition" Proc. Int'l Conf. on Computational Science 287-294, 2004