Spreadsheets have found wide use in many different domains and settings. They provide a broad range of both basic and advanced functionalities. In this way, they can support data collection, transformation, analysis, and reporting. Nevertheless, at the same time spreadsheets maintain a friendly and intuitive interface. Additionally, they entail no to very low cost. Well-known spreadsheet applications, such as OpenOffice, LibreOffice, Google Sheets, and Gnumeric, are free to use. Moreover, Microsoft Excel is widely available, with millions of users worldwide. Thus, spreadsheets are not only powerful tools, but also have a very low entrance barrier. Therefore, they have become very popular with novices and professionals alike. As a result, a large volume of valuable data resides in these documents. From spreadsheets, of particular interest are data coming in tabular form, since they provide concise, factual, and to a large extend structured information. One natural progression is to transfer tabular data from spreadsheets to databases. This would allow spreadsheets to become a direct source of data for existing or new business processes. It would be easier to digest them into data warehouses and to integrate them with other sources. Nevertheless, besides databases, there are other means to work with spreadsheet data. New paradigms, like NoDB, advocate querying directly from raw documents. Going one step further, spreadsheets together with other raw documents can be stored in a sophisticated centralized repository, i.e., a data lake. From then on they can serve (on-demand) various tasks and applications. All in all, by making spreadsheet data easily accessible, we can prevent information silos, i.e., valuable knowledge being isolated and scattered in multiple spreadsheet documents. Yet, there are considerable challenges to the automatic processing and understanding of these documents. After all, spreadsheets are designed primarily for human consumption, and as such, they favor customization and visual comprehension. Data are often intermingled with formatting, formulas, layout artifacts, and textual metadata, which carry domain-specific or even user-specific information (i.e., personal preferences). Multiple tables, with different layout and structure, can be found on the same sheet. Most importantly, the structure of the tables is not known, i.e., not explicitly given by the spreadsheet documents. Altogether, spreadsheets are better described as partially structured, with a significant degree of implicit information. In literature, the automatic understanding of spreadsheet data has only been scarcely investigated, often assuming just the same uniform table layout. However, due to the manifold possibilities to structure tabular data in spreadsheets, the assumption of a uniform layout either excludes a substantial number of tables from the extraction process or leads to inaccurate results. In this thesis, we primarily address two fundamental tasks that can lead to more accurate information extraction from spreadsheet documents. Namely, we propose intuitive and effective approaches for layout analysis and table detection in spreadsheets. Nevertheless, our overall solution is designed as a processing pipeline, where specialized steps build on top of each other to discover the tabular data. One of our main objectives is to eliminate most of the assumptions from related work. Instead, we target highly diverse sheet layouts, with one or multiple tables. On the same time, we foresee the presence of textual metadata and other non-tabular data in the sheet. Furthermore, we make use of sophisticated machine learning and optimization techniques. This brings flexibility to our approach, allowing it to work even with complex or malformed tables. Moreover, this intended flexibility makes our approaches transferable to new spreadsheet datasets. Thus, we are not bounded to specific domains or settings.:1 INTRODUCTION 1.1 Motivation 1.2 Contributions 1.3 Outline 2 FOUNDATIONS AND RELATED WORK 2.1 The Evolution of Spreadsheet Documents 2.1.1 Spreadsheet User Interface and Functionalities 2.1.2 Spreadsheet File Formats 2.1.3 Spreadsheets Are Partially-Structured 2.2 Analysis and Recognition in Electronic Documents 2.2.1 A General Overview of DAR 2.2.2 DAR in Spreadsheets 2.3 Spreadsheet Research Areas 2.3.1 Layout Inference and Table Recognition 2.3.2 Unifying Databases and Spreadsheets 2.3.3 Spreadsheet Software Engineering 2.3.4 Data Wrangling Approaches 3 AN EMPIRICAL STUDY OF SPREADSHEET DOCUMENTS 3.1 Available Corpora 3.2 Creating a Gold Standard Dataset 3.2.1 Initial Selection 3.2.2 Annotation Methodology 3.3 Dataset Analysis 3.3.1 Takeaways from Business Spreadsheets 3.3.2 Comparison Between Domains 3.4 Summary and Discussion 3.4.1 Datasets for Experimental Evaluation 3.4.2 A Processing Pipeline 4 LAYOUT ANALYSIS 4.1 A Method for Layout Analysis in Spreadsheets 4.2 Feature Extraction 4.2.1 Content Features 4.2.2 Style Features 4.2.3 Font Features 4.2.4 Formula and Reference Features 4.2.5 Spatial Features 4.2.6 Geometrical Features 4.3 Cell Classification 4.3.1 Classification Datasets 4.3.2 Classifiers and Assessment Methods 4.3.3 Optimum Under-Sampling 4.3.4 Feature Selection 4.3.5 Parameter Tuning 4.3.6 Classification Evaluation 4.4 Layout Regions 4.5 Summary and Discussions 5 CLASSIFICATION POST-PROCESSING 5.1 Dataset for Post-Processing 5.2 Pattern-Based Revisions 5.2.1 Misclassification Patterns 5.2.2 Relabeling Cells 5.2.3 Evaluating the Patterns 5.3 Region-Based Revisions 5.3.1 Standardization Procedure 5.3.2 Extracting Features from Regions 5.3.3 Identifying Misclassified Regions 5.3.4 Relabeling Misclassified Regions 5.4 Summary and Discussion 6 TABLE DETECTION 6.1 A Method for Table Detection in Spreadsheets 6.2 Preliminaries 6.2.1 Introducing a Graph Model 6.2.2 Graph Partitioning for Table Detection 6.2.3 Pre-Processing for Table Detection 6.3 Rule-Based Detection 6.3.1 Remove and Conquer 6.4 Genetic-Based Detection 6.4.1 Undirected Graph 6.4.2 Header Cluster 6.4.3 Quality Metrics 6.4.4 Objective Function 6.4.5 Weight Tuning 6.4.6 Genetic Search 6.5 Experimental Evaluation 6.5.1 Testing Datasets 6.5.2 Training Datasets 6.5.3 Tuning Rounds 6.5.4 Search and Assessment 6.5.5 Evaluation Results 6.6 Summary and Discussions 7 XLINDY: A RESEARCH PROTOTYPE 7.1 Interface and Functionalities 7.1.1 Front-end Walkthrough 7.2 Implementation Details 7.2.1 Interoperability 7.2.2 Efficient Reads 7.3 Information Extraction 7.4 Summary and Discussions 8 CONCLUSION 8.1 Summary of Contributions 8.2 Directions of Future Work BIBLIOGRAPHY LIST OF FIGURES LIST OF TABLES A ANALYSIS OF REDUCED SAMPLES B TABLE DETECTION WITH TIRS B.1 Tables in TIRS B.2 Pairing Fences with Data Regions B.3 Heuristics Framework

