TL;DR
This paper introduces a novel task: automatically mapping web pages to their corresponding records in structured databases. They propose using "link paths" – sequences of hyperlinks with their anchor texts – to achieve this, demonstrating significant improvements in precision over existing methods for tasks like matching faculty web pages to DBLP records and movie pages to IMDB entries.
What Problem Does This Paper Address?
The World Wide Web is a vast repository of information, and structured databases also hold immense value. However, bridging the gap between these two worlds has been challenging. While much research has focused on extracting structured data from web pages, this paper tackles the inverse problem: mapping existing structured database records to their corresponding web pages. This is crucial for enriching database records with web content and enabling new applications, such as visualizing the geographical distribution of computer science faculty based on their homepages. The challenge lies in accurately identifying which web page belongs to which database record, especially given the web's dynamic nature and the varied ways information can be presented.
Methods
The core of the proposed method lies in leveraging "link paths" and their associated anchor texts. A link path is a sequence of hyperlinks from a reference web page (e.g., a university's computer science department homepage) to a destination web page (e.g., a faculty member's personal homepage).
- Link Path Generation: The authors explore two methods for finding these paths:
- K-shortest paths: This finds the K shortest sequences of links between a reference and destination page.
- K-shortest loopless paths: This is a variation that avoids cycles, which are common in website navigation and can lead to redundant information. They hypothesize that loopless paths provide a richer set of anchor texts.
- Anchor Text Aggregation: For each destination page, they collect anchor texts from all the K link paths leading to it. These anchor texts are then aggregated into a "bag-of-anchors," essentially a frequency count of each anchor text.
- Anchor Text Ranking: The anchor texts within each bag are ranked based on their descriptive power. This is achieved by normalizing the term frequency of each anchor text by its global term frequency across all bags. This prioritizes anchor texts that are both frequent for a specific page and relatively rare overall, suggesting higher descriptiveness.
- Mapping to Database Records: The ranked anchor texts are then used to query a structured database.
- Sanitization: Anchor texts and database entries are preprocessed (punctuation removed, lowercased) to facilitate matching.
- Search Function: A full-text search is performed on a specified database column (e.g., "Name" for faculty records).
- Approximate Matching: To handle variations in text (e.g., "Dan Roth" vs. "Roth, Dan"), an approximate matching algorithm is used. This algorithm calculates a "word distance" score, where a lower score indicates a closer match. The algorithm prioritizes exact matches and then selects the best approximate match if no exact match is found.
- Thresholding: The authors explore two matching strategies:
- Strict Matching (λ=0): Requires an exact match between the sanitized anchor text and the database record.
- Approximate Matching (λ=1): Selects the closest match based on the word distance score, always returning a result.
Datasets
The paper evaluates their approach on two real-world datasets:
- Computer Science Faculty: Data was collected from the departmental homepages of the top 25 American computer science graduate schools. This involved crawling web pages and using a homepage finding algorithm to identify faculty personal homepages. The task was to map these homepages to their corresponding records in the DBLP database.
- Movie Homepages: Data was crawled from movie websites (e.g., trailers.apple.com, allmovie.com). The task was to map official movie homepages to their corresponding records in the Internet Movie Database (IMDB).
Key Insights and Ideas
- Link Paths as Rich Descriptors: The core insight is that sequences of hyperlinks (link paths) and their anchor texts provide a more robust and descriptive signal for mapping web pages to database records than just adjacent anchor texts.
- Loopless Paths Offer More Variety: Using K-shortest loopless paths, rather than just K-shortest paths, leads to a greater diversity of anchor texts, which is beneficial for capturing comprehensive information.
- Anchor Text Ranking is Crucial: Simply aggregating anchor texts isn't enough; ranking them by their estimated descriptiveness (using a normalized frequency approach) significantly improves the accuracy of the mapping.
- Approximate Matching is Necessary: Due to variations in naming and text representation, an exact string match is often insufficient. The proposed approximate matching algorithm effectively handles these discrepancies.
- "Not Found" is a Valid Result: For strict matching, the ability to correctly identify when a web page doesn't have a corresponding database record (resulting in a "not found" outcome) is a valuable aspect of precision.
Key Results
- DBLP Mapping: The proposed method achieved significantly higher precision compared to baseline methods. For approximate matching with K-shortest loopless paths, they saw a 36.03% increase in precision over the Google baseline and a 31.24% increase over an adjacent-only approximate matching baseline. Recall was consistently high (near 100%) for approximate matching.
- IMDB Mapping: The IMDB dataset proved more challenging due to title ambiguity and the prevalence of image links without anchor text. However, the method still showed substantial improvements, tripling the precision of the adjacent-only baseline and achieving an 84.40% increase in precision over the Google baseline.
- Strict vs. Approximate Matching: Strict matching yielded very high precision but lower recall, confirming that anchor texts often represent canonical representations. Approximate matching provided near-perfect recall with a slight trade-off in precision, which the authors found acceptable for the gain in recall.
- K-shortest Loopless Paths Advantage: The K-shortest loopless paths method generally outperformed the K-shortest paths method, especially in terms of generating a wider variety of descriptive anchor texts.
Limitations and Future Work
- Misspellings: The current method may struggle with misspellings if they are consistently present and ranked highly.
- Ambiguity: While the method performs well, domains with high ambiguity (like movie titles) can still pose challenges, especially for strict matching.
- Future Work:
- Other Information Sources: Incorporating title text, URL text, and page content could further enhance mapping accuracy.
- Improved Ranking: Exploring alternative anchor text weighting algorithms, such as giving higher weight to anchor texts closer to the destination page.
- More Complex Mappings: Extending the framework to handle many-to-one, one-to-many, or many-to-many mappings.
- Broader Applications: Utilizing the mapping as an intermediary step for tasks like semantic search, schema extension, and improving ranking algorithms.
- Developing a Mutually Enhancing System: The ultimate goal is to create a system where structured and unstructured data can enrich each other.
Summary updated