Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/33398
Title: | Constant Delay Algorithms for Regular Document Spanners | Authors: | Florenzano, Florenzano Riveros, Cristian Ugarte, Martín VANSUMMEREN, Stijn Vrgoc, Domagoj |
Issue Date: | 2018 | Publisher: | Association for Computing Machinery | Source: | Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Association for Computing Machinery, p. 165 -177 | Abstract: | Regular expressions and automata models with capture variables are core tools in rule-based information extraction. These formalisms, also called regular document spanners, use regular languages in order to locate the data that a user wants to extract from a text document, and then store this data into variables. Since document spanners can easily generate large outputs, it is important to have good evaluation algorithms that can generate the extracted data in a quick succession, and with relatively little precomputation time. Towards this goal, we present a practical evaluation algorithm that allows constant delay enumeration of a spanner's output after a precomputation phase that is linear in the document. While the algorithm assumes that the spanner is specified in a syntactic variant of variable set automata, we also study how it can be applied when the spanner is specified by general variable set automata, regex formulas, or spanner algebras. Finally, we study the related problem of counting the number of outputs of a document spanner, providing a fine grained analysis of the classes of document spanners that support efficient enumeration of their results. | Keywords: | Information Extraction;Spanners;Constant-delay evaluation;Automata;Capture Variables | Document URI: | http://hdl.handle.net/1942/33398 | ISBN: | 9781450347068 | DOI: | 10.1145/3196959.3196987 | ISI #: | WOS:000455483100013 | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Show full item record
WEB OF SCIENCETM
Citations
18
checked on Oct 19, 2024
Page view(s)
44
checked on Nov 7, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.