research-article

Efficient Enumeration Algorithms for Regular Document Spanners

Authors:

Fernando Florenzano,

Cristian Riveros,

Martín Ugarte,

Stijn Vansummeren,

Domagoj VrgočAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 45, Issue 1

Article No.: 3, Pages 1 - 42

https://doi.org/10.1145/3351451

Published: 08 February 2020 Publication History

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 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 efficient evaluation algorithms that can generate the extracted data in a quick succession, and with relatively little precomputation time. Toward this goal, we present a practical evaluation algorithm that allows output-linear delay enumeration of a spanner’s result after a precomputation phase that is linear in the document. Although 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 and provide a fine-grained analysis of the classes of document spanners that support efficient enumeration of their results.

References

[1]

Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley.

[2]

Carme Álvarez and Birgit Jenner. 1993. A very hard log-space counting class. Theoretical Computer Science 107, 1 (1993), 3--30.

Digital Library

[3]

Antoine Amarilli, Pierre Bourhis, Stefan Mengel, and Matthias Niewerth. 2019. Constant-delay enumeration for nondeterministic document spanners. In Proceedings of the 22nd International Conference on Database Theory (ICDT’19). 22:1--22:19.

[4]

Marcelo Arenas, Francisco Maturana, Cristian Riveros, and Domagoj Vrgoč. 2016. A framework for annotating CSV-like data. Proceedings of the VLDB Endowment 9, 11 (2016), 876--887.

Digital Library

[5]

Guillaume Bagan. 2006. MSO queries on tree decomposable structures are computable with linear delay. In Computer Science Logic. Lecture Notes in Computer Science, Vol. 4207. Springer, 167--181.

[6]

Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. 2007. On acyclic conjunctive queries and constant delay enumeration. In Computer Science Logic. Lecture Notes in Computer Science, Vol. 4646. Springer, 208--222.

[7]

Laura Chiticariu, Rajasekar Krishnamurthy, Yunyao Li, Sriram Raghavan, Frederick Reiss, and Shivakumar Vaithyanathan. 2010. SystemT: An algebraic approach to declarative information extraction. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL’10). 128--137.

[8]

Laura Chiticariu, Yunyao Li, and Frederick R. Reiss. 2013. Rule-based information extraction is dead! Long live rule-based information extraction systems! In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing (EMNLP’13). 827--832.

[9]

Bruno Courcelle. 2009. Linear delay enumeration and monadic second-order logic. Discrete Applied Mathematics 157, 12 (2009), 2675--2700.

Digital Library

[10]

Russ Cox. 2007. Regular Expression Matching Can Be Simple and Fast (But Is Slow in Java, Perl, PHP, Python, Ruby, …). Retrieved December 27, 2019 from http://swtch.com/&sim;rsc/regexp/regexp1.html.

[11]

Ronald Fagin, Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren. 2014. Cleaning inconsistencies in information extraction via prioritized repairs. In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS’14). 164--175.

Digital Library

[12]

Ronald Fagin, Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren. 2015. Document spanners: A formal approach to information extraction. Journal of the ACM 62, 2 (2015), Article 12.

Digital Library

[13]

Ronald Fagin, Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren. 2016. Declarative cleaning of inconsistencies in information extraction. ACM Transactions on Database Systems 41, 1 (2016), Article 6, 44 pages.

Digital Library

[14]

Fernando Florenzano, Cristian Riveros, Martín Ugarte, Stijn Vansummeren, and Domagoj Vrgoc. 2018. Constant delay algorithms for regular document spanners. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 165--177.

Digital Library

[15]

Dominik D. Freydenberger. 2017. A logic for document spanners. In Proceedings of the 20th International Conference on Database Theory (ICDT’17). Article 13, 18 pages.

[16]

Dominik D, Freydenberger, and Mario Holldack. 2016. Document spanners: From expressive power to decision problems. In LIPIcs-Leibniz International Proceedings in Informatics, Vol. 48. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[17]

