Web Crawling & Search Engines: Architecture, Crawling, Indexing, Ranking

What is a Search Engine?

A search engine is a software system that retrieves information from the web based on user queries. It consists of three core components:

1. Web Crawler (Spider): Downloads web pages.
2. Indexer: Processes and stores data for fast retrieval.
3. Query Processor: Matches queries to indexed data and ranks results.

---

Web Crawling: How Search Engines Discover Web Pages

1. Crawling Basics

Web crawling is the automated process of browsing the web to discover and download web pages. Crawlers start from a seed URL (e.g., https://www.esewa.com.np) and follow hyperlinks to explore new pages.

2. Crawling Strategies

Worked Example: Crawling eSewa’s Payment Links Suppose a crawler starts at esewa.com.np and follows links to:

1. esewa.com.np/payment (BFS: add to queue).
2. From payment, it finds esewa.com.np/payment/mobile (DFS: explore deeply).
3. Meanwhile, it also crawls esewa.com.np/support (BFS: parallel exploration).

3. Politeness and Crawling

Crawlers must respect robots.txt (e.g., https://daraz.com.np/robots.txt) and avoid overloading servers:

• Crawl Delay: Wait time between requests (e.g., 1 second).
• Rate Limiting: Max requests per second (e.g., 10 requests/sec).
• User-Agent Identification: Crawlers identify themselves (e.g., Googlebot).

---

Search Engine Architecture

A search engine’s architecture is divided into front-end (user-facing) and back-end (processing) components:

1. Front-End Components

• Query Interface: Where users input search terms (e.g., Google’s search bar).
• Result Ranking: Displays top-ranked pages (e.g., YouTube’s algorithm).
• User Interaction: Handles clicks, spell checks, and autocomplete.

2. Back-End Components

---

Indexing: Storing Web Data for Fast Retrieval

1. Inverted Index

An inverted index maps terms (words) to their locations in documents. Example:

Worked Example: Indexing Daraz Product Pages Suppose Daraz has pages for:

• daraz.com.np/product123 (terms: "laptop", "Dell", "NPR 50000").
• daraz.com.np/product456 (terms: "mobile", "Samsung", "NPR 30000").

The inverted index would store:

{
    "laptop": {"product123": 0.9},
    "Dell": {"product123": 0.8},
    "mobile": {"product456": 0.95},
    "Samsung": {"product456": 0.85}
}

2. Compression Techniques

• Posting Lists: Store document IDs efficiently (e.g., using gap encoding).
• Term Dictionaries: Compress frequent terms (e.g., "the", "and").

---

Ranking: How Search Engines Decide Relevance

1. TF-IDF (Term Frequency-Inverse Document Frequency)

Measures how important a word is to a document and a corpus.

• TF (Term Frequency): How often a term appears in a document. Example: "mobile" appears 5 times in ncell.com.np → TF = 5.
• IDF (Inverse Document Frequency): How rare the term is across all documents. Formula: $$IDF(t)=\log \left(\frac{\text{Total Documents}}{\text{Documents with }t}\right)$$ Example: If "mobile" appears in 100 out of 1000 documents: $$IDF("mobile")=\log \left(\frac{1000}{100}\right)=\log (10)\approx 1$$
• TF-IDF Score: TF * IDF. For "mobile" in ncell.com.np: $$TF-IDF=5\times 1=5$$

2. PageRank

Developed by Google, PageRank ranks pages based on link popularity:

• A page’s rank depends on the ranks of pages linking to it.
• Formula: $$PR(p)=\frac{1-d}{N}+d\sum _{i=1}^k\frac{PR(p_i)}{L(p_i)}$$ Where:
  • $PR(p)$ = PageRank of page $p$,
  • $d$ = Damping factor (~0.85),
  • $N$ = Total pages,
  • $L(p_i)$ = Outgoing links from page $p_i$.

Worked Example: Ranking NEPSE Stock Pages Suppose:

• nepse.com.np/stock1 has links from 3 financial blogs.
• nepse.com.np/stock2 has links from 10 blogs. PageRank will favor stock2 because it has more incoming links.

---

Real-World Applications in Nepal

1. eSewa: Payment Processing

• Crawling: eSewa’s crawler discovers merchant pages (e.g., esewa.com.np/merchant123).
• Indexing: Stores terms like "payment", "bill", "NPR" for fast searches.
• Ranking: Uses TF-IDF to show relevant payment options (e.g., "electricity bill" ranks higher for ntc.com.np).

2. Daraz: E-Commerce Search

• Crawling: Daraz’s crawler fetches product pages (e.g., daraz.com.np/product456).
• Indexing: Inverted index maps "laptop" → product123 (Dell), product789 (HP).
• Ranking: Combines TF-IDF (for "laptop") and user reviews (e.g., 4.5-star products rank higher).

3. Ncell: Mobile Plans

• Crawling: Ncell’s crawler updates plan pages (e.g., ncell.com.np/plans).
• Indexing: Stores terms like "data", "call", "NPR 500".
• Ranking: PageRank boosts pages linked by multiple telecom blogs.

---

Advanced Topics

1. Distributed Crawling

Large-scale crawlers (e.g., Google) use distributed systems to:

• Partition the web by domain (e.g., .com, .com.np).
• Use load balancing to avoid server overload.

2. Dynamic Content Crawling

Modern websites use JavaScript (e.g., React, Angular). Crawlers must:

• Render pages using headless browsers (e.g., Puppeteer).
• Example: Pathao’s ride request page loads dynamically.

3. Legal and Ethical Issues

• Copyright: Crawlers must respect robots.txt and terms of service.
• Privacy: Avoid crawling personal data (e.g., esewa.com.np/user123/profile).
• Spam: Block low-quality pages (e.g., fake Daraz seller pages).

---

Exam Tip

How to Score Full Marks

1. Diagrams: Always draw the search engine architecture or inverted index structure in exams.
2. Formulas: Memorize TF-IDF and PageRank formulas. Show step-by-step calculations in worked examples.
3. Real-World Links: Relate concepts to Nepalese platforms:
   • Crawling → eSewa/Khalti payment pages.
   • Indexing → Daraz product catalogs.
   • Ranking → NEPSE stock pages or Pathao ride results.
4. Pros/Cons Tables: Compare BFS vs. DFS crawling or TF-IDF vs. PageRank.
5. Shortcuts: Use acronyms like IR (Information Retrieval) and SEO (Search Engine Optimization) in answers.

Common Pitfalls to Avoid:

• Forgetting politeness policies (e.g., crawl delay).
• Ignoring dynamic content in modern crawling.
• Mixing up TF-IDF (term importance) and PageRank (link importance).

---