TL;DR
This paper introduces WHIRL, a "soft" logic system that uses textual similarity to automatically recognize structural patterns in HTML web pages. This approach significantly improves the accuracy of identifying meaningful structures compared to previous methods, paving the way for more robust and automated web data extraction.
What Problem Does This Paper Address?
Integrating data from the web is a major challenge for many applications. Traditionally, this requires writing custom "wrappers" – programs designed to extract specific information from a particular website's HTML structure. Building and maintaining these wrappers is time-consuming and tedious because web pages frequently change their format. While semi-automated tools and machine learning approaches exist, they often require significant user input or page-specific training. This paper tackles the problem of automatically recognizing the underlying structure of web pages in a general-purpose way, aiming to reduce or eliminate the need for page-specific programming or training.
Methods
The core of the paper is the WHIRL (Web-based Information Retrieval Logic) system. WHIRL is a logic programming language extended with two key features:
- Textual Similarity: It incorporates a notion of textual similarity, inspired by information retrieval techniques (specifically, the TF-IDF weighting scheme and vector space model). This allows WHIRL to treat similar pieces of text as having a degree of equivalence, rather than being strictly identical or different.
- "Soft" Logic: WHIRL uses a "soft" logic where predicates have associated scores (between 0 and 1) representing their confidence or probability. This allows for combining evidence and handling uncertainty.
- "Many" Construct: A novel extension to WHIRL is the "many" construct, which acts as a "soft" version of universal quantification. It allows for checking if a condition holds for many instances, with the score reflecting the average confidence across those instances.
The paper proposes three structure-recognition heuristics implemented in WHIRL:
fruitful_piece: Prefers structures that extract a large number of items.anchorlike_piece: Prefers structures where the text associated with an anchor element is similar to the main extracted text.R_like_piece: Prefers structures where extracted items are similar to items in a known external relationR(e.g., a list of known university names). This is particularly useful for recognizing familiar patterns.
These methods operate on an encoding of HTML parse trees using WHIRL predicates like elt (element type, text, position) and path (relationship between nodes).
Datasets
The paper uses a dataset of 82 hand-coded wrappers for "simple list" and "simple hotlist" structures, paired with their corresponding web pages. This dataset was collected from a real-world information integration system. The authors use this dataset for evaluating their structure-recognition methods in both page-independent and page-specific (wrapper learning) scenarios. No new benchmarks are introduced, but the existing dataset is used to evaluate performance against previous methods.
Key Insights and Ideas
- Textual similarity is a powerful heuristic for structure recognition: The success of
anchorlike_pieceandR_like_piecedemonstrates that recognizing patterns based on how text looks (rather than just its exact string value) is highly effective for finding meaningful web structures. - "Soft" logic and soft quantification are crucial for flexibility: The ability to handle partial matches and combine evidence with scores (rather than strict true/false) makes the system more robust to variations in web page formats.
- General-purpose heuristics can be surprisingly effective: Even simple heuristics like
fruitful_piece(preferring structures that extract many items) perform reasonably well, suggesting that common structural patterns are prevalent. - Leveraging external knowledge (
R_like_piece) significantly boosts performance: When the system has some prior knowledge about the type of data being extracted (e.g., university names), it can achieve much higher accuracy. - Wrapper learning can be framed as structure recognition: The
R_like_piecemethod, whenRis populated with examples from a similar page or corrupted versions of data, effectively performs wrapper learning without requiring explicit negative examples.
Key Results
- Page-independent structure recognition: The
anchorlike_piecemethod achieved an accuracy of nearly 70% in identifying meaningful structures (i.e., structures that correspond to data extracted by a hand-coded wrapper) at rank 1. This is a significant improvement over a previous method that achieved around 50%. - Page-specific wrapper learning: When using page-specific information (like examples from a similar page or corrupted data from a previous version), the
R_like_piecemethod (termedexamplelikeandoldpagelikein this context) achieved meaningful structure identification nearly 85% of the time. - Interactive use benefits: For interactive use, where a user selects from a ranked list, the
domainlike with backoffmethod achieved nearly 100% coverage with a low average number of "skips" (non-meaningful items ranked before meaningful ones).
Limitations and Future Work
- Restricted to simple list and hotlist structures: The current work focuses on two specific types of structures. The authors acknowledge that more complex structures exist and would require extensions.
- "Soft" logic approximations: While WHIRL inference can be efficient, it relies on approximations, especially for complex queries.
- Representativeness of corrupted examples: The
oldpagelikeexperiment used corrupted examples that might not perfectly reflect real-world web page changes. Further investigation is needed to see how well the method performs on more typical modifications. - Future work: The authors suggest extending the methods to handle more general structures, exploring different similarity metrics, and integrating these techniques into more comprehensive web information integration systems. They also highlight the potential for using these methods for maintaining wrappers as web pages evolve.
Summary updated