Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/43193
Title: | The Complexity of Aggregates over Extractions by Regular Expressions | Authors: | DOLESCHAL, Johannes Kimelfeld, B MARTENS, Wim |
Issue Date: | 2023 | Publisher: | LOGICAL METHODS COMPUTER SCIENCE E V | Source: | Logical Methods in Computer Science, 19 (3) | Abstract: | Regular expressions with capture variables, also known as "regex-formulas," extract relations of spans (intervals identified by their start and end indices) from text. In turn, the class of regular document spanners is the closure of the regex formulas under the Relational Algebra. We investigate the computational complexity of querying text by aggregate functions, such as sum, average, and quantile, on top of regular document spanners. To this end, we formally define aggregate functions over regular document spanners and analyze the computational complexity of exact and approximate computation. More precisely, we show that in a restricted case, all studied aggregate functions can be computed in polynomial time. In general, however, even though exact computation is intractable, some aggregates can still be approximated with fully polynomial-time randomized approximation schemes (FPRAS). | Keywords: | Information extraction;document spanners;weighted automata;aggregation;annotated databases;provenance semirings | Document URI: | http://hdl.handle.net/1942/43193 | ISSN: | 1860-5974 | e-ISSN: | 1860-5974 | DOI: | 10.46298/LMCS-19(3:12)2023 | ISI #: | 001049747500001 | Rights: | This work is licensed under the Creative Commons Attribution License. To view a copy of this license, visit https://creativecommons.org/licenses/by/4.0/ or send a letter to Creative Commons, 171 Second St, Suite 300, San Francisco, CA 94105, USA, or Eisenacher Strasse 2, 10777 Berlin, Germany | Category: | A1 | Type: | Journal Contribution |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
The Complexity of Aggregates over Extractions by Regular Expressions.pdf | Published version | 1.14 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.