An adaptive crawler for locating hiddenwebentry points

Luciano Barbosa, Juliana FreireWWW 2007 · DOI

TL;DR

This paper introduces ACHE, an adaptive web crawler designed to efficiently discover entry points to hidden-web databases. By dynamically learning from its crawling experience, ACHE significantly improves its ability to locate relevant forms compared to traditional, fixed-strategy crawlers, achieving up to three times higher harvest rates.

What Problem Does This Paper Address?

The "hidden web" refers to content residing in databases that is not directly indexed by standard search engines, typically accessed through web forms. Locating these hidden-web sources is challenging because they are sparsely distributed across the vastness of the internet. Existing methods, like the Form-Focused Crawler (FFC), attempt to address this by focusing on specific topics and prioritizing links that are likely to lead to forms. However, these methods often require extensive manual tuning, are sensitive to the quality of initial training data, and can retrieve a heterogeneous mix of forms, many of which may not be relevant to the target domain. This paper aims to overcome these limitations by developing an adaptive crawler that can learn and adjust its strategy automatically, leading to more efficient discovery of relevant hidden-web entry points with less manual effort.

Methods

ACHE builds upon the FFC but introduces a novel adaptive learning framework. Key components and techniques include:

  • Adaptive Link Learner: This is the core of ACHE's adaptivity. It dynamically learns features from successful crawling paths and uses this information to update a link classifier. This process is triggered periodically based on a learning threshold (e.g., after finding a certain number of relevant forms).
  • Automated Feature Selection (AFS): Instead of manual feature engineering, ACHE automatically extracts features from link anchors, URLs, and surrounding text. This process identifies terms that are indicative of paths leading to relevant forms.
  • Form Filtering (Critic): This component acts as a critic, evaluating the quality of retrieved forms. It uses a two-stage process: a Searchable Form Classifier (SFC) to identify forms that are likely to query a database, and a Domain-Specific Form Classifier (DSFC) to determine if a searchable form belongs to the target database domain. This feedback is crucial for the adaptive learning process.
  • Frontier Manager (BGE/PG): This module balances exploration (following links that might lead to future rewards) and exploitation (following links that are known to yield high rewards). It uses the link classifier's predictions to prioritize links in the crawling frontier.

The adaptive nature means ACHE doesn't rely on a pre-built, fixed link classifier. Instead, it starts with a basic strategy and refines its link prioritization over time based on the forms it successfully finds.

Datasets

The paper evaluates ACHE on eight representative online database domains, including Airfare, Auto, Book, Hotel, Job, Movie, Music, and Rental. The density of relevant forms varies significantly across these domains, with the Movie domain being the sparsest and Hotel being the densest. The paper does not introduce new benchmark datasets but uses real-world web data from these domains.

Key Insights and Ideas

  • Adaptive Learning is Crucial for Sparse Data: The paper strongly demonstrates that adaptive learning is essential for efficiently crawling the hidden web, especially in domains where relevant forms are rare. Crawlers that can adjust their strategy based on experience perform significantly better.
  • Automated Feature Selection Reduces Manual Effort: Eliminating manual feature engineering for link classifiers drastically reduces the setup time and expertise required, making the crawler more accessible. The AFS component proves effective in identifying relevant features automatically.
  • Delayed Benefit is Key to Exploration: By considering links that might not lead to immediate rewards but could open up new paths, ACHE can discover forms that a purely "best-first" approach would miss. This exploratory behavior is vital for adapting to the complex and often unpredictable structure of the web.
  • Form Quality Matters: The accuracy of the form filtering component (critic) is paramount. Without reliable identification of relevant forms, the adaptive learning process can be misled, leading to poor performance.

Key Results

  • ACHE's adaptive crawlers (Online Learning and Offline-Online Learning) achieved significantly higher harvest rates of relevant forms compared to a baseline crawler and the fixed-strategy FFC.
  • In experiments, adaptive crawlers retrieved up to three times as many forms as crawlers using a fixed focus strategy.
  • The "Online Learning" configuration, which starts from scratch without any pre-defined link classifier, was able to achieve harvest rates comparable to, and sometimes better than, crawlers that relied on prior knowledge.
  • The effectiveness of adaptive learning was more pronounced in sparser domains, where fixed strategies struggled to find enough relevant data.
  • The automated feature selection process was able to identify good features, sometimes outperforming manually selected features.

Limitations and Future Work

  • Sparsity Challenges: For extremely sparse domains (like the Movie domain in their experiments), even ACHE's adaptive approach can struggle if the initial crawl doesn't yield enough relevant forms to bootstrap the learning process effectively. A more focused initial strategy might be needed for such cases.
  • Integration of Other Components: The authors suggest integrating the "apprentice" component from other work (Chakrabarti et al.) to further improve focus and reduce the retrieval of off-topic pages.
  • Accelerating Learning: Investigating the use of back-crawling during learning iterations to increase sample paths is proposed to speed up the learning process, especially for sparse domains.
  • Simplifying Domain-Specific Classifiers: Future work includes exploring strategies to simplify the creation of domain-specific form classifiers, potentially by using online-database clustering techniques.

Summary updated

BibTeX
@inproceedings{barbosa2007adaptive,
  author = {Luciano Barbosa and Juliana Freire},
  title = {{An adaptive crawler for locating hiddenwebentry points}},
  booktitle = {The Web Conference},
  year = {2007},
  doi = {10.1145/1242572.1242632},
}
Figure