Optimization and Parallelization of RegEx Based Information Extraction

Abstract

The framework of document spanners abstracts the task of information extraction from text as a function that maps every document (a string) into a relation over the document’s spans (intervals identified by their start and end indices). For instance, the regular document spanners are the regular expressions with capture variables, closed under the relational algebra. The expressive power of the regular spanners is precisely captured by the class of vset-automata—an extension of finite state automata, that mark the endpoints of selected spans. In this thesis, we embark the investigation of multiple different aspects of document spanners. Namely, parallel evaluation, weight annotation, and aggregation of document spanners. Parallel Evaluation: Programs for extracting structured information from text, namely information extractors, often operate separately on document segments obtained from a generic splitting operation such as sentences, paragraphs, k-grams, HTTP requests, and so on. An automated detection of this behavior of extractors, which we refer to as split-correctness, would allow text analysis systems to devise query plans with parallel evaluation on segments for accelerating the processing of large documents. Other applications include the incremental evaluation on dynamic content, where re-evaluation of information extractors can be restricted to revised segments, and debugging, where developers of information extractors are informed about potential boundary crossing of different semantic components. We propose and study a new formal framework for split-correctness within the formalism of document spanners. Our analysis studies the complexity of split-correctness over regular spanners. We also discuss different variants of split-correctness, for instance, in the presence of black-box extractors with split constraints. Weight Annotation: Concerning weight annotation, we embark on the investigation of document spanners that can annotate extractions with auxiliary information such as confidence, support, and confidentiality measures. To this end, we adopt the abstraction of provenance semirings by Green, Karvounarakis, and Tannen, where tuples of a relation are annotated with the elements of a commutative semiring, and where the annotation propagates through the positive relational Algebra operators via the semiring operators. Hence, the proposed spanner extension, referred to as an annotator, maps every document into an annotated relation over the spans. As a specific instantiation, we explore weighted vset-automata that, similarly to weighted automata and transducers, attach semiring elements to transitions. We investigate key aspects of expressiveness, such as the closure under the positive relational Algebra, and key aspects of computational complexity, such as the enumeration of annotated answers and their ranked enumeration in the case of ordered semirings. For a number of these problems, fundamental properties of the underlying semiring, such as positivity, are crucial for establishing tractability. Aggregation: Lastly 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 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).

Het raamwerk van document spanners abstraheert het extraheren van informatie uit tekst als een functie die elk document (een tekst) omzet in een relatie bestaand uit overspanningen van het document (intervallen geïdentificeerd door hun start- en eindindices). Bijvoorbeeld, de reguliere document spanners zijn de reguliere expressies met variabelen die gesloten zijn onder de relationele algebra. De uitdrukkingskracht van de reguliere spanners valt precies samen met de klasse van vset-automata en deze zijn een uitbreiding van eindigetoestandsautomaten die de eindpunten van geselecteerde overspanningen markeren. In deze dissertatie beginnen we met het onderzoeken van verschillende aspecten van de document spanners zoals parallelle evaluatie, gewicht annotatie en aggregatie van de document spanners. Parallele evaluatie: Programma’s voor het extraheren van gestructureerde informatie uit tekst, genaamd information extractors, werken afzonderlijk op verschillende delen van het document, die verkregen zijn uit een generieke splitsingsoperatie. Voorbeelden van zulke delen zijn zinnen, paragrafen, k-grammen, HTTP verzoeken, enzovoort. Het geautomatiseerd detecteren van dit gedrag van de extractors, dat split-correctness heet, zou tekstanalyse systemen in staat stellen om queryplannen te bedenken met parallelle evaluatie op de verschillende delen zodat het verwerken van grote documenten versneld kan worden. Andere toepassingen zijn de incrementele evaluatie van dynamische inhoud, waarbij de herevaluatie van de informatie extractie kan beperkt worden tot de aangepaste delen, alsook foutopsporing, waarbij ontwikkelaars van informatie-extractors geïnformeerd worden over potentiële semantische componenten die over deelgrenzen heen gaan. We presenteren een nieuw formeel kader voor split-correctness en bestuderen dit binnen de theorie van document spanners. Onze analyse bestudeert de complexiteit van splitcorrectness voor reguliere spanners, bovendien bespreken we ook verschillende varianten van split-correctness, bijvoorbeeld bij de aanwezigheid van black-box extractors met split constraints. Annotatie van gewichten: Met betrekking tot de gewichtsannotatie, beginnen we met het onderzoeken van document spanners die overspanningen kunnen annoteren met extra informatie zoals een maat een zekerheid, ondersteuning en vertrouwelijkheid. Hiervoor gebruiken we de abstractie van provenance semirings van Green, Karvounarakis, en Tannen, waarbij de tuples van een relatie geannoteerd worden met de elementen van een commutatieve semiring en waar de annotatie via de semiring operatoren doorgegeven wordt doorheen de positieve relationele Algebra operatoren. Vandaar dat de voorgestelde uitbreiding voor spanners, aangeduid als een annotator, elke document toekent aan een geannoteerde relatie die gaat over de overspanningen. Als een specifieke geval, verkennen we de gewogen vset-automata die, op dezelfde manier als gewogen automaten en transductoren, semiring elementen koppelen met overgangen. We onderzoeken belangrijke aspecten van expressiviteit, zoals het gesloten zijn onder de positieve relationele Algebra en belangrijke aspecten van computationele complexiteit, zoals de opsomming van de geannoteerde antwoorden of de gerangschikte opsomming in het geval dat geordende semirings gebruikt worden. Voor een aantal van deze problemen zijn de fundamentele eigenschappen van de onderliggende semiring, zoals positiviteit, cruciaal voor het nagaan van de uitvoerbaarheid ervan.

