The Complexity of Aggregates over Extractions by Regular Expressions

DOI10.46298/LMCS-19(3:12)2023arXiv2002.08828MaRDI QIDQ6135782

Johannes Doleschal, Benny Kimelfeld, Wim Martens

Publication date: 26 August 2023

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/2002.08828

zbMATH Keywords

aggregationweighted automatainformation extractiondocument spannersprovenance semiringsannotated databases

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of optimization problems
• The relative complexity of approximate counting problems
• Approximately counting approximately-shortest paths in directed acyclic graphs
• Handbook of weighted automata
• On Unapproximable Versions of $NP$-Complete Problems
• BPP and the polynomial hierarchy
• ``Product partition and related problems of scheduling and systems reliability: computational complexity and approximation
• An Introduction to Conditional Random Fields
• The Complexity of Planar Counting Problems
• Probabilistic quantifiers and games
• Document spanners: a formal approach to information extraction
• Recursive Programs for Document Spanners
• A logic for document spanners
• SVM Based Learning System for Information Extraction
• #NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes
• Weight Annotation in Information Extraction

This page was built for publication: The Complexity of Aggregates over Extractions by Regular Expressions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6135782)