Software-basierte Selbsttest (SBST) Konzepte für Prozessoren werden zunehmend interessant nicht nur durch die At-Speed Test Problematik. Auch bezüglich Stromaufnahme und Testzeit bietet dieses Testkonzept gegenüber dem Standard Verfahren wie etwa Scan-Test Vorteile. Als grundsätzlich problematisch ist die Erzeugung solcher software-basierten Testroutinen anzusehen, da bislang kein geeigneter einheitlicher Entwurfsprozess vorliegt. Deshalb wurde exemplarisch für einen einfachen 16-bit Prozessorkern sowohl eine manuelle rein funktional erstellte SBST und eine automatisch generierte auf Strukturinformationen basierende SBST untersucht um die Möglichkeiten und Grenzen eines solchen Ansatzes aufzuzeigen.

Verwandte Sprachen besitzen Wörter gleichen Ursprungs. Im Laufe der Geschichte ändern diese Wörter ihre Gestalt und lassen sich heute in ähnlicher Form in verschiedenen Sprachen als Kognate wiederfinden. In dieser Arbeit wird ein formales Modell zur Beschreibung dieser Änderungen mit Hilfe von kodierten, lexikalischen Wortlisten entwickelt. Das Modell ist geeignet, automatisch und objektiv die Evolution idealisierter Sprachen mit Hilfe eines Sprach-Phylogeniebaumes abzubilden. Dabei werden die einzelnen Buchstabenveränderungen verwandter Wörter und die rekonstruierten Protoformen untersucht. Insbesondere interessieren solche Buchstabenveränderungen, die für mehrere Wörter einer Sprache synchron stattgefunden haben. Ein weiterer Bestandteil des evolutionären Modells ist die Identifikation von Kognaten, um die möglichen Buchstabenersetzungen zwischen den verwandten Wörtern untersuchen zu können. Für die Rekonstruktion linguistisch plausibler Buchstabenveränderungen und Kognatzuweisungen entlang einer Sprachphylogenie wird ein parsimonisches Kostenmodell verwendet, welches die verschiedenen Sprach- und Transformationsverläufe bewertet. Die Suche nach der plausibelsten Lösung ist NP-vollständig, so dass für den enorm großen Suchraum ein Annäherungsverfahren vorgeschlagen wird. Ausgehend von einer geeigneten Rekonstruktion wird durch sukzessives und minimales Verändern einzelner Transformationen oder Kognatzuweisungen mit Hilfe eines speziell entwickelten Approximationsverfahrens nicht nur eine lokal maximale Lösung, sondern eine global beste Lösung angenähert. Mit dem gewählten umfassenden Ansatz des untersuchten Rekonstruktionsmodells ist eine Sprachentwicklung für kleine Wortlisten in angemessener Zeit berechenbar. Als großer Vorteil ist die Nachvollziehbarkeit aller Einzeltransformationen für den linguistischen Diskurs anzusehen. Insbesonders die Identifikation regulärer Buchstabenersetzungen mit möglicher Interpretation als Lautwandel früherer Sprachen ist hierbei von Bedeutung. / Related languages contain words of the same origin. Through time these words change. Remaining similarities between these words can be detected in different languages. In this work, transformations across lexical wordlist are used to model these changes. To reconstruct the possible pathways of language change an algorithm is choosen that calculates the phylogeny, the appropriate protolanguage and the cognate sets. An evaluation function detects plausible evolutions. Because of the enormous amount of possible solutions an approximative method is proposed that continuously modifies and improves possible solutions.

