Summary 16 — Web Retrieval, Part I (The Web, Its Structure & Search Engine Architecture)

Source: 11_WebIR_Part-I.pdf

1. Table of Contents (Topics Covered)

Gist (2–3 paragraphs)

The Web is a massive, public, unstructured, fast-changing repository, making relevant retrieval genuinely hard. Challenges split into data-centric (distributed, volatile, huge-volume, redundant, heterogeneous, variable-quality data) and interaction-centric (users must express good queries; the system must return relevant answers fast even for poorly formed queries). The Web is effectively infinite (dynamic pages), dominated by HTML (most pages don’t even comply with the spec), with most pages small and pointed to by almost no external links.

Viewed as a graph (pages = nodes, links = edges), the Web has the famous bow-tie structure: a strongly connected CORE, an IN component (reaches CORE), an OUT component (reached from CORE), plus tendrils and many disconnected islands. Many Web measures follow power-law distributions (pages per site, in/out-link counts, connected components), and Heaps’ and Zipf’s laws hold (with faster-growing vocabulary and more biased word distribution than ordinary text). Link analysis operates at three levels — microscopic (individual node/link statistics, power-law degree), mesoscopic (node neighborhoods, hop-plots), and macroscopic (overall structure, bow-tie/jellyfish) — and is used to infer relevance, prioritize crawling, and find communities.

A search engine answers queries without touching the live Web: the dominant design is the centralized crawler-indexer architecture. Crawlers copy pages into a central repository; pages undergo normalization (punctuation removal, whitespace collapsing, lowercasing, optional stopword removal) and are stored in an inverted index (a logical view, ~30% of original size with good compression). Because words are too frequent on the Web to compute full answer sets, all engines use lazy evaluation — computing only the first ~10 results and more on demand. The early AltaVista-style architecture eventually couldn’t cope with Web growth, motivating distribution and parallelization (covered in Part II).

2. Key Terminologies — Meaning & Use Cases

Term Meaning Use Case
Data- vs. interaction-centric challenges Problems with the data vs. with users Framing Web IR difficulty
Web graph Pages as nodes, links as edges Link analysis, ranking
Bow-tie structure CORE + IN + OUT + tendrils + islands Modeling Web topology
Islands Disconnected page groups Hard to discover without registration
Power law Scale-invariant distribution (∝ x^-α) Modeling Web measures
Heaps’ / Zipf’s laws Vocabulary growth / word frequency Index sizing, term weighting
Link analysis (micro/meso/macro) Node, neighborhood, global structure Relevance, crawling, communities
Hop-plot Neighbors at increasing distances Mesoscopic analysis
Crawler-indexer architecture Crawl → repository → index → serve Standard engine design
Crawler Software agent copying Web pages Gathering the corpus
Normalization Cleaning text before indexing Consistent index terms
Inverted index (logical view) Compressed term→docs structure Fast query answering
Lazy evaluation Compute first results, rest on demand Handling frequent words

3. Process Workflow Diagram

flowchart TD
    A[World Wide Web] --> B[Crawler
traverses & copies pages]
    B --> C[Central Repository]
    C --> D[Normalization
lowercase, remove punctuation/stopwords]
    D --> E[Build Inverted Index
~30% of text size]
    F[User Query] --> G[Query Processing
no live web access]
    E --> H[Lazy Evaluation
compute top ~10 results]
    G --> H
    H --> I[Snippet generation
from local copies, top 10]
    I --> J[Results to user]
    subgraph Analysis[Link Analysis informs]
        K[Bow-tie / power laws] --> E
    end

4. ELI5 — Complex Terms Explained Simply