계층적 캐시 기법을 이용한 대용량 웹 검색 질의 처리 시스템의 구현 = Implementation of a Large-scale Web Query Processing System Using the Multi-level Cache Scheme

국문 초록 (Abstract)

웹을 이용한 정보 공개 및 검색이 확대됨에 따라 웹 검색 엔진도 지속적인 주목을 받고 있다. 이에 따라 웹 검색 엔진의 다양한 기술적 문제를 해결하고자 하는 연구가 있었음에도 웹 검색 엔진의 질의 처리 시스템에 대한 기술적 내용은 잘 다뤄지지 않았다. 질의 처리 시스템의 경우 소프트웨어 아키텍처나 운영 기법을 고안하기 어렵기 때문에 본 논문에서는 구현된 상용 시스템을 바탕으로 관련 기술을 소개하고자 한다. 구현된 질의 처리 시스템은 6,500 만개 웹 문서를 색인하여 일 500만개 이상의 사용자 질의 요청을 수행하는 큰 규모의 시스템이다. 구현한 시스템은 질의 처리 결과를 재사용하기 위해 계층적 캐시 기법을 적용했으며, 저장된 캐시 데이타는 4계층으로 구성된 데이타 저장소에 분산 저장되는 것이 특징이다. 계층적 캐시 기법을 통해 질의 처리 용량을 400% 정도로 향상 시킬 수 있었으며 이를 통해 서버 구축 비용을 70% 정도 절감할 수 있었다.

다국어 초록 (Multilingual Abstract)

With the increasing demands of information sharing and searches via the web, the web search engine has drawn much attention. Although many researches have been done to solve technical challenges to build the web search engine, the issue regarding its query processing system is rarely dealt with. Since the software architecture and operational schemes of the query processing system are hard to elaborate, we here present related techniques implemented on a commercial system. The implemented system is a very large-scale system that can process 5-million user queries per day by using index files built on about 65-million web pages. We implement a multi-level cache scheme to save already returned query results for performance considerations, and the multi-level cache is managed in 4-level cache storage areas. Using the multi-level cache, we can improve the system throughput by a factor of 4, thereby reducing around 70% of the server cost.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구
• 3. 질의 처리를 위한 색인구조
• 4. 질의 처리를 위한 계층적 캐시 기법
• 5. 성능 고찰
• 6. 결론
• 참고문헌

참고문헌 (Reference)

1 Taher H, "Topic-sensitive PageRank"

2 Larry Page, "The PageRank Citation Ranking: Bring Order to the Web" Stanford Univ. Technical Report 1998

3 Reiner Kraft, "Searching with Context" 477-486, 2006

4 Arvind Arasu, "Searching the Web, ACM Trans" 1 (1): 2-43, 2001

5 "Search Engine Report"

6 Ronny Lempel, "Predictive Caching and Prefetching of Query Results in Search Engines" 19-28, 2003

7 Maxim Lifantsev, "Implementation of a modern web search engine cluster" 2003

8 C. Ruemmler, "IEEE Computer" 17 (17): 17-28, 1994

9 Maxim Lifantsev, "I/O-Conscious Data Preparation for Large-Scale Web Search Engines" 2002

10 Andrei Z, "Efficient URL Caching for World Wide Crawling" 2003

11 Sriram Raghvan, "Crawling the Hidden Web" 129-138, 2001

12 Alfred V, "Corasick, Efficient String Matching: An Aid to Bibliographic Search" 18 (18): 333-340, 1975

13 Steve Lawrence, "Context in Web Search, IEEE Data Engineering Bulletin" 23 (23): 25-32, 2000

14 Zheng Chen, "Building a web thesaurus from web link structure" 48-55, 2003

15 Sergey Melnik, "Building a Distributed Full-text Index for the Web" 396-406, 2001

16 Tiziano Fagni, "Boosting the performance of Web search engines: Caching and prefetching query results by exploiting historical usage data" 24 (24): 51-78, 2006

17 BoostingCraig Silverstein, "Analysis of a very large web search engine query log" 33 (33): 6-12, 1999

18 C. Lee, "A Fast Two- Stage Algorithm for Computing PageRank" Stanford University 2003