Software-basierte Selbsttest (SBST) Konzepte für Prozessoren werden zunehmend interessant nicht nur durch die At-Speed Test Problematik. Auch bezüglich Stromaufnahme und Testzeit bietet dieses Testkonzept gegenüber dem Standard Verfahren wie etwa Scan-Test Vorteile. Als grundsätzlich problematisch ist die Erzeugung solcher software-basierten Testroutinen anzusehen, da bislang kein geeigneter einheitlicher Entwurfsprozess vorliegt. Deshalb wurde exemplarisch für einen einfachen 16-bit Prozessorkern sowohl eine manuelle rein funktional erstellte SBST und eine automatisch generierte auf Strukturinformationen basierende SBST untersucht um die Möglichkeiten und Grenzen eines solchen Ansatzes aufzuzeigen.

Verwandte Sprachen besitzen Wörter gleichen Ursprungs. Im Laufe der Geschichte ändern diese Wörter ihre Gestalt und lassen sich heute in ähnlicher Form in verschiedenen Sprachen als Kognate wiederfinden. In dieser Arbeit wird ein formales Modell zur Beschreibung dieser Änderungen mit Hilfe von kodierten, lexikalischen Wortlisten entwickelt. Das Modell ist geeignet, automatisch und objektiv die Evolution idealisierter Sprachen mit Hilfe eines Sprach-Phylogeniebaumes abzubilden. Dabei werden die einzelnen Buchstabenveränderungen verwandter Wörter und die rekonstruierten Protoformen untersucht. Insbesondere interessieren solche Buchstabenveränderungen, die für mehrere Wörter einer Sprache synchron stattgefunden haben. Ein weiterer Bestandteil des evolutionären Modells ist die Identifikation von Kognaten, um die möglichen Buchstabenersetzungen zwischen den verwandten Wörtern untersuchen zu können. Für die Rekonstruktion linguistisch plausibler Buchstabenveränderungen und Kognatzuweisungen entlang einer Sprachphylogenie wird ein parsimonisches Kostenmodell verwendet, welches die verschiedenen Sprach- und Transformationsverläufe bewertet. Die Suche nach der plausibelsten Lösung ist NP-vollständig, so dass für den enorm großen Suchraum ein Annäherungsverfahren vorgeschlagen wird. Ausgehend von einer geeigneten Rekonstruktion wird durch sukzessives und minimales Verändern einzelner Transformationen oder Kognatzuweisungen mit Hilfe eines speziell entwickelten Approximationsverfahrens nicht nur eine lokal maximale Lösung, sondern eine global beste Lösung angenähert. Mit dem gewählten umfassenden Ansatz des untersuchten Rekonstruktionsmodells ist eine Sprachentwicklung für kleine Wortlisten in angemessener Zeit berechenbar. Als großer Vorteil ist die Nachvollziehbarkeit aller Einzeltransformationen für den linguistischen Diskurs anzusehen. Insbesonders die Identifikation regulärer Buchstabenersetzungen mit möglicher Interpretation als Lautwandel früherer Sprachen ist hierbei von Bedeutung. / Related languages contain words of the same origin. Through time these words change. Remaining similarities between these words can be detected in different languages. In this work, transformations across lexical wordlist are used to model these changes. To reconstruct the possible pathways of language change an algorithm is choosen that calculates the phylogeny, the appropriate protolanguage and the cognate sets. An evaluation function detects plausible evolutions. Because of the enormous amount of possible solutions an approximative method is proposed that continuously modifies and improves possible solutions.

