SXPath - Extending XPath towards Spatial Querying on Web Documents

Ermelinda Oro, Massimo Ruffolo, Steffen Staab

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

Abstract

Querying data from presentation formats like HTML, for purposes such as information extraction, requires the consideration of tree structures as well as the consideration of spatial relationships between laid out elements. The underlying rationale is that frequently the rendering of tree structures is very involved and undergoing more frequent updates than the resulting layout structure. Therefore, in this paper, we present Spatial XPath (SXPath), an extension of XPath 1.0 that allows for inclusion of spatial navigation primitives into the language resulting in conceptually simpler queries on Web documents. The SXPath language is based on a combination of a spatial algebra with formal descriptions of XPath navigation, and maintains polynomial time combined complexity. Practical experiments demonstrate the usability of SXPath.
BibTeX
@article{oro2010sxpath,
  author = {Ermelinda Oro and Massimo Ruffolo and Steffen Staab},
  title = {{SXPath - Extending XPath towards Spatial Querying on Web Documents}},
  journal = {Proc. VLDB Endow.},
  year = {2010},
  url = {https://openreview.net/forum?id=CgsV4JUcjg},
}
Figure