Web Database Search Ranking Algorithms: Comprehensive Guide

Web Databases Overview: The course COMP1942, taught by Raymond Wong, explores the mechanics of web databases, specifically focusing on how search engines like Google process queries and rank results.
Search Engine Interface: A typical search engine interface (e.g., Google Hong Kong) includes components such as:
- Search Bar: For user query entry.
- Buttons: "Google Search" and "I'm Feeling Lucky."
- Localization: Features like "pages from Hong Kong" and language options.
- Advanced Features: Advanced Search, Preferences, and Language Tools.
Search Result Components: A results page (demonstrated via a search for "Raymond Wong") displays:
- Statistical Metadata: For example, "Results $1$ - $10$ of about $354,000$ for Raymond Wong ( $0.06$ seconds)."
- Listing Details: Title, URL, character count (e.g., $1k$ , $2k$ , $43k$ ), Cached link, and Similar pages.
- Rich Media Results: Video results (e.g., "AGDS Raymond_Wong.mp4" with a duration of $50\,\text{min}$ ) and external links to Wikipedia, LinkedIn (PMI HK), or specialized databases like DramaWiki and LoveHKFilm.
- Academic Identity: Identifying specific individuals such as "Raymond Chi-Wing Wong (Raymond Wong), HKUST CSE," distinguish researchers from actors or political commentators.

Definition: HITS is a ranking algorithm designed to evaluate and rank webpages based on two specific roles: "hubs" and "authorities."
Core Concepts:
- Authority: A page that provide valuable, primary information on a topic.
- Hub: A page that acts as a directory or catalog, containing many links to high-quality authorities.
Dual Weighting System: Every page $v$ in the network is assigned two distinct weights:
- Authority Weight $a(v)$ : Represents the quality of the content. A good authority is one that is linked to by many good hubs.
- Hub Weight $h(v)$ : Represents the quality of the page's links. A good hub is one that points to many good authorities.
Mathematical Relationships:
- The authority weight of a page is the sum of the hub weights of the pages that link to it: $a(v) = \sum_{u \rightarrow v} h(u)$ .
- The hub weight of a page is the sum of the authority weights of the pages it links to: $h(v) = \sum_{v \rightarrow u} a(u)$ .

Step 1: Sampling Step:
- Objective: To narrow down the vast web to a manageable set of relevant pages.
- Root Set: Given a query with several terms, the algorithm first retrieves all webpages containing those terms.
- Base Set: The root set is expanded to include "link pages." These are pages that either have a hyperlink pointing to a page in the root set or are pointed to by a page in the root set. This collection of pages forms the base set.
Step 2: Iteration Step:
- Objective: To identify which pages within the base set are the best hubs and best authorities through repeated calculation.
- Matrix Representation:
  - Let $M$ be the adjacency matrix of the base set.
  - Hub weights vector $h$ can be calculated as: $h = Ma$ .
  - Authority weights vector $a$ can be calculated as: $a = M^{T}h$ (where $M^{T}$ is the transpose of the adjacency matrix).
- Recursive Derivation:
  - $h = MM^{T}h$
  - $a = M^{T}Ma$

Scenario: A network consisting of three entities: Netscape ( $N$ ), Microsoft ( $MS$ ), and Amazon.com ( $A$ ).
Link Structure Example:
- $h(N) = a(N) + a(MS) + a(A)$
- $h(MS) = a(A)$
- $h(A) = a(N) + a(MS)$
Iterative Calculations (Non-Normalized vs. Normalized):
- Weights are updated through iterations (e.g., from Iteration $1$ to $7$ ).
- Normalization: To prevent weights from growing infinitely, they are scaled. In this example, the sum of all elements in the vector is set to $3$ .
Final Values (Iteration 7):
- Hub Vector: $N: 1.5$ , $MS: 0.402$ , $A: 1.098$
- Authority Vector: $N: 1.098$ , $MS: 1.098$ , $A: 0.804$
Ranking Options: Results can be ranked by:
- Descending order of hub weight only.
- Descending order of authority weight only.
- A combination (e.g., the sum of the hub and authority values).

Comparison with HITS:
- HITS Disadvantage: It uses two concepts (hubs/authorities), making it unclear which is more important for a specific ranking.
- PageRank Advantage: It consolidates importance into a single metric using a stochastic approach.
Mathematical Foundation:
- PageRank uses a Stochastic Matrix $M$ .
- The Rank vector $r$ is calculated via the power iteration method: $r = Mr$ .
Initial Numerical Example:
- Starting with all ranks set to $1$ , after $33$ iterations, the ranks might stabilize to: Netscape ( $1.20$ ), Microsoft ( $0.60$ ), and Amazon ( $1.20$ ).

The Problem: In the numerical example, if Microsoft ( $MS$ ) decides to link only to itself, it creates a "spider trap."
Spider Trap Definition: A group of one or more pages with no outgoing links to the rest of the web. These pages eventually accumulate all the "importance" or PageRank of the entire web.
Trap Result: After $40$ iterations in the example, Microsoft's rank becomes $3$ , while Netscape and Amazon both drop to $0$ .
The Solutions: Damping and Random Jumps:
- To prevent traps, a damping factor (typically around $0.8$ ) is introduced to simulate a user occasionally jumping to a random page.
- Revised Formula: $r = 0.8 \times Mr + c$ , where $c$ is a constant vector representing the random jump probability.
- Revised Example with $c = \begin{pmatrix} 0.2 \\ 0.2 \\ 0.2 \end{pmatrix}$ : After $20$ iterations, the distribution becomes more reasonable: $N: 0.636$ , $MS: 1.909$ , $A: 0.455$ .

Matrix Operations in Excel: Both HITS and PageRank can be modeled using spreadsheet software.
Key Function: The mmult function (Matrix Multiplication) is used to perform the iterative vector-matrix multiplications required by both algorithms ( $Ma$ , $M^{T}h$ , or $Mr$ ).