SFTM: Fast Matching of Web Pages using Similarity-based Flexible Tree Matching

Brisset, Sacha; Rouvoy, Romain; Seinturier, Lionel; Pawlak, Renaud

Type de document :

Article dans une revue scientifique: Article original

DOI :

10.1016/j.is.2022.102126

Titre :

SFTM: Fast Matching of Web Pages using Similarity-based Flexible Tree Matching

Auteur(s) :

Brisset, Sacha [Auteur]
Self-adaptation for distributed services and large software systems [SPIRALS]
Rouvoy, Romain [Auteur]
Self-adaptation for distributed services and large software systems [SPIRALS]
Seinturier, Lionel [Auteur]
Self-adaptation for distributed services and large software systems [SPIRALS]
Pawlak, Renaud [Auteur]

Titre de la revue :

Information Systems

Éditeur :

Elsevier

Date de publication :

2023-02

ISSN :

0306-4379

Mot(s)-clé(s) en anglais :

Web
Tree matching
Information Extraction

Discipline(s) HAL :

Informatique [cs]/Génie logiciel [cs.SE]
Informatique [cs]/Web

Résumé en anglais : [en]

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 pages. However, when applied to existing web pages, traditional ...
Lire la suite >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 pages. However, when applied to existing web pages, traditional tree matching approaches, covered by algorithms like Tree-Edit Distance (TED) or XyDiff, either fail to scale beyond a few hundred nodes or exhibit a relatively low accuracy. In this article, we therefore propose a novel algorithm, named Similaritybased Flexible Tree Matching (SFTM), which enables high accuracy tree matching on real-life web pages, with practical computation times. We approach tree matching as an optimisation problem and leverage node labels and local topology similarity in order to avoid any combinatorial explosion. Our practical evaluation demonstrates that SFTM significantly improves the state of the art in terms of accuracy, while allowing computation times significantly lower than the most accurate solutions. By gaining on these two dimensions, SFTM therefore offers an affordable solution to match complex trees in practice.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Fichiers

https://hal.archives-ouvertes.fr/hal-03774245/document
Accès libre
Accéder au document

http://arxiv.org/pdf/2004.12821
Accès libre
Accéder au document

https://hal.archives-ouvertes.fr/hal-03774245/document
Accès libre
Accéder au document

https://hal.archives-ouvertes.fr/hal-03774245/document
Accès libre
Accéder au document

document
Accès libre
Accéder au document

SFTM-IS.pdf
Accès libre
Accéder au document

2004.12821
Accès libre
Accéder au document

document
Accès libre
Accéder au document

SFTM-IS.pdf
Accès libre
Accéder au document

SFTM: Fast Matching of Web Pages using ... BibTeX CSV Excel RIS

Fichiers

SFTM: Fast Matching of Web Pages using ...

BibTeX

CSV

Excel

RIS