Web Search Engine

Web Search Engine history

<국외>

Lycos: CMU의 연구 프로젝트 (1994)
Excite: Standford 대학원생
OpenText: Washington University
HotBot: U.C.Berkley의 검색엔진을 발전시킴
Altavista: DEC (1995)
Google: Stanford 박사과정 학생
InkTomi (Yahoo), Northernlight 등
Ask Jeeves (1997.4)
amswerbus.com (2001)

<국내>

Simmani (1996): 한글과 컴퓨터
까치네 (1996): 대구대 동아리
한글 Yahoo (1997)
Naver : 삼성 SDS
Altavista (1998)
Lycos (1999)
Empas (1999)
HanMir, 와카노, Paran
Google (2000)

Web 문서 개수

99년 12월 약 10억개 -> 현재? 수천억개
--> 블로그 활성화 등으로 인해 기하 급수적으로 증가
-Web spider(crawler)

검색결과의 ranking

-상위 20~30개 내에 적합한 문서개수
-Ranking algorithm

Web 문서 갱신 주기

-뉴스 등 매일 갱신되어야 하는 것

Web의 특성

안정성 문제

23%/day, 38%/week

중복문서

• Syntactic 30%
• Semantic ???

High linkage: 평균 8 links/page

질의어 특성

• 평균 2.35 terms
• 부정확한 질의어
• 연산자 없는 질의어: 80%

사용자 특성

• 사용자 85% - one screen only
• 질의어 78% - 수정안함
  Link를 따라감

Web Search Problems

• 웹 문서 수집
  -priority: 매일 갱신되는 page?
  -Load balancing: internal, external
  -Trap avoidance: 서버가 죽어있거나 웹페이지가 삭제된 경우

• 문서 처리
  -중복문서 제거
  -색인어 추출 및 저장 구조
  -Query-independent ranking
  -문서 분류, 클러스터링, 문서요약 등
  -질의어 수정/ 확장

Ranking Problems

• 문서 연관성 기법
  -Query-independent ranking: pagerank, 각 문서에 대한 가중치(중요도 계산)
  -Query-dependent ranking: Hits, vector model의 cosine measure

• 문서 분석 기법
  -Ad-hoc factors: publication, location
  -Human annotation

PageRank - hyperlink information in the web

Assumptions

-links often connect related apges
-A link between pages is a recommendation

• 웹 페이지의 그래프 표현
  (u, v): page u에서 page v로 link

• 웹 페이지의 quality
  -In-degree 및 그 페이지에 link된 페이지의 quality에 의해 결정

• 웹 페이지의 pagerank는 사용자가 그 페이지에 머무는 시간에 비례

Reference

The anatomy of a large-scale hypertextual Web search engine - Sergey Brin, Lawrence Page (1998)

Relevance of Search Engines for Modern Generations (2014)

Monika Henzinger -"Web Information Retrieval"