Constant-Delay Enumeration for Nondeterministic Document Spanners

Amarilli, Antoine; Bourhis, Pierre; Mengel, Stefan; Niewerth, Matthias

Type de document :

Article dans une revue scientifique: Article original

DOI :

10.1145/3422648.3422655

Titre :

Constant-Delay Enumeration for Nondeterministic Document Spanners

Auteur(s) :

Amarilli, Antoine [Auteur]
Département Informatique et Réseaux [INFRES]
Data, Intelligence and Graphs [DIG]
Bourhis, Pierre [Auteur]

Self-adaptation for distributed services and large software systems [SPIRALS]
Mengel, Stefan [Auteur]
Centre de Recherche en Informatique de Lens [CRIL]
Niewerth, Matthias [Auteur]
Universität Bayreuth [Deutschland] = University of Bayreuth [Germany] = Université de Bayreuth [Allemagne]

Titre de la revue :

SIGMOD Record

Pagination :

25-32

Éditeur :

ACM

Date de publication :

2020-09-04

ISSN :

0163-5808

Discipline(s) HAL :

Informatique [cs]/Base de données [cs.DB]

Résumé en anglais : [en]

One of the classical tasks in information extraction is to extract subparts of texts through regular expressions. In the database theory literature, this approach has been generalized and formalized as document spanners. ...
Lire la suite >One of the classical tasks in information extraction is to extract subparts of texts through regular expressions. In the database theory literature, this approach has been generalized and formalized as document spanners. In this model, extraction is performed by evaluating a particular kind of automata, called a sequential variable-set automaton (VA). The efficiency of this task is then measured in the context of enumeration algorithms: we first run a preprocessing phase computing a compact representation of the answers, and second we produce the results one after the other with a short time between consecutive answers, called the delay of the enumeration. Our goal is to have an algorithm that is tractable in combined complexity, i.e., in the sizes of the input document and the VA, while ensuring the best possible data complexity bounds in the input document size, i.e., a constant delay that does not depend on the document. We present such an algorithm for a variant of VAs called extended sequential VAs and give an experimental evaluation of this algorithm.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Projet ANR :

Réponse efficace aux requêtes sous mises à jour

Collections :