Dominik D. Freydenberger, Benny Kimelfeld, and Liat Peterfreund. 2018. Joining extractions of regular expressions. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. ACM, New York, NY, 137--149.

Digital Library

[18]

R. Hoffmann. 2012. Interactive Learning of Relation Extractors with Weak Supervision. Ph.D. Dissertation. University of Washington.

[19]

Wojciech Kazana and Luc Segoufin. 2013. Enumeration of monadic second-order queries on trees. ACM Transactions on Computational Logic 14, 4 (2013), 25.

Digital Library

[20]

Benny Kimelfeld. 2014. Database principles in information extraction. In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS’14). 156--163.

Digital Library

[21]

Rajasekar Krishnamurthy, Yunyao Li, Sriram Raghavan, Frederick Reiss, Shivakumar Vaithyanathan, and Huaiyu Zhu. 2008. SystemT: A system for declarative information extraction. SIGMOD Record 37, 4 (2008), 7--13.

Digital Library

[22]

Francisco Maturana, Cristian Riveros, and Domagoj Vrgoc. 2018. Document spanners for extracting incomplete information: Expressiveness and complexity. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. ACM, New York, NY, 125--136.

Digital Library

[23]

Andrea Morciano. 2017. Engineering a Runtime System for AQL. Master’s Thesis. Université Libre de Bruxelles and Politecnico di Milano.

[24]

Andrea Morciano, Martín Ugarte, and Stijn Vansummeren. 2016. Automata-Based Evaluation of AQL Queries. Technical Report. Université Libre de Bruxelles.

[25]

Luc Segoufin. 2013. Enumerating with constant delay the answers to a query. In Proceedings of the 16th International Conference on Database Theiry (ICDT’13). 10--20.

Digital Library

[26]

Luc Segoufin. 2014. A glimpse on constant delay enumeration. In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS’14). 13--27.

[27]

Luc Segoufin. 2015. Constant delay enumeration for conjunctive queries. SIGMOD Record 44, 1 (2015), 10--17.

Digital Library

[28]

Warren Shen, AnHai Doan, Jeffrey F. Naughton, and Raghu Ramakrishnan. 2007. Declarative information extraction using datalog with embedded extraction predicates. In Proceedings of the 33rd International Conference on Very Large Data Bases. 1033--1044.

Digital Library

[29]

Leslie G. Valiant. 1979. The complexity of enumeration and reliability problems. SIAM Journal on Computing 8, 3 (1979), 410--421.

Digital Library

[30]

Stijn Vansummeren. 2006. Type inference for unique pattern matching. ACM Transactions on Programming Languages and Systems 28, 3 (2006), 389--428.

Digital Library

Cited By

Gawrychowski PManea FSchmid M(2024)Revisiting Weighted Information Extraction: A Simpler and Faster Algorithm for Ranked EnumerationProceedings of the ACM on Management of Data10.1145/36958402:5(1-19)Online publication date: 7-Nov-2024
https://dl.acm.org/doi/10.1145/3695840
Thompson SFreydenberger D(2024)Generalized Core Spanner Inexpressibility via Ehrenfeucht-Fraïssé Games for FCProceedings of the ACM on Management of Data10.1145/36511432:2(1-18)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651143
Bossonney KCalisto VRiveros CToro GVan Sint Jan NVrgoč DBarcelo PSanchez-Pi NMeliou ASudarshan S(2024)Demonstrating REmatch: A Novel RegEx Engine for Finding all MatchesCompanion of the 2024 International Conference on Management of Data10.1145/3626246.3654746(448-451)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3626246.3654746
Show More Cited By

Index Terms

Efficient Enumeration Algorithms for Regular Document Spanners
1. Information systems
  1. Information retrieval
    1. Retrieval tasks and goals
      1. Information extraction
