Focused crawling by exploiting anchor text using decision tree

Jun Li, Kazutaka Furuse, Kazunori Yamaguchi2005 · DOI

TL;DR

This paper tackles the challenge of efficiently crawling the web for specific topics by proposing a novel approach that leverages anchor text from hyperlinks. By training a decision tree on anchor texts associated with relevant pages, their "Decision Tree Crawler" (DTC) can prioritize URLs more effectively than traditional methods, leading to significantly faster discovery of relevant content.

What Problem Does This Paper Address?

The internet is vast, and for tasks like topic-specific search engines or personalized content discovery, crawling the entire web is impractical and inefficient. "Focused crawlers" aim to address this by intelligently prioritizing which links to follow to find relevant pages quickly. The core challenge lies in designing an effective strategy for this prioritization. Existing methods often struggle with discovering "low in-degree" pages (pages linked to by few other pages), which can still be highly relevant. This paper seeks to improve focused crawling by finding a better way to assess the relevance of a linked page based on the text used to link to it.

Methods

The authors propose a "Decision Tree Crawler" (DTC) that uses anchor texts of hyperlinks to predict the relevance of target pages. Here's a breakdown of their approach:

  1. Defining Relevance: They first identify "relevant" pages within a limited URL domain (like a university website) using a pre-trained Support Vector Machine (SVM) classifier. This requires users to provide example relevant and irrelevant pages.
  2. Shortest Path Analysis: For each identified relevant page, they compute the shortest path from the entry page (e.g., the university's homepage) using Dijkstra's algorithm. This helps understand the "importance" or "directness" of reaching a relevant page.
  3. Anchor Text Feature Engineering: They collect anchor texts from hyperlinks that connect pages on these shortest paths to relevant pages (positive examples) and hyperlinks that connect pages off these shortest paths to relevant pages (negative examples).
  4. Decision Tree Training: An ID3 algorithm is used to train a decision tree on these anchor text examples. The tree learns to classify anchor texts based on the presence of specific terms, predicting whether a hyperlink's target page is likely to be relevant.
  5. Crawling Strategy: The trained decision tree then guides the crawler. When encountering a hyperlink, its anchor text is fed into the decision tree. If the tree predicts relevance, the link is prioritized for crawling.

Datasets

The experiments were conducted on real-world data sets from four Japanese universities: the University of Tokyo (UT), Kyoto University (KU), Keio University (KO), and Waseda University (WU). The target topic for crawling was "lecture." The paper does not introduce new benchmark datasets but uses existing university websites as their testbeds.

Key Insights and Ideas

  • Anchor text as a powerful signal: The paper highlights that anchor text, often a concise summary of a linked page's content, can be a very effective feature for predicting relevance, especially when traditional page content analysis might be too resource-intensive or less informative for focused crawling.
  • Addressing the "low in-degree" problem: By focusing on paths to relevant pages and the anchor texts associated with them, the DTC can potentially discover relevant pages that might be missed by crawlers that solely rely on link popularity or simple breadth-first traversal.
  • Decision trees for efficient classification: Using a decision tree allows for a relatively interpretable and efficient way to model the complex relationship between anchor text features and page relevance, enabling real-time prioritization during crawling.

Key Results

The DTC demonstrated significant improvements in crawling efficiency:

  • On the University of Tokyo (UT) dataset: The DTC was able to crawl 50% of the relevant pages by only crawling about 3% of the total pages. This is a substantial improvement over a standard breadth-first crawler and a traditional focused crawler.
  • Generalization: When trained on the UT data and tested on the other three universities (KU, KO, WU), the DTC consistently outperformed the breadth-first crawler. It was competitive with, and sometimes slightly inferior to, the traditional focused crawler, suggesting good generalization but also room for improvement in consistency across different web structures.

Limitations and Future Work

  • Generalization across domains: While the DTC showed good performance on different university websites, its generalization performance across vastly different web domains (e.g., e-commerce vs. academic) might require further investigation and potentially domain-specific training.
  • SVM dependency: The initial identification of relevant pages relies on an SVM classifier, which itself requires labeled data. The quality and quantity of this initial training data can impact the DTC's performance.
  • Anchor text limitations: The paper acknowledges that anchor text can sometimes be misleading or generic. Future work could explore combining anchor text features with other signals (e.g., surrounding text, link context) for even more robust relevance prediction. The authors also note that further study is needed to improve the generalization performance and make it steady across different datasets.

Summary updated

Abstract

Focused crawlers are considered as a promising way to tackle the scalability problem of topic-oriented or personalized search engines. To design a focused crawler, the choice of strategy for prioritizing unvisited URLs is crucial. In this paper, we propose a method using a decision tree on anchor texts of hyperlinks. We conducted experiments on the real data sets of four Japanese universities and verified our approach.
BibTeX
@misc{li2005focused,
  author = {Jun Li and Kazutaka Furuse and Kazunori Yamaguchi},
  title = {{Focused crawling by exploiting anchor text using decision tree}},
  year = {2005},
  doi = {10.1145/1062745.1062933},
}

Loading related content...

Figure