Link analysis and search engine architecture

Link analysis in web search

Link analysis uses the hyperlink structure of the web to judge the importance and relevance of pages. Search engines treat a link as a recommendation: pages with many links from good pages are ranked higher. The main algorithms are PageRank and HITS (hubs and authorities). The anchor text of links also helps describe the target page.

How a search engine works

1. Crawling: a crawler (spider) starts from seed URLs, downloads pages and follows links to find new pages.
2. Indexing: text is extracted, cleaned, tokenised, stemmed, and stored in an inverted index (word -> list of pages and positions). Link data and other features are stored too.
3. Ranking: relevance of pages to the query is calculated using content (TF-IDF) and link analysis (PageRank).
4. Query processing: the user's query is analysed, matching documents are found in the index, ranked and displayed with snippets.

Architecture

 Web --> [Crawler] --> [Page store]
                           |
                      [Indexer]
                           |
            [Inverted index + Link data]
                           |
 User --> [Query processor / Ranker] --> Results

Components

• Crawler/spider and URL scheduler.
• Document repository (cache of pages).
• Indexer and link analyser (computes PageRank).
• Index/database (distributed across many servers).
• Query engine and ranking module, and user interface.
• Supporting parts: spam detection, caching of popular queries and freshness updates.