While semantic web data is machine-understandable and well suited for advanced filtering, in its raw representation it is not conveniently understandable to humans. Therefore, visualization is needed. A core challenge when visualizing the structured but heterogeneous data turned out to be a flexible mapping to Visual Variables. This work deals with a highly flexible, semi-automatic solution with a maximum support of the visualization process, reducing the mapping possibilities to a useful subset. The basis for this is knowledge, concerning metrics and structure of the data on the one hand and available visualization structures, platforms and common graphical facts on the other hand — provided by a novel basic visualization ontology. A declarative, platform-independent mapping vocabulary and a framework was developed, utilizing current standards from the semantic web and the Model-Driven Architecture (MDA). / Während Semantic-Web-Daten maschinenverstehbar und hervorragend filterbar sind, sind sie — in ihrer Rohform — nicht leicht von Menschen verstehbar. Eine Visualisierung der Daten ist deshalb notwendig. Die Kernherausforderung dabei ist eine flexible Abbildung der strukturierten aber heterogenen Daten auf Visuelle Variablen. Diese Arbeit beschreibt eine hochflexible halbautomatische Lösung bei maximaler Unterstützung des Visualisierungsprozesses, welcher die Abbildungsmöglichkeiten, aus denen der Nutzer zu wählen hat, auf eine sinnvolle Teilmenge reduziert. Die Grundlage dafür sind einerseits Metriken und das Wissen über die Struktur der Daten und andererseits das Wissen über verfügbare Visualisierungsstrukturen, -plattformen und bekannte grafische Fakten, welche durch eine neuentwickelte Visualisierungsontologie bereitgestellt werden. Basierend auf Standards des Semantic Webs und der Model-getriebenen Architektur, wurde desweiteren ein deklaratives, plattformunabhängiges Visualisierungsvokabular und -framework entwickelt.

