Constant-Delay Enumeration for Nondeterministic ...
Type de document :
Compte-rendu et recension critique d'ouvrage
DOI :
Titre :
Constant-Delay Enumeration for Nondeterministic Document Spanners
Auteur(s) :
Amarilli, Antoine [Auteur]
Data, Intelligence and Graphs [DIG]
Département Informatique et Réseaux [INFRES]
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
Data, Intelligence and Graphs [DIG]
Département Informatique et Réseaux [INFRES]
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
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 >
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
Vulgarisation :
Non
Projet ANR :
Collections :
Source :
Fichiers
- http://arxiv.org/pdf/2003.02576
- Accès libre
- Accéder au document
- 2003.02576
- Accès libre
- Accéder au document