티스토리 뷰
1. 웹 문서의 특성과 규모
웹 문서 컬렉션의 특징
- 분산적 생성: 웹은 중앙에서 관리되는 게 아니라 전 세계 사용자들이 자유롭게 생성한다.
- 내용 다양성: 사실과 거짓, 오래된 정보, 상반된 주장 등이 섞여 있다.
- 언어 다양성: 전 세계 다양한 언어와 문체가 섞여 있어 언어처리(stemming 등)가 복잡해진다.
- 구조 다양성: 비구조적(HTML), 반구조적(XML), 구조적(DB) 문서들이 존재한다.
- 규모: 초창기(예: Altavista가 1995년에 3천만 페이지 크롤링)부터 지금까지 폭발적인 증가.
2. 웹 정보 검색 방식
검색 방식의 변화
- 초기: 키워드 기반 검색 (Altavista, Excite 등)
- 분류 기반: 디렉토리 기반의 Yahoo 스타일 (taxonomy 사용, 수작업 분류)
- 과제:
- 사용자와 편집자 간 분류 기준 불일치
- taxonomy가 커지면 오히려 찾기 힘들어짐
3. 웹 검색 사용자의 특징
- 전통 IR vs. 웹 검색 사용자:
- 과거에는 전문가가 쿼리를 설계함 → 지금은 일반인이 키워드 2~3개만 입력
- 연산자(AND, OR 등)를 잘 사용하지 않음
- 검색 결과 행동:
- 대부분 첫 3페이지 이내에서 클릭함
- 원하는 정보가 없으면 검색어를 수정하거나 다른 엔진으로 이동함
- 검색 의도 유형:
- 정보 탐색형 (정보를 알고 싶을 때)
- 내비게이션형 (특정 사이트로 가고 싶을 때)
- 거래형 (무언가를 사고/받고 싶을 때)
4. Web Graph & Power Law
- 웹은 하이퍼링크로 연결된 방향성 그래프(directed graph)로 표현됨
- 링크 분포는 Poisson 분포가 아닌 Power Law 분포를 따름:
- 대부분의 페이지는 적은 in-link를 가지지만, 일부 페이지는 수천~수만 개의 in-link를 가짐 (허브)
5. 광고 모델과 스폰서 검색
- Paid Inclusion: 노출 순서나 강조를 위해 돈을 내는 모델 (ex. Yellow Pages)
- CPM (Cost per Mille): 1,000회 노출 기준으로 광고비 지불 → 브랜드 중심
- CPC (Cost per Click): 클릭당 비용 → 거래 유도 중심 (스폰서 서치)
- GOTO는 CPC 모델을 도입한 최초의 예, 이후 Google이 발전시킴
6. 검색 엔진 최적화(SEO)와 스팸
- Keyword Stuffing: 키워드를 과하게 반복해서 tf·idf를 조작
- Cloaking: 크롤러에겐 가짜 문서, 사용자에겐 진짜 페이지 제공
- Doorway Page: 검색 결과에만 잘 보이게 만든 후 리디렉션
- Click Spam: 경쟁자의 광고 예산을 고의로 소모시키는 행위
7. 검색 엔진 인덱스 크기 측정
✔️ 웹은 무한하다
- 정적 웹 페이지만 인덱싱할 수 있음
- 동적 웹 페이지 (ex. 달력, 404 에러 등)는 무한히 생성될 수 있음
✔️ 인덱스 크기 비교 방법
- 엔진 A, B가 있을 때, A에서 무작위로 URL을 뽑아 B에 존재하는지 확인하고 교집합 비율을 측정함
- 핵심은 무작위 URL 샘플링
✔️ 무작위 URL 생성 방식
- Random Searches: 사용자 쿼리 로그에서 검색 → 결과 중 랜덤 URL 선택
- Random IP Address: 무작위 IP에 요청 보내서 페이지 얻기
- Random Queries: 단어 사전에서 단어를 랜덤 조합해 쿼리 생성 → 검색 결과 사용
8. 중복 문서와 유사 문서
✔️ 중복 문서
- 전체 웹의 약 40%가 중복됨 (미러링, 복사 등)
- 중복을 탐지해서 저장 공간과 처리 비용을 줄여야 함
✔️ Fingerprinting
- 각 문서를 해시 함수로 압축한 고유한 64비트 값으로 표현
- 두 문서의 fingerprint가 같으면 동일 문서로 간주
1. Web Search Basics
웹 검색의 기본 개념과 특성을 설명하는 장으로 시작합니다. 예시로:
- "Web Results 1 - 10 of about 7,310,000 for miele. (0.12 seconds)"
- Miele와 같은 상위 브랜드 웹사이트 검색 결과와 Sponsored Links(광고 링크)가 표시됩니다.
요점:
- 사용자에게 검색 결과를 제공하는 구조와 웹 검색의 역할을 보여줍니다.
- 관련 웹사이트와 광고 모델도 언급.
9. 유사 문서(Near-Duplicate) 탐지
1️⃣ 자카드 계수 (Jaccard Coefficient)
문서의 유사도를 가장 직관적으로 계산하는 방법 중 하나. 두 문서의 단어 집합을 각각 A, B라고 할 때:
- 교집합이 많을수록 → 유사도 ↑
- 문제: 모든 문서 쌍 비교 시 계산량 O(N²)
2️⃣ k-shingles
문서를 비교하기 위해 문서 내용을 쪼개는 방식. 대표적인 방식이 바로 k-shingle이다.
- 문장을 연속된 k개의 단어로 나눈다
- 예: a rose is a rose is a rose
- → a rose is a, rose is a rose, is a rose is, a rose is a
이렇게 하면 문장 구조가 조금 바뀌어도 유사도를 보존하면서 비교 가능하다.
3️⃣ Sketch
자카드 계수를 빠르게 근사하기 위한 기법.
✔️ 과정 요약
- k-shingle을 해시값으로 바꿈
- 여러 개의 랜덤 순열(π)을 적용
- 각 순열마다 최소 해시값(Min-Hash)을 선택 → 이걸 Sketch라고 함
- 문서 간 Sketch를 비교해 자카드 계수를 근사 계산
✔️ 예시
문서 d1의 Sketch: [1, 1, 2]
문서 d2의 Sketch: [1, 2, 1]
- 위치 1: 같음 (1 == 1)
- 위치 2: 다름 (1 != 2)
- 위치 3: 다름 (2 != 1)
→ 동일한 위치에서 동일한 값은 1개 → 근사 자카드 계수: 1/3
✔️ 장점
- 자카드 계수 정확히 안 구해도 빠르게 유사 문서 찾을 수 있음
- Sketch 길이만 정해두면 계산량도 작고, 확장성도 좋음
- 웹 검색은 단순 키워드 매칭을 넘어서, 구조, 광고, 중복 탐지까지 폭넓은 기술이 사용된다
- 중복/유사 문서 탐지에는 k-shingles와 Sketch가 핵심 도구
- 효율과 정확도 간 트레이드오프를 감안해서 자카드 계수는 근사로 계산한다