2. Theory of computation
  1. Formal languages and automata theory
  2. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Document Spanners: A Formal Approach to Information Extraction

An intrinsic part of information extraction is the creation and manipulation of relations extracted from text. In this article, we develop a foundational framework where the central construct is what we call a document spanner (or just spanner for short)...
Constant-Delay Enumeration for Nondeterministic Document Spanners

We consider the information extraction framework known as document spanners and study the problem of efficiently computing the results of the extraction from an input document, where the extraction task is described as a sequential variable-set ...
Constant Delay Algorithms for Regular Document Spanners
PODS '18: Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 45, Issue 1

Best of SIGMOD 2018 and Best of PODS 2018

March 2020

177 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/3382758

Editor:
Christian S. Jensen
Aalborg University, Denmark

Issue’s Table of Contents

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 February 2020

Accepted: 01 July 2019

Revised: 01 May 2019

Received: 01 October 2018

Published in TODS Volume 45, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Fondo Nacional de Desarrollo Científico y Tecnológico
Innoviris

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
303
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)2

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gawrychowski PManea FSchmid M(2024)Revisiting Weighted Information Extraction: A Simpler and Faster Algorithm for Ranked EnumerationProceedings of the ACM on Management of Data10.1145/36958402:5(1-19)Online publication date: 7-Nov-2024
https://dl.acm.org/doi/10.1145/3695840
Thompson SFreydenberger D(2024)Generalized Core Spanner Inexpressibility via Ehrenfeucht-Fraïssé Games for FCProceedings of the ACM on Management of Data10.1145/36511432:2(1-18)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651143
Bossonney KCalisto VRiveros CToro GVan Sint Jan NVrgoč DBarcelo PSanchez-Pi NMeliou ASudarshan S(2024)Demonstrating REmatch: A Novel RegEx Engine for Finding all MatchesCompanion of the 2024 International Conference on Management of Data10.1145/3626246.3654746(448-451)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3626246.3654746
Schmid M(2024)The Information Extraction Framework of Document Spanners - A Very Informal SurveySOFSEM 2024: Theory and Practice of Computer Science10.1007/978-3-031-52113-3_1(3-22)Online publication date: 19-Feb-2024
https://dl.acm.org/doi/10.1007/978-3-031-52113-3_1
Riveros CVan Sint Jan NVrgoč D(2023)REmatch: A Novel Regex Engine for Finding All MatchesProceedings of the VLDB Endowment10.14778/3611479.361148816:11(2792-2804)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611488
Kassaie BTompa F(2023)Autonomously Computable Information ExtractionProceedings of the VLDB Endowment10.14778/3603581.360358516:10(2431-2443)Online publication date: 8-Aug-2023
https://dl.acm.org/doi/10.14778/3603581.3603585
Martens WNiewerth MPopp TRojas CVansummeren SVrgoč D(2023)Representing Paths in Graph Database Pattern MatchingProceedings of the VLDB Endowment10.14778/3587136.358715116:7(1790-1803)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.14778/3587136.3587151
Su WChen HLi RChen Z(2023)Modeling Regex Operators for Solving Regex Crossword PuzzlesDependable Software Engineering. Theories, Tools, and Applications10.1007/978-981-99-8664-4_12(206-225)Online publication date: 27-Nov-2023
https://dl.acm.org/doi/10.1007/978-981-99-8664-4_12
Bucchi MGrez AQuintana ARiveros CVansummeren S(2022)COREProceedings of the VLDB Endowment10.14778/3538598.353861515:9(1951-1964)Online publication date: 27-Jul-2022
https://dl.acm.org/doi/10.14778/3538598.3538615
Schmid MSchweikardt NLibkin LBarceló P(2022)Document Spanners - A Brief Overview of Concepts, Results, and Recent DevelopmentsProceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3517804.3526069(139-150)Online publication date: 12-Jun-2022
https://dl.acm.org/doi/10.1145/3517804.3526069
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents