TL;DR
This paper introduces SXPath, a novel extension to XPath that allows querying web documents based on both their structural (DOM) and visual (spatial layout) properties. This addresses the challenge of extracting information from complex web pages where visual arrangement often conveys meaning that is not explicit in the underlying code, enabling more intuitive and robust web data extraction.
What Problem Does This Paper Address?
Web pages, especially those generated dynamically (Deep Web pages), often present data in visually organized layouts. While XPath is excellent for navigating the hierarchical Document Object Model (DOM) of these pages, it struggles when the meaning or relationships between data elements are conveyed through their spatial arrangement on screen. For instance, identifying all entries in a table row or column is straightforward in a visual representation but can be convoluted to express using only DOM structure. This gap makes it difficult for both humans and automated systems to reliably extract information from the web, as the underlying HTML structure can be complex and frequently updated, while the visual layout remains more stable and intuitive for users.
Methods
The core innovation is the Spatial DOM (SDOM), a data model that enriches the standard DOM with spatial relationships between the Minimum Bounding Rectangles (MBRs) of visualized elements. This spatial information is represented using qualitative spatial models like the Rectangle Algebra (RA).
Building on SDOM, SXPath extends XPath 1.0 with two key features:
- Spatial Axes: These allow navigation based on topological and rectangular cardinal relations (e.g., "element to the East of context node").
- Spatial Position Functions: These exploit spatial orderings to select nodes based on their position within a spatial arrangement (e.g., "the first element from the North").
The paper also defines formal semantics for SXPath and analyzes its computational complexity, demonstrating that it maintains polynomial time complexity, comparable to XPath 1.0.
Datasets
The paper describes experiments using datasets of real-world web pages, including:
- A dataset of 25 Deep Web sites (5 pages each) previously used for wrapper learning.
- A dataset of 200 Deep Web pages randomly selected from www.completeplanet.com.
- A dataset of social network sites for testing query generality.
No new benchmarks were introduced, but the experiments leverage existing web content to evaluate SXPath's performance and usability.
Key Insights and Ideas
- Visual Layout is Key: The paper strongly argues that visual layout is a crucial, often overlooked, aspect of web data semantics, and that querying should leverage this.
- Intuitive Querying: SXPath aims to make web querying more intuitive by allowing users to express spatial relationships that mirror how humans perceive and understand web page content.
- Robustness to DOM Changes: By relying on visual layout, SXPath queries are expected to be more resilient to changes in the underlying HTML structure compared to pure XPath queries.
- SDOM as the Foundation: The Spatial DOM is a critical component, bridging the gap between the DOM and the visual rendering by explicitly modeling spatial relationships.
Key Results
- Usability: Experiments showed that SXPath is perceived as easy to learn and satisfactory to use. Users required fewer attempts to write queries compared to pure XPath, especially when only visual information was available.
- Effectiveness: SXPath queries achieved significantly higher precision (99% vs. 42%) and comparable recall (100% vs. 99%) compared to pure XPath for extracting product data, demonstrating its superior ability to capture relevant information.
- Generality: SXPath queries were found to be more general and abstract, allowing them to be applied across different web sites with varying internal structures, unlike pure XPath queries which are highly site-specific.
- Performance: The system implementation demonstrated polynomial time complexity for query evaluation and SDOM construction, with empirical results showing linear time behavior for query evaluation with respect to document and query size.
Limitations and Future Work
- Complexity: While polynomial, the complexity of SXPath is higher than that of Core XPath 1.0, especially for full SXPath queries.
- Browser/Parameter Dependence: While generally robust, SXPath queries can be affected by changes in browser window size and font dimensions, although the system's real-time SDOM computation mitigates this for users.
- Future Work: The authors suggest SXPath could be a stepping stone for improving both human and automatic web data extraction, potentially enhancing wrapper induction systems. Further investigation into SXPath's implications for wrapper induction effectiveness is mentioned.
Summary updated