SFTM: Fast Comparison of Web Documents using Similarity-based Flexible Tree Matching
This addresses a bottleneck for researchers and practitioners in web data mining by enabling efficient analysis of complex web documents, though it is an incremental improvement over existing methods.
The paper tackles the scalability problem of tree matching algorithms for web documents by proposing SFTM, which reduces computation times by two orders of magnitude compared to Tree-Edit Distance while maintaining qualitative performance.
Tree matching techniques have been investigated in many fields, including web data mining and extraction, as a key component to analyze the content of web documents, existing tree matching approaches, like Tree-Edit Distance (TED) or Flexible Tree Matching (FTM), fail to scale beyond a few hundreds of nodes, which is far below the average complexity of existing web online documents and applications. In this paper, we therefore propose a novel Similarity-based Flexible Tree Matching algorithm (SFTM), which is the first algorithm to enable tree matching on real-life web documents with practical computation times. In particular, we approach tree matching as an optimisation problem and we leverage node labels and local topology similarity in order to avoid any combinatorial explosion. Our practical evaluation demonstrates that our approach compares to the reference implementation of TED qualitatively, while improving the computation times by two orders of magnitude.