Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/43193
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | DOLESCHAL, Johannes | - |
dc.contributor.author | Kimelfeld, B | - |
dc.contributor.author | MARTENS, Wim | - |
dc.date.accessioned | 2024-06-18T09:23:35Z | - |
dc.date.available | 2024-06-18T09:23:35Z | - |
dc.date.issued | 2023 | - |
dc.date.submitted | 2024-06-18T09:19:07Z | - |
dc.identifier.citation | Logical Methods in Computer Science, 19 (3) | - |
dc.identifier.uri | http://hdl.handle.net/1942/43193 | - |
dc.description.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). | - |
dc.description.sponsorship | The authors are grateful to Noa Bratman for participating in the initial efforts on the research reported in this manuscript. Furthermore, we thank the anonymous reviewers of ICDT 2021 and LMCS for many helpful remarks. This work was supported by the GermanIsraeli Foundation for Scientific Research and Development (GIF), grant I-1502-407.6/2019. The work of Johannes Doleschal and Wim Martens was also supported by the Deutsche Forschungsgemeinschaft (DFG), grant 369116833. The work of Benny Kimelfeld was also supported by the Israel Science Foundation (ISF), grants 1295/15 and 768/19, and the DFG project 412400621 (DIP program). | - |
dc.language.iso | en | - |
dc.publisher | LOGICAL METHODS COMPUTER SCIENCE E V | - |
dc.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 | - |
dc.subject.other | Information extraction | - |
dc.subject.other | document spanners | - |
dc.subject.other | weighted automata | - |
dc.subject.other | aggregation | - |
dc.subject.other | annotated databases | - |
dc.subject.other | provenance semirings | - |
dc.title | The Complexity of Aggregates over Extractions by Regular Expressions | - |
dc.type | Journal Contribution | - |
dc.identifier.issue | 3 | - |
dc.identifier.volume | 19 | - |
local.bibliographicCitation.jcat | A1 | - |
local.publisher.place | KLEISTSTR 22, BRAUNSCHWEIG 38124, GERMANY | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
dc.identifier.doi | 10.46298/LMCS-19(3:12)2023 | - |
dc.identifier.isi | 001049747500001 | - |
local.provider.type | Web of Science | - |
local.uhasselt.international | yes | - |
item.fulltext | With Fulltext | - |
item.accessRights | Open Access | - |
item.contributor | DOLESCHAL, Johannes | - |
item.contributor | Kimelfeld, B | - |
item.contributor | MARTENS, Wim | - |
item.fullcitation | DOLESCHAL, Johannes; Kimelfeld, B & MARTENS, Wim (2023) The Complexity of Aggregates over Extractions by Regular Expressions. In: Logical Methods in Computer Science, 19 (3). | - |
crisitem.journal.issn | 1860-5974 | - |
crisitem.journal.eissn | 1860-5974 | - |
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.