While semantic web data is machine-understandable and well suited for advanced filtering, in its raw representation it is not conveniently understandable to humans. Therefore, visualization is needed. A core challenge when visualizing the structured but heterogeneous data turned out to be a flexible mapping to Visual Variables. This work deals with a highly flexible, semi-automatic solution with a maximum support of the visualization process, reducing the mapping possibilities to a useful subset. The basis for this is knowledge, concerning metrics and structure of the data on the one hand and available visualization structures, platforms and common graphical facts on the other hand — provided by a novel basic visualization ontology. A declarative, platform-independent mapping vocabulary and a framework was developed, utilizing current standards from the semantic web and the Model-Driven Architecture (MDA).:ABSTRACT S. x 1. INTRODUCTION S. 1 2. VISUALIZATION OF STRUCTURED DATA IN GENERAL S. 4 2.1. Global and Local Interfaces S. 4 2.2. Steps of the Visualization Process S. 4 2.3. Existing Visual Selection Mechanisms S. 6 2.4. Existing Visualizations of Structured Data S. 12 2.5. Categorizing SemVis S. 25 3. REQUIREMENTS FOR A FLEXIBLE VISUALIZATION S. 27 3.1. Actors S. 27 3.2. Use Cases S. 27 4. FRESNEL, A STANDARD DISPLAY VOCABULARY FOR RDF S. 31 4.1. Fresnel Lenses S. 31 4.2. Fresnel Formats S. 33 4.3. Fresnel Groups S. 33 4.4. Primaries (Starting Points) S. 33 4.5. Selectors and Inference S. 34 4.6. Application and Reusability S. 34 4.7. Implementation S. 35 5. A VISUALIZATION ONTOLOGY S. 37 5.1. Describing and Formalizing the Field of Visualization S. 37 5.2. Overview S. 37 5.3. VisualVariable S. 38 5.4. DiscreteVisualValue S. 39 5.5. VisualElement S. 41 5.6. VisualizationStructure S. 42 5.7. VisualizationPlatform S. 42 5.8. PresentationScenario S. 43 5.9. Facts S. 44 6. A NOVEL MAPPING VOCABULARY FOR SEMANTIC VISUALIZATION S. 45 6.1. Overview S. 45 6.2. Mapping S. 46 6.3. PropertyMapping S. 47 6.4. ImplicitMapping S. 48 6.5. ExplicitMapping S. 53 6.6. MixedMapping S. 54 6.7. ComplexMapping S. 55 6.8. Inference S. 58 6.9. Explicit Display of Relations S. 58 6.10. Limitations s. 59 7. A MODEL-DRIVEN ARCHITECTURE FOR FLEXIBLE VISUALIZATION S. 60 7.1. A Model-Driven Architecture S. 61 7.2. Applications of the MDA Pattern S. 62 7.3. Complete System Overview S. 71 7.4. Additional Knowledge of the System S. 72 7.5. Comparison to the Graphical Modelling Framework — GMF S. 77 8. VISUALIZATION PLATFORMS S. 80 8.1. Extensible 3D (X3D) S. 80 8.2. Scalable Vector Graphics (SVG) S. 81 8.3. XHTML + CSS S. 82 8.4. Text S. 82 9. OUTLOOK AND CONCLUSION S. 84 9.1. Advanced Mapping Vocabulary S. 84 9.2. Reusing Standardized Ontologies S. 84 9.3. Enabling Dynamic, Interaction and Animation S. 84 9.4. Implementation and Evaluation S. 85 9.5. Conclusion S. 85 GLOSSARY S. 86 BIBLIOGRAPHY S. 87 A. S. 90 A.1. Schemata S. 90 / Während Semantic-Web-Daten maschinenverstehbar und hervorragend filterbar sind, sind sie — in ihrer Rohform — nicht leicht von Menschen verstehbar. Eine Visualisierung der Daten ist deshalb notwendig. Die Kernherausforderung dabei ist eine flexible Abbildung der strukturierten aber heterogenen Daten auf Visuelle Variablen. Diese Arbeit beschreibt eine hochflexible halbautomatische Lösung bei maximaler Unterstützung des Visualisierungsprozesses, welcher die Abbildungsmöglichkeiten, aus denen der Nutzer zu wählen hat, auf eine sinnvolle Teilmenge reduziert. Die Grundlage dafür sind einerseits Metriken und das Wissen über die Struktur der Daten und andererseits das Wissen über verfügbare Visualisierungsstrukturen, -plattformen und bekannte grafische Fakten, welche durch eine neuentwickelte Visualisierungsontologie bereitgestellt werden. Basierend auf Standards des Semantic Webs und der Model-getriebenen Architektur, wurde desweiteren ein deklaratives, plattformunabhängiges Visualisierungsvokabular und -framework entwickelt.:ABSTRACT S. x 1. INTRODUCTION S. 1 2. VISUALIZATION OF STRUCTURED DATA IN GENERAL S. 4 2.1. Global and Local Interfaces S. 4 2.2. Steps of the Visualization Process S. 4 2.3. Existing Visual Selection Mechanisms S. 6 2.4. Existing Visualizations of Structured Data S. 12 2.5. Categorizing SemVis S. 25 3. REQUIREMENTS FOR A FLEXIBLE VISUALIZATION S. 27 3.1. Actors S. 27 3.2. Use Cases S. 27 4. FRESNEL, A STANDARD DISPLAY VOCABULARY FOR RDF S. 31 4.1. Fresnel Lenses S. 31 4.2. Fresnel Formats S. 33 4.3. Fresnel Groups S. 33 4.4. Primaries (Starting Points) S. 33 4.5. Selectors and Inference S. 34 4.6. Application and Reusability S. 34 4.7. Implementation S. 35 5. A VISUALIZATION ONTOLOGY S. 37 5.1. Describing and Formalizing the Field of Visualization S. 37 5.2. Overview S. 37 5.3. VisualVariable S. 38 5.4. DiscreteVisualValue S. 39 5.5. VisualElement S. 41 5.6. VisualizationStructure S. 42 5.7. VisualizationPlatform S. 42 5.8. PresentationScenario S. 43 5.9. Facts S. 44 6. A NOVEL MAPPING VOCABULARY FOR SEMANTIC VISUALIZATION S. 45 6.1. Overview S. 45 6.2. Mapping S. 46 6.3. PropertyMapping S. 47 6.4. ImplicitMapping S. 48 6.5. ExplicitMapping S. 53 6.6. MixedMapping S. 54 6.7. ComplexMapping S. 55 6.8. Inference S. 58 6.9. Explicit Display of Relations S. 58 6.10. Limitations s. 59 7. A MODEL-DRIVEN ARCHITECTURE FOR FLEXIBLE VISUALIZATION S. 60 7.1. A Model-Driven Architecture S. 61 7.2. Applications of the MDA Pattern S. 62 7.3. Complete System Overview S. 71 7.4. Additional Knowledge of the System S. 72 7.5. Comparison to the Graphical Modelling Framework — GMF S. 77 8. VISUALIZATION PLATFORMS S. 80 8.1. Extensible 3D (X3D) S. 80 8.2. Scalable Vector Graphics (SVG) S. 81 8.3. XHTML + CSS S. 82 8.4. Text S. 82 9. OUTLOOK AND CONCLUSION S. 84 9.1. Advanced Mapping Vocabulary S. 84 9.2. Reusing Standardized Ontologies S. 84 9.3. Enabling Dynamic, Interaction and Animation S. 84 9.4. Implementation and Evaluation S. 85 9.5. Conclusion S. 85 GLOSSARY S. 86 BIBLIOGRAPHY S. 87 A. S. 90 A.1. Schemata S. 90