Das System der Document Spanner (frei übersetzt: Abschnittsanfragen) abstrahiert die Aufgabe der Informationsextraktion aus Texten als eine Funktion, die Dokumente (Zeichenketten) in Relationen über Abschnitte des Dokuments (identifiziert durch die Start- und Endposition in der Zeichenkette) übersetzt. Reguläre Abschnittsanfragen zum Beispiel sind reguläre Ausdrücke mit Variablen, abgeschlossen unter der relationalen Algebra. Die Ausdrucksstärke von regulären Abschnittsanfragen umfasst exakt die Klasse der sogenannten vset-Automaten — eine Erweiterung von endlichen Automaten, welche die Endpunkte der selektierten Abschnitte markieren. In dieser Arbeit studieren wir mehrere verschiedene Aspekte von Abschnittsanfragen und befassen uns mit der parallelen Auswertung, Annotation von Gewichten und der Aggregation von Abschnittsanfragen. Parallele Auswertung: Programme, die strukturierte Informationen aus Texten extrahieren, auch informations Extraktoren genannt, arbeiten oft unabhängig voneinander an mehreren Teilen eines Dokuments, die durch eine generische Aufteilung des Dokuments in Sätze, Absätze, HTTP Anfragen oder Ähnliches erzeugt werden. Ein automatisches Erkennen eines solchen Verhaltens, das wir als Aufteilungskorrektheit bezeichnen, würde es informations Extraktoren erlauben, Ausführungspläne zur parallelen Auswertung zu erzeugen und dadurch die Verarbeitung von großen Dokumenten zu beschleunigen. Andere Anwendungen sind die inkrementelle Auswertung von dynamischen Inhalten, für welche die erneute Auswertung von informations Extraktoren auf überarbeitete Bereiche beschränkt werden kann und die Suche von Fehlern, wobei Entwickler von informations Extraktoren über die mögliche Überschreitung von semantischen Inhaltsgrenzen informiert werden können. In dieser Arbeit definieren und studieren wir ein neues formales System für Aufteilung Korrektheit im Formalismus von Abschnittsanfragen. Unsere Analyse studiert die Komplexität der Aufteilungskorrektheit für reguläre Abschnittsanfragen und wir untersuchen verschiedene Varianten von Aufteilungskorrektheit, zum Beispiel im Zusammenhang mit Black Box Extraktoren unter Aufteilungsbedingungen. Gewichts Annotation: Bezüglich der gewichteten Annotation untersuchen wir Abschnittsanfragen, welche die extrahierten Daten mit zusätzlichen Informationen, wie zum Beispiel der Irrtumswahrscheinlichkeit, dem Support oder Informationen zur Vertraulichkeit anreichern. Dazu passen wir die Abstraktion sogenannter “provenance semirings” (frei übersetzt: Ursprungs Semiringe) von Green, Karvounarakis und Tannen an. In diesen werden Tupel einer Relation mit Elementen eines kommutativen Semirings annotiert und Informationen zum Ursprung mittels der Semiring Operatoren durch positive relationale Algebra Operatoren propatiert. Die vorgeschlagene Erweiterung von Abschnittsanfragen, welche wir als Annotatoren bezeichnen, bildet Dokumente auf annotierte Relationen über Abschnitte ab. Als eine spezifische Darstellungsmöglichkeit untersuchen wir gewichtete vset-Automaten welche ähnlich zu gewichteten endlichen Automaten und Transduktoren Semiring Elemente zu Zustandsübergängen hinzufügt. Wir untersuchen Schüsseleigenschaften der Ausdrucksstärke, wie zum Beispiel den Abschluss unter positiver relationaler Algebra und Schlüsseleigenschaften der Komplexität, wie zum Beispiel der Aufzählung von annotierten Antworten und deren geordnete Aufzählung im Fall von geordneten Semiringen. Für eine Vielzahl dieser Probleme sind fundamentale Eigenschaften des verwendeten Semirings, beispielsweise Positivität, für effiziente Algorithmen essenziell.