Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/32727
Title: | Weight Annotation in Information Extraction | Authors: | DOLESCHAL, Johannes Kimelfeld, Benny Martens, Wim Peterfreund, Liat |
Issue Date: | 2020 | Publisher: | Schloss Dagstuhl - Leibniz-Zentrum für Informatik | Source: | 23rd International Conference on Database Theory (ICDT 2020), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 1 -18 (Art N° 8) | Series/Report: | Leibniz International Proceedings in Informatics (LIPIcs) | Abstract: | The framework of document spanners abstracts the task of information extraction from text as a function that maps every document (a string) into a relation over the document's spans (intervals identified by their start and end indices). For instance, the regular spanners are the closure under the Relational Algebra (RA) of the regular expressions with capture variables, and the expressive power of the regular spanners is precisely captured by the class of vset-automata-a restricted class of transducers that mark the endpoints of selected spans. In this work, we embark on the investigation of document spanners that can annotate extractions with auxiliary information such as confidence, support, and confidentiality measures. To this end, we adopt the abstraction of provenance semirings by Green et al., where tuples of a relation are annotated with the elements of a commutative semiring, and where the annotation propagates through the (positive) RA operators via the semiring operators. Hence, the proposed spanner extension, referred to as an annotator, maps every string into an annotated relation over the spans. As a specific instantiation, we explore weighted vset-automata that, similarly to weighted automata and transducers, attach semiring elements to transitions. We investigate key aspects of expressiveness, such as the closure under the positive RA, and key aspects of computational complexity, such as the enumeration of annotated answers and their ranked enumeration in the case of numeric semirings. For a number of these problems, fundamental properties of the underlying semiring, such as positivity, are crucial for establishing tractability. | Keywords: | Information extraction;regular document spanners;weighted automata;provenance semirings;K-relations | Document URI: | http://hdl.handle.net/1942/32727 | ISBN: | 978-3-95977-139-9 | ISSN: | 1860-5974 | e-ISSN: | 1860-5974 | DOI: | 10.4230/LIPIcs.ICDT.2020.8 | ISI #: | 000749867200001 | Rights: | Creative Commons Attribution 3.0 Unported license (CC-BY 3.0) © Johannes Doleschal, Benny Kimelfeld, Wim Martens, and Liat Peterfreund; licensed under Creative Commons License CC-BY | Category: | C1 | Type: | Proceedings Paper | Validations: | ecoom 2023 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
LIPIcs-ICDT-2020-8.pdf Restricted Access | Published version | 675.86 kB | Adobe PDF | View/Open Request a copy |
WEB OF SCIENCETM
Citations
10
checked on Oct 12, 2024
Page view(s)
32
checked on Jul 7, 2022
Download(s)
4
checked on Jul 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.