Bachelor and Master Theses

• Master theses
• Bachelor theses

Master theses

2026

• Aaryan Bhandari
  Content Style Transfer using RAG  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Retrieval-Augmented Generation (RAG) pipelines are traditionally used to augment Large Language Models (LLMs) with external, factual knowledge. However, their potential applications in Content Style Transfer , the process of preserving a message’s meaning while adapting it to different style attributes remain largely unexplored. This thesis explores In-Context Learning by dynamically retrieving stylistic context, allowing the model to adapt to an author’s unique text style without the need for computationally expensive fine-tuning. Using a subset of the Enron email corpus, we establish an experimental setup that compares two reconstruction pipelines against original ground truth emails. The first, a Vanilla Pipeline, reconstructs emails using only the de-stylised semantic content. The second, a RAG Pipeline that induces style with retrieved relevant historical emails and stylistic attributes such as lexical preferences and syntactic structures extracted from the author’s historical writing. We evaluate these pipelines using an LLM-as-a-Judge framework, measuring Style transfer accuracy, content preservation and naturalness of the generated text. The research further validates this approach through a user study, in which participants generate emails using the pipeline and rate them based on three core metrics (Style Transfer, Meaning Preservation and Naturalness) for a specific recipient. The results demonstrate that RAG-driven stylistic augmentation markedly improves the Style Trans- fer that standard models often fail to capture. This work demonstrates that retrieval mechanisms can effectively condition generation on user specific stylistic preferences, extending their applicability beyond factual grounding. The code for experimentation with the Enron dataset and the web application for the user study is publicly available at https://github.com/BebopCode/content-style-transfer-using-rag.
• Shantini Malarvizhi
  Enhancing Retrieval and LLM Understanding of Structured Data for Financial Table Question Answering  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Though the recent advances in Retrieval-Augmented Generation (RAG) and Large Language Models (LLMs) have improved reasoning over structured data, there are still challenges in retrieving and interpreting information from heterogeneous and multi-table datasets, especially in the financial domain. This thesis examines three retrieval strategies for tables and different generation techniques using LLMs within a unified RAG-based Table QA framework. In the table retrieval stage, a SPARQL-based hybrid approach that combines retrieval over RDF-based knowledge graphs using SPARQL queries with semantic similarity filtering via FAISS vector search is proposed. On top of this, the study also compares BM25 retrieval and embedding-based retrieval methods across various table representations, such as linearized and context-augmented formats. In the generation stage, LLMs are evaluated for their ability to understand and reason over retrieved tabular data, which are presented in formats like HTML, Markdown, Plaintext, and RDF triples. In addition, different prompt designs for LLMs were experimented with to enhance the reasoning performance. Experiments show that retrieval performance strongly depends on the choice of table representation, retrieval model, and dataset characteristics. Using tables in plaintext format, our dense retrieval approach improves Average Recall@30 by approximately 7–10% compared to the TableRAG baseline across finance and open-domain datasets. Furthermore, the SPARQL-based hybrid retrieval method supports fine-grained retrieval using RDF triples and achieves comparable or better performance, especially for questions involving multiple tables. Finally, the answer generation step results show that retrieval-augmented prompting with tables or RDF triples significantly improves LLM accuracy compared to zero-shot prompting. We also find that presenting tables in Markdown or HTML format improves LLM performance, and the effective prompt design further enhances the results of the GPT-4o model by placing the context before instructions and adding few-shot examples for RDF triples. Overall, using the best-performing LLM and prompt design for each dataset leads to significant improvement over the TableRAG baseline.

2025

• Mahmoud Khalaf
  An Efficient Query Planner for the QLever SPARQL Engine  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Handling increasingly complex queries is not only expectation, but the main prerequisite for any robust modern relational database management system. As extracting any meaningful insight requires interacting with dozens and dozens of relations in a single query. Having a domain expert synthesize a hand-crafted query in SPARQL is considered the exception and not the rule, as the vast majority of the queries in the modern day and age are machine-generated using high-level frontends, dashboards and business intelligence tools. Synthesizing a good concrete execution plan is the relational database management system’s Query Planner require joining multiple relations. the Join order of the relations involved drastically affect the quality of the final plan. Optimal Join Order of a set of relations can be formulated as an NP-Hard Optimal Scheduling problem [1]. the same approaches, techniques and methodologies will be repurposed for our intended use case. Exploring the search space of all possible plans while constrained by a reasonable time frame and a computational budget heavily relay on using estimation techniques to guess plan cost and using clever heuristics to prune the search space. This thesis will mainly focus on Join Ordering techniques capable of synthesizing efficient query plans where relatively large number of relations are involved in polynomial time complexity.
• Tanmay Garg
  Enabling Automated Setup and Evaluation of SPARQL Engines through Unified Benchmarking Infrastructure  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Knowledge graphs provide a structured way to represent the growing volume of web data by organizing information into entities and the relationships between them. They are typically expressed in the Resource Description Framework (RDF), where knowledge is stored as subject-predicate-object triples that capture facts about the world. SPARQL engines enable efficient management and querying of these graphs, but they vary widely in their architecture, storage models, indexing strategies, and query optimization. This variation makes it essential to identify engines that deliver both strong current performance and effective scalability as data and query demands grow. In this thesis, we present a unified and extensible framework for benchmarking and evaluating seven SPARQL engines: QLever, Virtuoso, Blazegraph, Apache Jena, Oxigraph, GraphDB, and MillenniumDB. The framework allows setup of SPARQL endpoints for all supported engines using uniform, simple commands that work with both containerized environments and pre-installed native binaries, without having to worry about internal engine-specific details. A single configuration file, the Qleverfile, ensures consistent and reproducible setup across engines and datasets. The framework supports execution of benchmark queries with structured output that records runtimes, result sizes, and benchmark metadata. We also develop an interactive web application that automatically consumes the benchmark results, enabling comparisons across engines at both aggregate and per-query levels. We use the framework to evaluate the seven engines on various synthetic and real-world benchmarks at three scales: small (∼50M triples), medium (∼500M triples), and large (∼8B triples). The experiments show how the framework simplifies setup, ensures reproducibility, and provides actionable insights into performance, scalability, and correctness of SPARQL engines. All software and materials to reproduce the evaluation are publicly available at https://github.com/ad-freiburg/sparql-engine-evaluation-tanmay.
• Jonathan Zeller
  Implementing efficient geo queries for the SPARQL engine QLever  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  In this thesis the SPARQL engine QLever was extended by a SpatialJoin operation. The SpatialJoin operation receives two SPARQL subresults as input. Each input contains, among other things, geometries. Then, each pair of geometries is added to the result if and only if the distance between these two geometries is smaller than a user-defined limit. The SpatialJoin operation is implemented using R-trees to achieve fast runtimes. The algorithm has been evaluated on two datasets and compared to a baseline solution. In addition, a detailed theoretical analysis was performed, including a correctness proof of the algorithm.
• Cora Hartmann
  Improving the Explainability of Graph Neural Networks for Power Grid Topology Error Identification  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Accurate power grid models are essential for a successful energy transition. These digital twins of the physical grid enable advanced simulation and analysis for optimized grid planning and operation. Currently, maintaining an accurate model of the distribution grid involves time-consuming and error-prone manual work due to frequent changes in the underlying topology. To address this challenge, the Fraunhofer Institute for Solar Energy Systems ISE developed a Graph Neural Network (GNN) to detect errors in distribution grid models. However, the difficulty to retrace how an AI model arrived at a conclusion restricts its application in the critical power industry. In this Thesis, we investigate and improve the explainability and trustworthiness of this GNN using three complementary approaches: confidence calibration, model visualization, and explainable AI. Confidence calibration ensures that the model’s prediction scores represent the probability of the prediction’s correctness. Model visualization provides insights into the internal representations of the models. Explainable AI methods offer interpretable explanations for the model’s predictions. We show that the GNN underestimates the probability of its correct predictions. We improve the calibration with histogram binning and temperature scaling. Our visualizations of the GNN with dimension reduction methods reveal clusters determined by topographical proximity and erroneous nodes. We categorize and analyze explanation subgraphs, identifying patterns in explanations for incorrectly classified nodes. We also quantitatively analyze the explainability of correctly and incorrectly classified nodes. Additionally, we enhance the GNNs loss function with an explainability term which improves the explainability while maintaining model performance. These methods make GNNs for grid topology error identification more accessible to the energy systems industry, addressing the needs of modern smart grids.
• Robin Textor-Falconi
  Lazy Evaluation of SPARQL Queries with Caching  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  QLever is a SPARQL engine capable of computing queries with results of billions of triples fast and efficiently. This is mainly because the operations’ computations are almost exclusively done in memory. However, there are many cases where QLever has larger memory requirements than conceptually necessary. This work implements a new system that allows operations to perform their computations on partial results one after another to reduce the memory requirements up to an order of magnitude with minimal impact on performance while keeping some of the key benefits of the existing caching mechanism.
• Nicolas von Trott zu Solz
  Live Updates for SPARQL Endpoints Containing OpenStreetMap Data  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  OpenStreetMap (OSM) is a collaborative project that provides free and editable geospatial data worldwide. Representing OSM data in knowledge graphs based on the Resource Description Framework (RDF) enables the execution of expressive queries via the SPARQL query language. However, keeping such endpoints synchronized with OSM’s rapidly evolving planet-scale data is computationally demanding. This thesis introduces osm-live-updates (olu), a tool that generates SPARQL update operations from OSM change files, enabling efficient and near real-time updating of OSM data on SPARQL endpoints. When paired with a high-performance SPARQL engine like QLever, olu can generate SPARQL update operations from minute-level change files for the complete OSM Planet dataset in under 7 seconds on average, while ensuring the geometries of all OSM elements on the SPARQL endpoint remain correct. The tool is open-source and available on GitHub.
• Johannes Mannhardt
  Natural Entity Typing in Wikidata  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Wikidata is a massive knowledge graph with millions of entities, each associated with multiple types through the properties instance of ( P31 ) and subclass of ( P279). However, it lacks a single, intuitive type for each entity (e.g., “Einstein is a person”, “Germany is a country”, “Mona Lisa is a painting”). To address this gap, we propose a supervised machine learning approach to automate the process of assigning types. Our method first pre-selects valid type candidates from existing properties, then leverages large language models (LLMs) to generate large-scale training data. Various machine learning models, including a Feedforward Neural Network, GraphSAGE, and R-GCN, are used for type prediction. A masking strategy ensures predictions remain within pre-selected types. Results on two human-annotated benchmarks demonstrate the eectiveness of our method in determining an entity’s most natural type, achieving up to 86% top-1 accuracy.
• Swathi Thiruvengadam
  Recognition of Complex Table Structures and Extraction of Tabular Data From Photovoltaic Module Datasheets  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  The growing demand for solar energy in recent times calls for the development of efficient approaches to analyze photovoltaic (PV) module datasheets. Critical technical specifications are documented in these datasheets, which often contain unstructured data with inconsistent formatting that makes automated data extraction challenging. Tables with complex structures containing merged cells and multiple headers result in missing or incorrect data extraction if processed through rule-based systems. This thesis addressed these challenges by proposing a pipeline for accurate recognition of complex table structures and extraction of relevant key data. The proposed pipeline integrates Deep Learning (DL) models capable of Table Detection (TD) and Table Structure Recognition (TSR) with optical character recognition (OCR) to transform PDF datasheets into structured outputs. A transformer-based Detection Transformer (DETR) model was initially trained to localize tables present in documents. This was followed by a second DETR model that was trained to detect rows, columns, merged cells, multi-row/multi-column headers, and other complex structures. An improved canonicalization algorithm was also implemented to process horizontal and dual-axis tables. Post-processing techniques like Naive Bayes classifier and regular expressions pattern matching enabled validation and extraction of relevant data from the datasheets to aid PV module research. Experiments performed on a custom PV module test dataset show that this pipeline significantly outperforms traditional rule-based extraction methods when processing tables with complex structures. The TD model attained an Average Precision (AP50) of up to 89.5%, and the TSR model attained an AP50 of 71.3%. Furthermore, the TSR model obtained a GriTS_Loc (Location Grid Table Similarity) score of 92.18% on complex tables whcih indicates strong performance in locating complex structures such as merged cells and headers. The experiments also showed the pipeline’s robustness to noisy images and layout variations and noted that modifications to the OCR engine and enhancing the canonicalization algorithm could further improve the extraction results. This thesis provides an end-to-end pipeline for accurate and automated large-scale extraction of PV data to support broader sustainable energy initiatives.

2024

• Armin Saur
  Graph Neural Networks for Electrical Grid State Estimation  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Increasing loads on the Low-voltage network (LVN) require constant status checks. The health status of a LVN can be determined using an automated Electrical grid power system state estimation (SE). The reformulation of the State estimation task (SE-task) uses heterogeneous graph concepts. Using Graph Neural Networks (GNNs, applied complex voltage can be gained in spare measured girds. A date-fitting concept is presented, for parsing LVN into a proper data structure. The author presents the GNN GSETR, capable of performing the SE. A great performance of 99 % is reached by GSETR, knowing all power measurements. Moreover, this work demonstrates the robustness of the model. For this purpose, the measured power data is only sparsely available to the model. A 91 % accuracy is achieved, in this second scenario.
• Erik Schill
  Prisma: A prototype for private and offline searching in mbox files  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Although email is an open communication protocol, most email users are locked within the system of a single email provider. In the past it was generally impossible to export email data or move the data to a different provider. This changed in 2019 when the GDPR came into force in Europe. The GDPR grants European citizens the right to export their data from online platforms, and archive it privately offline. Users that export their emails offline need simple to use, open-source, user configurable programs to manage their emails without being restricted to a single provider, while still allowing users to send emails as they choose, using an address and service of their choice. In this thesis, we present Prisma, an open source Thunderbird add-on that leverages the CompleteSearch engine to search in mbox files. We conduct a small user study under Thunderbird users to compare the usability of Prisma and the Thunderbird Global Search and Quick Filters. The results are mixed, but give clear directions to further improve Prisma’s functionality and usability.

2023

• Sambhav Sandeep Shah
  Evaluation of Non-Intrusive Load Monitoring Algorithms on Industrial Load Profiles  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Non-intrusive Load Monitoring (NILM) is a technique to estimate the energy consumption of individual devices from their aggregated consumption. Using NILM can help in making energy management more efficient, leading to energy savings and thereby, saving costs associated with energy. Most of the research in NILM has been done in residential settings. This thesis makes a contribution to address this shortage in research of NILM in industrial settings. We have performed a comparative analysis of different deep learning algorithms on datasets from two German factories. Our investigation shows that the BERT algorithm performs the best on all the devices used for the analysis. We also find out that using reactive power along with active power as input features improves the results. We also make an extensive comparison of the performance of NILM algorithms using combinations of various sample rates and sequence lengths. The results indicate that there is no universal optimal sequence length and it varies according to the choice of sample rate. We also test the transferability of the CNN-based Sequence-to-Point algorithm to verify if the learnings from one device can be transferred to another device in the same factory.
• Muhammad Moeez Malik
  Extraction of Solar Cell Data from PDF Datasheets  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Tables in data sheets contain the most critical information. Due to variability in design of data sheets, computers cannot readily process and extract data from them. In this thesis, an end-to-end pipeline is presented that aims to extract solar cell data from tables in PDF data sheets. The approach is divided into three major parts. Firstly, the table containing areas of the data sheets are detected using deep learning based object detectors. Secondly, the raw values contained in the tables are extracted using off-the-shelf table extraction utilities. Finally, the raw values are structured and validated using a combination of machine learning and rule-based methods. The complete pipeline achieved 99.86% precision and 94.9% recall performance at extracting electrical and thermal characteristics from solar cell data sheets.
• Rachana Niranjan Murthy
  Fine-tuning NER models for Information Retrieval in the Materials Fatigue domain
  » Abstract anzeigen « Abstract verbergen
  Abstract

  The gradual and progressive weakening of a material over time due to repeated cyclic loading and unloading in the materials domain is a very valuable data to gather since it results from expensive experiments. The industry expresses consistent concerns about the potential failure of metallic structures due to wear, fatigue, and component design. Due to the microstructure sensitivity of the material’s response to fatigue and its probabilistic character, a large quantity of material data is necessary to capture the relevant dependencies. To effectively extract this domain-specific data, Natural Language Processing (NLP) tasks such as Named Entity Recognition (NER) utilize language models. It is important to note that general language models lack the knowledge required to effectively recognize domain-specific entities. To effectively extract, manage, semantically annotate, and link entities in this field, it often becomes necessary to create customized domain ontologies, which can help to organize the heterogeneous data. Utilizing the classes introduced in our domain ontology, a NER dataset was generated. In this thesis, we explore the necessity of a domain-specific NER model and analyze the performances of different language models on a distinct domain dataset. Additionally, we perform parameter-efficient fine-tuning (PEFT) to overcome the costly and practically infeasible fine-tuning of larger language models, with limited hardware resources and in an affordable period of training duration.
• Alharjas Algdairy
  Scriburg: A Configurable Preferential Web Search Engine  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Online content analysis is crucial in making informed decisions in today’s business landscape. However, existing solutions in this space are often proprietary, needing more transparency in their code and flexibility for customization and scalability. In this thesis, Scriburg is introduced, a prototype for a large-scale search engine that can be configured to suit specific user preferences. Scriburg has been developed to crawl efficiently and index web content, offering a range of settings through a user- friendly interface. The system is designed to handle small and large websites, making it adaptable to various scenarios. Scriburg is particularly well-suited for situations where users have a specific interest in a subset of the web, such as a particular domain or a select group of web pages. Despite the significance of web search engines, there remains a need for further academic research focused on developing and designing open-source search engine solutions that can be easily used and extended by a wide range of users.

2022

• Iradj Solouk
  Conversion of OSM data to RDF Data and the use of Simplified Geometries when computing Spatial Relations  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  An OSM-data processing tool, which outputs RDF data, will be introduced. To achieve that a custom parser, specialized in the way OSM-data is represented, is used. The requirement of processing large OSM-data sets encourages the use of on-disk processing data structures. The rules of the conversion are presented in this work. For this, the underlying structure of OSM was taken into consideration. The tool uses clustering and geometric analysis to infer additional data from the input. Furthermore simplified polygons are used in order to infer spatial relations as the containment relation. Those simplifications are computed with a modified Ramer-Douglas-Peucker algorithm. The efficient computation of the spatial relations is done via an RTREE and a directed acyclic graph.
• Rohit Kerekoppa Ramesha
  Detection Of High Energy Consuming Appliances’ Load Profiles Using Non-Intrusive Load Monitoring  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Non-intrusive load monitoring (NILM) is the process of using the energy consumption of a house as a time-series, which is the sum of the consumptions of the individual appliances to predict the individual appliance’s consumption time-series. The goal of this thesis is to predict the load profiles of high energy consuming appliances such as electric vehicle chargers and heat-pumps using the overall energy consumption time-series of a house. NILMTK is an open-source toolkit for comparative analysis of NILM algorithms across various datasets. Different deep learning algorithms are compared using NILMTK on both a synthetic and real dataset. The Seq2point algorithm outperformed the other deep learning algorithms in most houses of both datasets. Additional weather data improved the performance of the Seq2point and BERT models in predicting energy consumed by heat-pumps. This additional data also helped in improving the performance of the Seq2point algorithm in predicting energy consumed while charging an electric vehicle. Converting the BERT and Seq2point algorithm into a multi-output algorithm resulted in only a small decrease in performance. These multi-output models can be used in order to save time since one model can predict more than one appliance at a time.
• Sneha Senthil
  Energy Price Forecasting with Uncertainty Estimation  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Forecasting is the task of predicting future values, taking into account historical data. We forecast energy prices taking into consideration load, generation, historical prices and weather data. This thesis aims to solve this task using a Transformer model. While Transformers are typically used for NLP tasks, there have recently been some successful applications of Transformers for forecasting. In addition to predicting the prices, we try to estimate the uncertainty of this prediction by probabilistic forecasting. We experiment with different types of distributions and determine which distribution would be the best for probabilistic forecasting. We also study how probabilistic forecasting affects the model’s results compared to deterministic forecasting. We find that Transformers outperform other deep learning models. Additionally, probabilistic forecasting helps improve the accuracy in some cases and is helpful in understanding the uncertainty in the model’s prediction.
• Amund Faller Raheim
  Joint Entity Linking with BERT  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Entity Linking aims to connect mentioned names in a text to unambiguous entities in a knowledge base. State-of-the-art approaches are deep neural network models based on one or more instances of BERT. With the use of a Candidate Generation step between Mention Detection and Entity Disambiguation, these approaches tend to break the end-to-end capabilities of training deep neural networks. This thesis aims to investigate an end-to-end approach that combines Mention Detection and Entity Disambiguation in a single BERT-based model. We find that we are able to reach near state-of-the-art performance, but that we are unable to reproduce previous results with a similar approach.
• Sebastian Walter
  Transformers and Graph Neural Networks for Spell Checking  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Spell checking is a general term for methods that detect or correct spelling errors in natural language text. Such methods can not only help with correcting human written text, they can also improve the performance and robustness of natural language processing systems dealing with misspelled text, when applied as a preprocessing or postprocessing step. We study the usage of Transformers and graph neural networks for spelling error detection on sequence and word level, as well as spelling error correction. We show that open vocabulary sequence-to-sequence Transformers can perform well for spelling correction. We also experiment with ways to represent text not as sequences of tokens, but rather as word graphs to be processed with graph neural networks. As a simple way to boost spelling error detection performance we propose to enrich misspelled input texts with additional word features. Our models perform better than most of the strong baselines for both artificially generated benchmarks and benchmarks built from real data. They achieve word accuracies of over 98% for word-level spelling error detection and F1 scores of over 80% for spelling error correction, while running fast enough to be used in practice.
• Tanyu Tanev
  Two-step OCR Post-correction with BERT and Neural Machine Translation models  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Optical Character Recognition (OCR) is a process, which transforms images (scans) of PDF documents into actual text. This allows, among other things, for historical documents to be digitalized, archived, and made available for researchers to use for further processing. Modern OCR systems, however, produce errors when reading the texts of historical documents due to a number of reasons — degraded quality of the document, archaic forms of words, unknown fonts and so on. In order to make up for this loss of information, Post-OCR correction can be employed to transform the erroneous text back into its original form. This paper evaluates the performance of a “two-step” approach on the task of Post-OCR correction — using BERT for error detection and marking OCR errors — optionally with context tokens around them — and sequence-to-sequence models for correcting them. In particular, it researches how viable this approach is when compared to the tradition “one-step” sequence-to-sequence method, which involves just running a sequence-to-sequence model on parts of the whole sequence. Furthermore, the paper also offers in-depth statistics of popular Post-OCR correction benchmark datasets, alongside introducing some new ones. A procedure is outlined, which can harness the aforementioned statistics, in order to build an arbitrary amount of artificial data. Although the two-step approach massively improves on the baseline method, it achieves very underwhelming results when compared to the state-of-the-art models from wide-known competitions. This is due to the error detection part becoming the bottleneck of the approach, essentially putting a cap on how good this approach can function based on how many samples the detection model actually marks right. The paper discusses the shortcomings of this approach and gives ideas on how it can be improved in the future.

2021

• Axel Lehmann
  Creating a RDF Knowledgebase from OpenStreetMap Data  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  We present osm2ttl, a tool for converting OpenStreetMap data into valid RDF data for use in SPARQL engines. The output we generate retains all data provided by the OpenStreetMap, and we add some explicit spatial relations ogc:intersects, ogc:contains, ogc:intersects_area, and ogc:contains_area. The spatial and non-spatial data stored in the OpenStreetMap is curated by volunteers providing mostly accurate and recent data. The internal representation of non-spatial data can not enforce certain data types, formats, or the use of special characters and thus all data is treated as text. To conform with the rigid grammars of the RDF standard, we implemented conversions into both the N-Triple and Turtle grammar. The ogc:intersects_area and ogc:contains_area describe the spatial relation of named areas with other named areas. ogc:intersects and ogc:contains describe the spatial relation of all other types with named areas. To generate these relations more efficiently, we use a directed acyclic graph storing named areas. Through the addition of these elations, a SPARQL engine without explicit GeoSPARQL support can answer spatial queries.
• Johannes Kalmbach
  Effcient SPARQL Autocompletion on Large Knowledge Bases  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  We describe an autocompletion system, that is able to help users formulate complex SPARQL queries on large knowledge bases. As the user types a SPARQL query, they are presented with suggestions for the entity that is currently under the cursor. These suggestions are context-sensitive. This means that they form a useful continuation to the part of the query previously typed. We obtain these suggestions by executing special SPARQL queries which we call autcompletion queries (AC queries). We formalize this setting as the SPARQL Autocompletion via SPARQL problem. We describe a template-based approach that allows the automatic generation of the AC queries. This approach can easily be adapted to a wide range of knowledge bases. We provide technical improvements to the QLever SPARQL engine that allow us to efficiently process the AC queries. We also provide an extensive evaluation of our setup using multiple knowledge bases and query engines. This evaluation shows, that context-sensitive autocompletion leads to significantly better suggestions than alternative approaches which do not consider the context. We also show that our improved version of QLever is able to process 90% of a diverse set of context-sensitive AC queries in less than 1 second even on the large Wikidata knowledge base (6.9 Billion statements). This makes our approach feasible for a pratical user interface because the high-quality context-sensitive suggestions can be presented to the user interactively as they type.
• Lukas Gebhard
  Expansion Planning of Low-Voltage Grids Using Ant Colony Optimization  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  The decarbonization of the energy sector necessitates a large-scale expansion of low-voltage (LV) grids. Yet, such expansion is expensive and increasingly difficult to plan, particularly in face of the rising number of distributed energy generation facilities and the electrification of the transportation sector. To assist utilities in the planning of electricity grids, scholars have proposed a variety of tools that automatically search for optimal grid expansion strategies. Tools that implement ant colony optimization (ACO), a heuristic framework for the solution of combinatorial optimization problems, rank among the best. Nevertheless, only few researchers have studied the application of ACO to LV grid expansion planning; and existing research neglects the cost savings potential of combining conventional power line expansion with a reconfiguration of power switches. To fill this gap, I present AntPower, a tool that searches for a minimum cost strategy to expand a given LV grid, subject to topological and electrical requirements that are common in Europe. Unlike existing tools, AntPower integrates the installation, reinforcement, and dismantling of power lines with an optimization of power switch settings. For evaluation, I consider the case of expanding a heavily overloaded grid that powers an 800-inhabitant village in rural Germany. The expansion plan generated by AntPower is by 60% cheaper than an expansion plan obtained through conventional, manual planning based on expert knowledge, and is by 64% cheaper than the expansion plan generated using a local search algorithm. Finally, a sensitivity analysis indicates that AntPower is robust against changes in most of its parameters; and for the sensitive parameters, good default values exist.
• Yi-Chun Lin
  Named Entity Recognition and Disambiguation with Wikidata on Arbitrary English Text  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Named entity recognition and disambiguation (NERD) is the task of identifying and determining the meaning of named entities in a given text, for example, to tell whether the word "Amazon" is referred to the company or the river. This is done by linking the text spans to their corresponding entities in a knowledge base. NERD is an essential technique in many NLP applications including recommendation system and question-answering system, as it helps to extract and understand information from plain text. The task is however challenging, because the same piece of text can refer to different entities and the same entity can be referred to in multiple ways. In addition, the variety of texts – length, topic, style – also increases the difficulty of recognition and disambiguation. In this thesis, we propose an algorithm with configurable features for the task of NERD with Wikidata. In the recognition stage, we examine all possible text spans in the pre-generated named entity index, while reducing the complexity to linear scale by utilizing POS tags as a filter. In the disambiguation stage, we consider the popularity of each candidate entity and its similarity to the context. On top of the base model, we give the algorithm more flexibility in recognition by expanding the synonyms of certain named entities, and leverage Wikipedia abstracts to enrich the knowledge base. We further discard unlikely named entities to decrease false positives. In evaluation, we analyze the contribution of each component as well as the entire NERD system. Results show that synonym expansion and false positive reduction are very effective. In addition, our algorithm performs better and is capable of outputting more named entities on one dataset with shorter documents. On the other dataset consisting of news articles with rich context, our performance is also acceptable in comparison with the other sophisticated system.
• Thomas Götte
  Simple Question Answering over Wikidata  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Question Answering over Knowledge Bases (QAKB) aims to extract the answer to a natural language question from a Knowledge Base. We approach this task for the Knowledge Base Wikidata by translating a natural language question into its corresponding SPARQL query which returns the answer to the question. Our focus is on simple questions which means that the corresponding SPARQL query contains only one triple. We provide a modular, easy-toextend QA pipeline and evaluate it on the SimpleQuestionsWikidata benchmark. With it, we also provide an evaluation web tool which enables analyzing evaluation results of the pipeline.

2020

• Armando Miguel Garcia
  Conception, Implementation and Evaluation of the Safety-Critical Application „Intersection Movement Assist (IMA)” Based on Simulation and C-V2X Experimental Vehicles  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Intersections make the flexible shaping and connection of our roads possible. Though accident statistics show that passing through an intersection is not a trivial task for vehicle drivers, as the majority of vehicle accidents happen inside or near to an intersection. This challenge becomes even greater, when the visibility of drivers is hindered due to weather conditions or obstacles, as for example buildings or other vehicles parked near to an intersection. One of the groups of road users that is especially threatened, even under normal road conditions, are the motorcycle riders. These often face the risk of being overlooked or misjudged by vehicle drivers. The development of Advanced Driver Assistance Systems (ADAS) intends to solve this problem by extending the senses and capabilities of drivers, with the goal of reducing the probability of overlooking or misjudging other road users. One of the technologies to still be exploited in this field is Vehicle-to-Vehicle (V2V) communication. This technology relies on a wireless, non-line-of-sight dependent communication between vehicles, in contrast to existent ADAS solutions, which use conventional sensors for gathering information about their surroundings. Of course, the application of such a technology for avoiding collisions at intersections is accompanied by several challenges and questions: Which properties should have such an application? Which one is the best approach for the prediction of collisions? How precise must be satellite navigation devices so that the application provides an acceptable prediction? Can we rely exclusively on the V2V-communication for issuing warnings to the drivers? Are intelligent traffic lights and map data needed for such an algorithm to work acceptably? To answer these questions within this thesis, the whole process from drafting a V2V-version of the applications Intersection Movement Assist (IMA) and Left Turn Assist (LTA) until the validation using prototypes, takes place. This process includes the writing of an extensive concept for these applications, the development of four different approaches according to the most recent industry standards, and the implementation and comprehensive evaluation of those approaches in both a modern simulation environment and cutting-edge prototype vehicles. The obtained results demonstrate the great potential of V2V-communication for aiding vehicle drivers at intersections and thus preventing road accidents. Those also evince the strengths and weaknesses from each of the four implemented approaches, one of which demonstrated to be the more suitable for the conceived applications. It also becomes clear that map data is necessary for achieving acceptable levels of accuracy and that such an application should be seen as a sensor to be integrated into a larger system, instead of a standalone solution.
• Engy Nasr
  Evaluation of Automatic Ontology Matching for Materials Sciences and Engineering  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  A challenge of managing various amounts and types of data has raised due to the exponential increase in information and communication technologies. Creating strategies for handling those exponentially increased amounts of data using logic, semantics and computers, allowing reasoning between various data entities, is still under progress. Ontologies present a promising solution as a high-level knowledge representation system with strong semantics. Accordingly, institutions develop and establish ontologies according to their needs, resulting in various ontologies created for a specific field by different actors. To enable interoperability between actors and systems, mapping between ontologies is crucial. One way to establish a mapping between different ontologies is ontology matching, where actual relations and alignments between entities of different ontologies are found. As Huschka and Dlugosch have stated, “Digitization is increasingly entering classical engineering disciplines. Especially in the field of materials science, pioneering innovations are characterized by modern methods of data processing”. [1] Many automatic ontology matching tools (matchers) have been introduced, evaluated and approved by the “Ontology Alignment Evaluation Initiative (OAEI)”, recently in the field of Bioinformatics and Biomedical domains. However, until now, there have not yet been evaluations performed for automatic ontology matching (evaluation workflows) for Materials Sciences. Consequently, there is no available benchmark for Materials Sciences ontologies to evaluate the already existing ontology matchers in terms of the Materials Sciences domain. Other domains’ benchmarks cannot be used as Materials Sciences benchmark due to the different concepts represented in different domains’ ontologies. Therefore, in this thesis, creating a Materials Sciences benchmark with test cases, controls and supporting ontologies, and performing evaluations of the existing ontology matchers are crucial for the application of automatic ontology matching in the Materials Sciences domain. The evaluation results have shown that the usage of “LogMap”, an ontology matching tool, is recommended for applications that demand high precision. “Agreement Maker Light (AML)”, another ontology matching tool, provides a background knowledge ontology matcher, which uses the supporting background knowledge ontologies and boosts the number of correct alignments found by the tool. Accordingly, a mature Materials Sciences background knowledge (semantics bridge) ontology is essential in getting more correct and complete alignments. The usage of the property matcher is currently not recommended until it is improved to include logically correct alignments. Finally, the fully automated ontology matching is not achieved since all alignments are only equivalences and no sub or super alignments are detected; accordingly, human interference is also needed because the results are not 100 % correct and complete.

2019

• Ibrahim Alshibani
  A Cryptocurrency Evaluation and Trading System  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Accurately predicting asset prices in a financial market is a very difficult task. This difficulty arises from the large number of real-world factors that drive the price. Often these factors are hard to model or follow a random behaviour. This thesis studies the predictability of a financial market of a new type of asset, cryptocurrencies. We employ two types of approaches to this problem, the first one is based on Technical Analysis. We utilized an approach based on grid search and cross validation to find the best set of parameters for the trading strategies based on technical analysis. This approach was applied to 5 different cryptocurrencies and 7 different trading strategies. All candidate strategies that resulted from the cross-validated grid search method performed well on out-of-sample data, yielding positive returns. The second approach used to tackle the problem was based on computer learning. We fitted historical data for 5 different cryptocurrencies to a Recurrent Neural Network model that uses the Long Short Term Memory (LSTM) architecture. The model was able to achieve limited accuracy improvement over a random classifier by around 5% for 3 out of 5 currencies. Complementary to the first approach, we designed a trading system that enables the user to run trading simulations on historical data, and launch a trading bot to perform automated trading based on a selected trading strategy. By comparing the performance of the trading bot to that of the offline trading simulations, we found that our offline simulation is a realistic approximation to real-world live trading.
• Nishat Fariha Rimi
  Comparative Study of Forecasting Algorithms for Energy Data  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Accurate forecasting data is an important requirement of energy management systems and subsequent decision-making processes to ensure proper balance between supply and demand. The energy industry commonly carries out planning and forecasting of energy consumption for three types of prediction intervals: short-term, medium-term and long-term. The accuracy of a forecast depends on different parameters. Influence of the forecast horizon and the dataset type is significant among them. Often PV generation and electrical load profiles are subject to forecasting. Furthermore, different forecasting methods yield different accuracy. This study aims to identify the most appropriate method for accurately forecasting energy data based on the desired prediction horizon and the type of predicted dataset. The analysed methods include three categories of approaches– statistical, machine learning and deep learning. Statistical approaches include: Autoregressive moving average (ARMA), Autoregressive integrated moving average (ARIMA), Exponential smoothing (ES) and Holt-Winters method (HW). Machine learning approaches are K-nearest neighbor (KNN) and Random forest (RF). From the deep learning approaches, Artificial neural network (ANN) and Recurrent neural network (RNN) have been focused. The forecasting quality for each method was measured using mean absolute error, mean absolute percentage error, root mean squared error, and the correlation coefficient R value. The results suggest that RF and KNN were the most appropriate forecasting algorithms for short-term (daily), medium-term (monthly) and long-term (3 monthly) forecasting horizon for both energy datasets. During the comparisons, these two methods provided higher accuracy and required minimum computational time to forecast among the compared methods. Additionally, ARIMA and ARMA methods performed better for very short-term (hourly) forecasting.
• Sameed Hayat
  De-Identification of free text  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Sharing data in the form of text is important for a wide range of activities but it also raises a concern about privacy when sharing data that could be sensitive. Text-based patient medical records are a vital resource in medical research. Processing of a large amount of medical data can be done in order to derive meaningful statistical information from such data as well as for other research purposes. The use of such data usually imposes problems with privacy of patients’ personally identifiable information. Automated text de-identification is a solution for removing all the sensitive information from documents. However, this is a challenging task due to the unstructured form of textual data and the ambiguity of natural language. In this thesis, we developed two models that use semi-supervised approaches. These approaches use mix of labeled and unlabeled data to remove personal information from the data. First approach uses contextualized characterlevel word embedding trained on large corpus of unlabeled data. This model outperforms the state-of-the-art systems on i2b2 2014 de-identification challenge dataset without using hand-curated feature. This model yields an F1-score of 97.99%, with a recall 97.52% and a precision of 98.46%. Whereas, the second approach uses Cross-View Training (CVT) algorithm, which aims at improving the performance of the model by incorporating unlabeled data. Our results show that this approach can aid in increasing the performance of the model on the de-identification task. This model outperforms the state-of-the-art systems on i2b2 2014 de-identification challenge dataset without using hand-curated feature. Our best performing model yields an F1-score of 97.99%, with a recall 97.52% and a precision of 98.46%. We also showed with our experiments that as the amount of data decreases the performance of semi-supervised approaches grow larger over purely supervised learning approaches.
• Muhammad Hamiz Ahmed
  Meta Data Inference on Building Sensors Data  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Modern buildings are equipped with complex heating, cooling and ventilation sys-tems. In the group "Building Performance Optimization" at Fraunhofer ISE, various methods are investigated for detecting faulty or suboptimal operation of such systems (e.g. simultaneous heating and cooling). These methods require data of a multitude of sensors for input (like temperature, pressure, current etc.). For this, a manual labelling of the sensor is required, which is excessively time consuming. The labelling convention called data point naming convention marks the origin and type of the sensor. Every sensor has recorded time series data as well as a small description text describing the nature of the sensor. In this thesis, we create a supervised machine learning system that utilizes the time series and description text data and automates the labelling of the data point name of the sensor. The proposed system is able to predict with an accuracy of 88% with 218 labels in the dataset, outperforming the baseline score of 76% which only used 81 labels.
• Matthias Hertel
  Neural Language Models for Spelling Correction  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Spelling correction is the task of automatically recovering the intended text froma misspelled text. This enhances digital communication and enables Natural Lan-guage Processing and Information Retrieval systems to work with misspelled text.We propose NLMspell, a spelling corrector based on a neural language model.NLMspell achieves correction F-scores of 91.5 % on artificial misspellings and88.4 % on real misspellings. It outperforms our baselines methods based on tra-ditional language models, as well as our neural machine translation approach tospelling correction, and the commercial product of a large Internet company.
• Theresa Klumpp
  Neural Word Embeddings as Matrix Factorization  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  The problem of finding continuous word vectors is central and well studied in natural language processing (NLP). In this thesis, we consider two neural networks that yield lowdimensional word embeddings: skip-gram and skip-gram with negative sampling (SGNS),0 introduced by Mikolov et al. in [10] and [11]. Assuming the dimension of these word embeddings was large (at least as large as the size of the vocabulary), we show that a different method, namely the factorization of a word-context matrix using singular value decomposition (SVD), also maximizes the objective function of the neural network. Even though we cannot make this link for low-dimensional embeddings, we can still use SVD and show that this method performs even better in some linguistic tasks than the neural network that it stems from. This connection between the SGNS neural network and SVD was presented by Levy and Goldberg in [8]. We analyze the cosine similarity, commonly used in NLP to measure the similarity between word vectors, and we derive a formula that gives us a heuristic understanding of what `close' in Rd is. We compare the different methods for finding low-dimensional word vectors and evaluate them on word similarity and semantic and syntactic analogy tasks. Our data clearly shows that SVD prefers a low number of `negative samples', whereas the SGNS neural network generally performs better for a higher number. Furthermore, the neural network is evidently superior in the analogy tasks, while SVD gains the advantage on word similarity tasks, if the number of negative samples is low.
• Omar Kassem
  Predicting Personalities through Multimodal Signals  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Automatic personality perception is a research area that has recently gained attention from the scientific community due to the wide range of fields that could benefit from personality predictions. The rise of social media platforms is providing access to huge amounts of labelled personality data. The dataset used for this research has been collected from the social media website Youtube. In this thesis, deep neural networks have been used to predict personality from one of three communication modalities: text, audio and images, or combinations thereof. The performance of the different trained models was used to compare the information embedded in each modality with respect to personality. This work’s analysis points to visual information has the most personality content.
• Natalie Prange
  Question Auto-Completion using a Typed LSTM Language Model  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Query auto-completion (QAC) is the task of predicting a user’s query as they type. A QAC system presents completion predictions to the user to ease the process of entering a query. Most approaches to QAC heavily rely on query logs - large collections of queries asked by users in the past. These logs are often used to estimate the probability of a query based on how frequently it occurs in the logs. Major limitations of this approach are the inability to predict queries that have not been asked before as well as the fact that search engines with a small user base or recently deployed search engines usually do not have access to large enough and up-to-date query logs. We therefore explore the possibilities of QAC independent of query logs. For this work, we focus on questions as opposed to queries which are often just fragments of the question a user has in mind. We deploy a typed Long Short Term Memory (LSTM) language model trained on more than 11 million questions. In our language model, we replace concrete entities by abstract types in order to overcome the problem of data sparsity. When predicting a query completion, we insert entities for the types that the language model predicts by using an entity prominence score, co-occurrence between entities and word vector similarity. We evaluate our system over a hand-crafted ground truth of question prefixes and reasonable completions. Additionally, we evaluate our system over three question test sets. We compare several versions of our system. Apart from illustrating the importance of various system components, the results show that using co-occurrence to insert entities is superior to inserting entities purely based on an entity prominence score or word vector similarity.
• Tobias Matysiak
  Tabular Information Extraction  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Searching for content in knowledge bases can involve some challenges, especially for inexperienced users. On the one hand, they need to know the underlying data structure (mostly represented by an ontology), on the other hand, they need to know how to query the knowledge base. This thesis introduces a web application called Knowledge Base Table Extractor (KBTE) that is able to generate SPARQL queries for Freebase and Wikidata back-ends to retrieve information in a tabular form. For this, the thesis provides a simple tabular description format for specifying table definitions like city | country | population as input. KBTE tries to find a table matching which maps each column keyword to a class or property of the knowledge base and relates the columns to each other. Unlike keyword search and question answering approaches, it is not focused on matching entities. The algorithm for table matching exploits the combined use of a search index and a column graph. The search index is used for the mapping part, the column graph is used to find relations between two columns. Furthermore, the thesis provides three datasets for evaluation. One is created from tables of Wikipedia, the other two contain hand-crafted table definitions. The evaluation compares the table matching algorithm used by KBTE with a simple baseline algorithm. The results can confirm the better performance of the former.

2018

• Mostafa M. Mohamed
  Automatic Correction of Misaligned Spaces and Typos Using Deep Learning  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Large text corpora could get corrupted for a variety of reasons, such corruptions could be tokenization corruptions, like removing correct spaces between words, adding wrong spaces in-between words, splitting words across lines or garbling some characters in words. These mistakes could make it hard for systems, that process large text corpora, to identify the words within a text correctly, and as a result, lose a lot of information about the text. This thesis developed a model which utilizes characterbased language models, that are trained as recurrent neural networks via deep learning. The model automatically detects the tokenization mistakes in a given text and fixes them accordingly. The model can successfully classify, and hence fix, the tokenization errors with a mean F1-score that, depending on the model’s specifications, training settings, and evaluation settings, varies between to 81% to 96%. Furthermore, two non-learning dictionary-based approaches are presented, using a baseline greedy strategy and dynamic programming, in addition to an end-to-end deep learning approach and a baseline learning approach using 3-Gram Markov models. The models are trained and evaluated using two datasets: Simple-Wikipedia and Reuters-21578. The presented approaches are empirically evaluated to demonstrate the superior performance of the presented model. Additionally, it is experimented using different RNN architectures, RNN history length, model size, beam size in Beam-search, training data size, tokenization errors and some internal features.
• Bhashitha Gamage
  Automatic Generation of Frequency Maps for Public Transit Networks  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  This thesis addresses the problem of automatically generating the frequency map of a public transit network when given its GTFS [1] data feed. Normally, the drawing of a frequency graph is completely done manually and doing it automatically is extremely complicated. Our approach consists of a few major steps including extraction of the transit graph from the GTFS data, implementation of the frequency finding algorithm, extraction of the frequencies among interested nodes, creation of the frequency lines and finally the drawing of frequency lines and nodes in a convenient way to resemble a schematic map. The last step which is the drawing of a frequency map automatically was the most challenging step, and several approaches experimented until satisfactory results were achieved. We explain each of this steps in detail and discuss how the appeared challenges are solved and overcome in a scientific manner. We tested our approach against several examples GTFS Feeds, evaluated it concerning the running time and the frequency coverage and compared our results to the official, hand-drawn frequency graph published by the Swiss Federal Railways.
• Sumitra Magdalin Corraya
  Dehyphenation of Words and Guessing Ligatures  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  The accurate extraction of text from PDF (e.g. in order to be able to search in it) can prove to be a difficult task as on some occasions long words at the end of the line are split into two words joined with a hyphen. Moreover, PDF contains ligatures (multiple characters, which translate to one/single character in the PDF) that can be hard to search for as well. In this thesis we propose solutions to the aforementioned problems, i.e. deciding if the hyphen (-) in the words is necessary or not, and proposing a method for guessing ligatures by looking up in a large dictionary. In both cases, we try to provide a fast response of time and good accuracy. In PDF, long words can be split into two parts with a hyphen between them, when they do not fit in one line and as a result appear in different lines. The reason for the hyphen is to show that the words had a combined meaning or that there is a relationship between the words (also known as compound words). However, not all compound words need to be hyphenated which can prove to be problematic. This thesis proposes a procedure to decide when to dehyphenate the word. We decide upon the necessity of the hyphen by using the dictionary of words. Our approach provides efficiency and good accuracy, which we demonstrate with different experimental results. During the making of PDF files, some combination of character (ligature) translates to a single character (for example the ligatures: "ffi","ffl" are translated to some special characters). This can be problematic as when the text is extracted from the PDF, e.g. for searching, one wants to extract the individual characters within the word and not the special character. This issue is further aggravated by the fact that PDF has different fonts and encoding. We propose a method for guessing ligatures from such special characters. We do so, by trying different ligatures and searching the formed words in the dictionary. Finally, we also discuss what to do in case of an ambiguity when looking up the word.
• Mohammad Mahadi Hasan
  Efficient Database Model to Represent Numerical Research Data of Material Flow Analysis  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  The research group of Industrial Ecology Freiburg (IEF) produces research results consisting material stock and flow data between industrial sectors and regions. Most of these data are stored in .mat or .csv files on a local machine which makes data accessibility difficult to other users. Usually these datasets are big, and it is difficult to re-generate a specific part (based on specific region or industrial sector) on request from another interested user. An efficient data storing and retrieving mechanism could provide a solution to this problem. While, Relational Databases (RDB) have been meeting this criterion for decades, Triple Store is a new kind of database which has grown in popularity in recent years due to its applications towards Semantic Web Technology which assures that data to be shared and reused. In this thesis, we provide a study on both relational databases and triple stores. We start with constructing a relational database from our dataset and design a web interface so that users can retrieve data by their own. To examine the offerings that triple stores provide us, we design a triple store to store the same dataset. In relational databases where data is stored in relational tables, triple stores store data as semantic triples using the Resource Description Framework (RDF); a semantic web standard for publishing and sharing data on the Web. Therefore, we transform our entire dataset from the relational database to RDF and load into the triple store. Finally, we do the performance evaluation on both database models in terms of query processing time running equivalent test queries. This evaluation also includes the additional offerings triple stores and relational databases provide which summarize the argument to choose more suitable database model for industrial ecology research data.
• Philip Schledermann
  Knowledgebase construction of genetic variants in literature  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  In Publikationen werden oftmals synonyme Begriffe für eine genetische Variation verwendet. Für die verbesserte Suche nach Veröffentlichungen über genetische Variationen in wissenschaftlichen Publikationsdatenbanken wie PubMed und PubMedCentral, sollen die unterschiedlich verwendeten Begriffe auf die präferierte Bezeichnung der jeweiligen genetischen Variation zurückgeführt werden. Mit ClinVar existiert eine manuell kurierte Datenbank, in der die Begriffe welche in Standardnomenklatur geschrieben werden enthalten sind. Um auch Begriffsvariationen zusammenzuführen, welche nicht der Norm entsprechen sollen diese aus den Veröffentlichungen extrahiert werden. Der Text wird mittels Named Entity Recognition und anderen Algorithmen der Sprachverarbeitung vereinfacht. In einem "word embedding"Modell werden aus dem Text Begriffe und ihre Kontexte extrahiert und miteinander verglichen. Gleiche Kontexte für unterschiedliche Begriffe weisen darauf hin, dass es sich bei den Begriffen um Synonyme handeln könnte. Dieses Modell wird auf unterschiedliche Schreibweisen von genetischen Variationen angewandt. Das Modell wird gegen ClinVar evaluiert. Hierbei zeigt sich, dass der überwiegende Teil der normierten Standardbegriffe teils verschwindend gering in der verwendeten wissenschaftlichen Literatur enthalten ist. Zudem zeigt sich, dass das Modell nicht ohne zusätzliche Filterung der Ergebnisse verwendet werden kann.
• Daniel Tischner
  Multi-Modal Route Planning in Road and Transit Networks  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Wir präsentieren Algorithmen für multi-modale Routenplanung in Straßennetzwerken und Netzwerken des öffentlichen Personennahverkehrs (ÖPNV), so, wie in kombinierten Netzwerken. Dazu stellen wir das Nächste-Nachbar- und das Kürzester-Pfad-Problem vor und schlagen Lösungen basierend auf Cover Trees,ALT und CSA vor. Des Weiteren erläutern wir die Theorie hinter den Algorithmen, geben eine kurze Übersicht über andere Techniken, zeigen Versuchsergebnisse auf und vergleichen die Techniken untereinander.

2017

• Johannes Güttler
  Semantische Personensuche auf Hochschulwebsites  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Die Arbeit zeigt wie Personendaten aus einem Webcrawl extrahiert und als Grund-lage für eine Suchmaschine aufbereitet werden können. Es wird vorgestellt, wie sich die Texte deutscher Hochschulwebsites aus einem vorhandenen Webcrawl extrahie-ren lassen. Dazu wird die ungeordnete Menge der Daten mehrerer CommonCrawl-Webcrawls verarbeitet. Mittels Named Entity Recognition werden Personennamen extrahiert und in eine Ontologie überführt. Diese wird mit zusätzlichen Informatio-nen wie zum Beispiel der persönlichen Homepages angereichert. Die Ontologie und extrahierten Websitetexte werden für die Suchmaschine Brocco-li aufbereitet. Sie lassen sich beschränkt auf geografische Gebiete und zusätzlicher Volltextsuche in den Websitetexten durchsuchen. Die Qualität der Ergebnisse va-riiert stark. Sie ist nicht nur von der Art der Suchanfrage abhängig, sondern auch stark von der Darstellung von Personen auf der entsprechenden Hochschulwebsite.

2016

• Tobias Sommer
  Movie Search - Building semantic search queries with suggestions  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  MovieSearch helps with building semantic queries for tasks like ”find movies with Arnold Schwarzenegger where he fights with a sword”. The suggestions by MovieSearch aim to enable the usage of semantic queries. Usability of semantic queries is the main contri-bution of MovieSearch. The tasks of our user study could be successfully answered in 94% of the cases.MovieSearch provides a user-friendly and effective semantic search system for non-experts. Semantic search shall become available for users who have no knowledge about database languages like SPARQL. The interactive query building delivers trace-able results in contrast to natural-language-based approaches with their hidden query building. We build queries by stepwise adding conditions to specify what we are looking for. The conditions consist of facts and plot. MovieSearch implements an approach with those two input categories. Our example task looks for a movie with actor Arnold Schwarzenegger as a fact, and the plot description fights with a sword. MovieSearch enriches the fact options by 3-ary relations. This allows to connect certain fact parts, for example to look for a movie where the actor Elijah Wood played the character Frodo. The results for the queries will be answered by the SPARQL Server provided by [? ].

2015

• Max Lotstein
  Mitigating Feature Exclusion to Improve Hypernymy Recognition  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Hypernymy, which is the sort of relationship exemplified in the pair (dog, animal)when both take their conventional senses, lies at the heart of many applications in artificial intelligence and natural language processing. In this work, I investigate automatic methods of identifying such sense-pairs. Many existing models for this task implement feature inclusion, which is the intuition that senses like dog are semantically narrower than senses like animal in that the properties one can apply to the former can always conceivably be applied to the latter, but not the inverse. Stateof-the-art performance of these models has been limited by the Feature Exclusion Problem, which is that in the sparse feature vectors representing a sense like dog, in which a non-zero feature is interpreted as an applicable one, there are many nonzero features that should also be non-zero in the representation of animal but aren’t. This work begins by exploring in greater detail the nature of this problem before exploring a post-processing technique designed to mitigate it.
• Tobias Faaß
  Ontology-Based Route Queries with Time Windows  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Most of the time we use route planning to get from A to B. However, we can also incorporate stopovers into our route so that we may get things done along the way. A route from A to B via a gas station, for example, is of no use if the gas station is closed upon arrival. As a consequence, the opening hours and the duration of stay become necessary considerations. In this thesis we define an ontology to be a hierarchical structure of groups to serve us as stopovers. We fill this ontology with POI extracted from the open source project OpenStreetMap. Since the extracted POI rarely have attached opening hours, these opening hours must be calculated based on existing ones or defined by hand. To calculate the route along which a sequence of POI groups are visited, we implement known approaches of sequenced route planning and extended them to match the time window requirements. Different test queries were executed on the system. Within a test area of about 25 km, query times under a half second were measured. During these tests, it was discovered that the route starting time influences the running time, which is due to the fact that during the night most POI are closed. The implemented system covering all of Germany can be found at http://panarea.informatik.uni-freiburg.de/osm-search/.
• Fabian Schillinger
  Strukturierte Extraktion von Text aus PDF  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Wissenschaftliche Artikel werden, vor allem in der Informatik, oft online im PDFFormat angeboten. Ein großer Vorteil ist die Plattformunabhängigkeit. Zeichenkodierungen und Schriftarten sind genauso wie Grafiken, Tabellen oder Algorithmen eingebunden. Für einige Anwendungen, wie z. B. die semantische Suche, wird jedoch nur der Informationen enthaltende Fließtext benötigt. Um den Text eines PDFDokuments zu erhalten, bieten viele Anwendungen die Möglichkeit diesen zu extrahieren. Diese Anwendungen haben aber Schwierigkeiten mit Grafiken oder Tabellen, denn diese beinhalten auch Text, der mit extrahiert wird. Weitere Schwierigkeiten für diese Systeme sind z. B. Fußnoten oder mehrspaltige Layouts. Fußnoten können einzelne Sätze, die auf zwei Seiten oder Spalten stehen, unterbrechen. Bei mehrspaltigen Layouts kommt es oft vor, dass die Aufteilung in Spalten ignoriert werden. Um nur den Informationen enthaltenden Fließtext aus PDF-Dokumenten zu extrahieren sind noch weitere Schwierigkeiten zu überwinden. Das hier vorgestellte System schafft es, die meisten dieser Schwierigkeiten zu überwinden und aus wissenschaftlichen Artikeln den Fließtext strukturiert zu extrahieren. Dabei wird das zu untersuchende Dokument in verschiedene Blöcke aufgeteilt. Diese Blöcke werden dann klassifiziert, indem z. B. nach Schlüsselworten wie “Abstract” gesucht wird. Nach und nach werden nicht benötigte Blöcke ignoriert und am Ende nur die benötigten Blöcke ausgegeben. Dabei wird sowohl eine hohe Präzision von mehr als 0,98, als auch eine hoher Sensitivität von mehr als 0,96 erreicht. Der kombinierte F1-Wert liegt bei etwa 0,97. Auf Grund der geringen Komplexität ist auch der Zeitaufwand für die strukturierte Textextraktion gering.

2014

• Niklas Meinzer
  Dynamic Emergency Ambulance Fleet Allocation and Management  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Most countries have implemented some form of Emergency Medical Services (EMS)in order to help people with urgent medical needs. Typically a number of ambulances serve a specific geographic region by responding to emergency calls, treating patients and transporting them to a hospital. Since the number of ambulances is limited and emergency calls need to be responded to quickly by nature, EMSs have to be thoroughly managed and coordinated, which is usually done by human operators in special call centers. In this thesis we model that task and present and compare different strategies which could be employed by an automatic ambulance fleet management system. We show that continuous optimization of ambulance distribution over the region and dynamic reassignment of ambulances to incoming requests can benefit both the patients and, economically, the provider of the EMS.
• Ragavan Natarajan
  Entity Disambiguation using Freebase and Wikipedia  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  This thesis addresses the problem of entity disambiguation, which involves identifying important phrases in a given text and linking them to the appropriate entities they refer to. For this work, information extracted from both Freebase and Wikipedia served as the knowledge base. A fully functional entity disambiguation tool is made available online and the challenges involved in each stages of the development are addressed in this paper. It explains how the phrases in a text are assigned importance measure, both before and after the disambiguation process, based on several studies available in the literature and experimental analysis conducted as a part of this work. Additionally it explains the implementation of the collective-entity-linking algorithm by Han et al.[1] for entity disambiguation. Several highly reusable code have been developed, whose usability extend well beyond the work described here. Stages involved in the development, from parsing the database dump to storing them in a high-speed, memory efficient key-value store are addressed. By means of D3js a JavaScript based vector graphics library for bringing data to life, visualization of the ambiguity tree is provided, which helps the user easily comprehend the results.
• Patrick Brosi
  Real-Time Movement Visualization of Public Transit Data  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  One of the primary challenges in visualizing movement in public transportation networks is handling the amount of data. This becomes particularly difficult when the visualization should be available in real-time and for arbitrary spatial parts of the dataset, for example to provide an interactive live map. The main task is then to reduce and crop the set of trajectories to the parts currently relevant for the visualization. In this thesis, we present an approach that combines static schedule data and real-time delay information into vehicle trajectories that are treated as piecewise linear functions from the time domain to the projected map-plane, allowing for fast interpolation. We introduce a highly efficient server that accepts temporal and spatial boundaries as an input and returns trajectory parts within these limits. We discuss the implementation details, show that our approach scales well and demonstrate that it is able to handle public transit datasets of entire countries. As a client, we introduce a thin vector-layer for map services that can display thousands of (time-lapsed) vehicle-movements at the same time. This thesis also briefly outlines an approach to extract vehicle trajectories from geospatial datasets.
• Eugen Sawin
  Semantic Search with Keyword Queries  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  We present a semantic search concept, which effectively combines the simplicity of keywordbased search with the sophistication of semantic results. Our bootstrapping process is designed to utilize the efficiency and precision of full-text search to provide reliable intermediate results during the retrieval phase. In the second phase, we perform a deep semantic search, based on the previous results for their refinement. The introduced methods include lexical query analysis, ranking and answer selection algorithms and a variety of filtering solutions. We argue that a simple query interface based on keywords is essential to unlock the potential of semantic search technologies and make them accessible for a greater audience. Finally, we provide Pythia – an open source implementation of the two-phase approach – to support further practical research on this topic.

2013

• Cynthia Jimenez Cardenas
  Efficient Multi-modal Route Planning with Transfer Patterns  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  In these days, there is a big interest in route planning systems with different types of transportation. We study a way to efficiently compute optimal paths with real data in a multi-modal scenario considering walking, transit and car. Therefore, we implement Transfer Patterns, which is a state-of-the-art route planning approach. This allows to obtain shortest paths queries within milliseconds. When using a Pareto-cost model various optimal paths are provided for the user. However, the high number of optimal solutions also includes a lot of unreasonable routes, although they are Pareto-optimal. To address this problem, we use a filtering procedure called Types aNd Thresholds (TNT) [10], which provides a both small and diverse set of reasonable optimal paths decreasing the number of transfer patterns and hence resulting in faster query times. To our knowledge this is the first work which realizes the combination of these two approaches (Transfer Patterns with TNT). We present an evaluation on query times of selected optimal paths, which shows different and reasonable route options with an average query time of 14 milliseconds for the Freiburg network.
• Mirko Brodesser
  Multi-Modal Route Planning  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  We examine the computation of optimal paths, which consist of using public transportation, walking and taking a car. A challenge in itself is to determine concise and diverse sets of paths. We consider metropolises like New York, where a fast computation of the paths is difficult. We exemplify that multiple optimality criteria are necessary to obtain diverse sets of paths. This extends the set of optimal paths severely, whereas many paths are similar. To determine concise sets, we study different methods of filtering. We propose a filtering procedure, Types aNd Thresholds (TNT) , which leads to the desired sets. To reduce the high computation times, we introduce several optimality-preserving and heuristic ideas. We experimentally evaluate the found paths with respect to quality and computation time. The experiments show the claimed quality of TNT and that the running time, while accepting a fraction of suboptimal solutions, is in the magnitude of few seconds. We complete the paper by giving an outline of possible improvements.
• Jonas Sternisko
  On Compact Representation and Robustness of Transfer Patterns in Public Transportation Routing  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Transfer pattern routing is a state-of-the-art routing algorithm for public transportation. It allows to answer multi-criteria shortest path queries within a few milliseconds. The algorithm is based on an expensive precomputation of shortest paths between stations. This thesis examines two aspects of transfer pattern routing. The first objective is to find a compact representation of the transfer patterns. We detect redundancy in the transfer patterns and present novel ways to store the information within less memory. The second objective is to analyze the robustness of the transfer patterns towards delay and to answer the question whether the patterns still allow for optimal routing, if the underlying network changes. We address the second question by introducing a framework to evaluate the robustness in networks with different delay scenarios and we present experimental results indicating that transfer patterns are quite robust.

2012

• Ilinca Tudose
  Automatic Population of a Pharmaceutical Company Ontology  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  We have implemented and evaluated a method to populate a company ontology, focusing on hierarchical relations such as acquisitions or subsidiaries. Our method searches for information about user-specified companies on the Internet using a search engine API (Google Custom Search API). From the resulted snippets we identify companies using machine learning and extract relations between them using a set of manually defined semantic patterns. We developed filtering methods both for companies and unlikely relations and from the set of company and relation instances we build this way, we construct an ontology addressing identity matching and consistency problems in a company-specific manner. We achieved a precision of 77 to 93 percent, depending on the evaluated relations.
• Dirk Kienle
  Efficient Multi-Modal Route Planning  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  We present our system for computing shortest paths from A to B where we combine two types of networks: The road network and the public transportation network. The result is a multi-modal network where we are able to state a source and target address together with a date and a departure time and the system returns optimal paths that show us what roads to use and which vehicles to take. Modeling the timetable information concerning the public transportation network, we use the time-expanded and the time-dependent approach. The main goal of this thesis is to analyze both approaches concerning the computation of the shortest paths and to evaluate the performance of both using bi-criteria optimization. Therefore, in both approaches we do not only minimize the travel time but also the number of transfers. Thus, we get several optimal solutions in order to get from A to B. For example, consider two optimal and incomparable paths where for the first we need 30 minutes and 2 transfer and for the second 45 minutes and only 1 transfer. As it depends on the customer which of the paths is preferred, we present both as optimal solutions. Comparing the efficiency of both approaches, we also minimize in combination with the number of transfers walking between and to stations. It turns out that the time- dependent approach is about four times faster in average when we only use travel time and the number of transfers as criteria costs. But with the additional option of minimizing walking the difference becomes smaller.
• Manuel Braun
  Multi-Modal Route Planning with Transfer Patterns  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  We examine a way to extend routing using transfer patterns – a state of the art route planning approach for fast routing in public transportation networks – to a multi-modal scenario that allows using public transport, cars, and walking. We specifically examine how to precompute transfer patterns for multi-criteria, multi-modal route planning. When done naively with a Pareto cost model, this leads to a large number of undesirable route variations that render precomputation computationally infeasible. We identify rea- sons why these variations appear and present ways to reduce the number of variations with appropriate graph models and by applying limits during search. Our results indicate that precomputing multi-modal transfer patterns on large datasets is feasible with such a restricted model.

2011

• Florian Bäurle
  A User Interface for Semantic Full Text Search  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  We present a powerful and comfortable interactive web user interface for semantic full-text search. It combines and extends established components of other search user interfaces - namely keyword search, facets, proposals and breadcrumbs - in a new way. The result is a reasonably easy to use semantic search application that assists its users in an incremental creation of semantic queries, without requiring them to have knowledge about any special query language or the underlying ontology. The user interface provides only a single input field as it is also common for current keyword search applications like Google . When something is typed, it automatically shows different proposals for words, relations, entities, or semantic classes that are used to build the search query. When any of the proposals is selected, it is added to the query which is displayed as a tree in an advanced breadcrumbs panel. With the help of the breadcrumbs panel, the query can easily be extended or changed by adding new proposals or replacing or deleting already existing parts. The provided proposals are context sensitive with respect to the current query to support users in the incremental creation of meaningful queries. The hits for the current query are always automatically displayed together with evidence why they suit to the query. In this work we address the design decisions that were made during the implementation of the interface application and explain its basic architecture. We also show what queries are supported by the user interface and how it is used to create them.
• Claudius Korzen
  Icecite: Ein System zur Verwaltung von Wissenschaftlichen Publikationen mit Automatischer Metadaten-Extraktion  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Wir präsentieren in dieser Masterarbeit IceCite – ein System, mit dem wissenschaftliche Publikationen verwaltet und verwandte Publikationen gefunden werden können. Das System bestimmt die Metadaten und bibliografischen Daten (Literatur-Referenzen) von Publikationen automatisch, indem es Titel und Referenzen aus entsprechenden PDF-Dateien extrahiert und Einträgen aus den Literaturdatenbanken DBLP und Medline zuordnet. Wir erhalten damit vollständige und korrekte Metadaten, die sowohl die Publikationen als auch ihre Referenzen eindeutig identifizieren. Unter anderem weil wir damit in der Lage sind, Verknüpfungen zwischen Publikationen herzustellen, kann das System alle notwendigen Schritte einer Literaturrecherche vereinfachen. Die Schwierigkeit der Titel- und Referenzen-Extraktion aus wissenschaftlichen Publikationen liegt in der großen Variabilität in Position und Struktur der zu extrahierenden Elemente. Mögliche Fehler in den extrahierten Zeichenketten, die z.B. auf Schreib- oder Extraktionsfehler zurückzuführen sind, machen zudem eine fehlertolerante Zuordnung zu einem Literaturdatenbank-Eintrag notwendig. In ausführlichen Experimenten an 700 Publikationen aus DBLP und 500 Publikationen aus Medline haben wir unter anderem die Korrektheit der Ergebnisse unserer Algorithmen zur Extraktion und Zuordnung von Titeln und Referenzen evaluiert. Wir erreichen Ergebnisse von bis zu 98.8% korrekt extrahierter Titel und von bis zu 91.1% korrekt extrahierter Referenzen. Die Zuordnung zu repräsentierenden Einträgen aus DBLP und Medline gelingt uns für bis zu 99.9% Titel und für bis zu 94.8% Referenzen.

2010

• Elmar Haussmann
  Contextual Sentence Decomposition with Applications to Semantic Full-Text Search  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  In this thesis, we introduce and study contextual sentence decomposition , which, intuitively, decomposes a given sentence into parts that semantically “belong together”. For example, a valid decomposition of the sentence “ Usable parts of rhubarb include the edible stalks and the medicinally used roots, however its leaves are toxic” are the sub-sentences “ Usable parts of rhubarb include the edible stalks”, “ Usable parts of rhubarb include the edible stalks” and “however its leaves are toxic ”. Our motivation for this problem comes from semantic full-text search . For a query plant edible leaves, semantic full-text search returns passages where instances of a plant, such as “ rhubarb ” (and not the word “plant ”), are mentioned along with the words “ edible” and “leaves ”. One of the results this query might erroneously return is the original sentence above. With contextual sentence decomposition we avoid this false-positive, while at the same time maintaining the true factual contents of the original sentence. We propose two approaches for our problem, one based on a set of rules and one using machine learning. On a manually assembled ground truth, we achieve an F-measure of about 65 percent for the former and of 40 percent for the latter. For the semantic full-text search based on these approaches, evaluated on the English Wikipedia (27 GB of raw text), we achieve improvements nearly doubling the F-measure for some queries.
• Björn Buchhold
  SUSI: Wikipedia Search Using Semantic Index Annotations  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  We present Susi , a system for efficient semantic search on the English Wikipedia. Susi combines full-text and ontology search. For example, for the query penicillin scientist , Susi recognizes that scientist is a type of person, and returns a list of names of scientists that are mentioned along with the word penicillin . We argue that neither full-text search alone nor ontology-search alone is able to answer these kinds of queries satisfactorily. Along with the list of entities matching the query (the name of the scientists in the example), Susi also provides excerpts from the text as evidence. The data structure behind Susi is an index for the CompleteSearch search engine. This index is enriched by constructs derived from facts from the Yago ontology. The challenge was to do this in a way that keeps the index small and enables fast query processing times. We present an annotation style, specifically designed to eliminate index-blowup associated with adding semantic information. In our experiments on the complete English Wikipedia (26GB XML dump), Susi achieved average query times of around 200 milliseconds with an index blowup of only 42% compared to ordinary full-text search. We also examine result quality by comparing the contents of hand-compiled Wikipedia lists like " List of drug-related deaths " against the output of Susi for corresponding semantic queries ( drug death person ). We come up with a simple typification of the kinds of errors that can occur. One of our findings is that the vast majority of false-positives is due to false omissions on the side of the Wikipedia lists, while the vast majority of false-negatives is due to omissions in the Yago ontology.

Bachelor theses

2026

• Benke Boldizsár Hargitai
  Efficient GroupBy for the QLever SPARQL engine  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  This bachelor’s thesis describes methods developed to accelerate data grouping in the QLever SPARQL data management engine. This was accomplished by optimizing the QLever engine’s GROUP BY algorithm. Calculating the GROUP BY operation requires one or more columns to be specified. The input data is then grouped along these columns. Currently, there are two strategies for this calculation: 1. Sorting the input data by the grouping columns and separating blocks of data where the values in the grouping column are the same. 2. Using a hash map. Neither strategy has proven to be faster than the other on a consistent basis. When the hash map strategy was introduced, it initially appeared to be consistently better than the sorting strategy. However, it turned out to be slower when there were too many small groups. This common scenario occurs when the values in the grouping columns are mostly unique. This problem led to the development of a “hybrid” approach in this bachelor’s thesis. The approach uses both of the previously mentioned grouping strategies. It begins with the hash map strategy. If the number of groups exceeds a certain threshold, the approach switches to sorting while extending the groups already in the hash map. Finally, the results from the two strategies are merged and sorted. Experimental evaluations based on RDF benchmark datasets show that this new approach leads to significant improvements in query time.

2025

• Noah Nock
  An efficient external R-tree for very large datasets  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Modern information retrieval which is used in big search engines has a large impact on our lives. One of the many challenging tasks of information retrieval is spatial quering. Vast spatial datasets can be managed in different ways depending on the application. This work focuses on the task to retrieve every bounding box of a large dataset that intersects with a given bounding box. Among many different data structures which can be used to solve this problem, the R-tree is a popular choice. The R-tree is a search tree specifically designed for spatial indexing. It works by dividing all elements of a certain node into a number of child nodes so that the bounding boxes of the elements in each child have a minimal overlap. Every node keeps track of the bounding box containing all its elements and continues to divide those elements into child nodes until a specific leaf condition is reached. When given a R-tree, you simply check for intersections of your query with the children of every expanded node starting from the root node. When an intersection is found, you expand the intersecting child node until the leaf nodes of every expanded nodes are reached. Every intersection in a leaf node delivers a result for the query. In theory this works really well, since a balanced R-tree will answer your query in logarithmic time. However, the actual implementation poses significant challenges in terms of memory management when it comes to large datasets. Since the best-performing R-tree building algorithms require the knowledge about all data points to iiiwork, previous implementations load the entire dataset into RAM and keep it loaded to execute queries. This is not possible for very large datasets. This work provides the theoretical background of a R-tree implementation, which can build well-balanced trees in a very efficient way, while also being able to operate within a given RAM limit by using only the necessary data on demand. To address this object, this work delves into the fundamental concepts of R-trees, R-tree packing, the actual implementation and the analysis of the implemented R-tree.
• Hagen Morgalle
  Bringing Neural Spelling Correction to Mobile Keyboards Using a Client-Server Architecture  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Mobile keyboards rely heavily on intelligent spelling correction to support users during text input. Modern neural networks deliver high accuracy but often exceed the computational limits of mobile devices. This thesis investigates the practical feasibility of employing a neural spelling correction model for mobile keyboards using a client-server architecture. We developed an Android keyboard application that retrieves corrections from a remote server and evaluated it in technical experiments and a user study. The technical evaluation shows that the system achieves an average end-to-end latency of 128 ms and a correction accuracy that clearly outperforms Google’s Gboard. In the user study, we evaluated the acceptance of the system for both word-level and sentence-level correction. Both modes were found to be feasible in practice, with sentence-level correction being rated particularly positive.
• Christoph Ullinger
  Efficient Spatial Search for the QLever SPARQL Engine  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  We present an end-to-end workflow for efficiently performing geographic searches for nearest neighbors with the QLever SPARQL engine. Our solution significantly reduces the time and the users’ effort required to combine and query spatial data from multiple sources. QLever allows working with points in the standardized Well-Known Text format, which it now stores efficiently. Searching for geographically close points in data sets containing hundreds of millions of points becomes a matter of seconds using QLever’s new spatial search capabilities. A fast algorithm based on a spatial index is presented as well as a proof of concept baseline algorithm. The spatial search is carefully integrated into the SPARQL syntax. We introduce programs for the conversion of data from multiple formats (Keyhole Markup Language, Comma-Separated Values and General Transit Feed Specification) to RDF. Additionally, a new program allows users to construct complex spatial queries for QLever with a graphical user interface. The retrieval of data, which would otherwise require working with many different data sets individually, is now possible in a single SPARQL query. We demonstrate the usability of our workflow using a current research question from political science. Furthermore, we show that our efficient spatial search implementation in QLever surpasses the query performance of the popular PostgreSQL system by orders of magnitude for large inputs. Regarding all benchmarks, our implementation shows more stable running times.
• Moritz Dom
  Efficient and Correct Federated Queries for the QLever SPARQL engine  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  The QLever SPARQL+Text query engine is an efficient application used for querying both large-scale knowledge graphs and text corpus. Federated query is a feature of the SPARQL query language that allows querying multiple data sources in a single query. In this thesis we present an improved implementation of federated query processing in QLever, increasing both their efficiency and robustness. By constraining the result size of federated queries based on the query context, we were able to decrease their RAM usage in QLever significantly.
• Felix Meisen
  Improving the full-text index of QLever  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  QLever is a SPARQL+Text engine that can be used to build and query an index of a knowledge base and a text corpus. QLever extends SPARQL by two QLever-specific predicates for text search. Those predicates are ql:contains-word and ql:contains-entity [5]. While the predicate ql:contains-word can be used to retrieve texts containing certain words using a WordScan, the predicate ql:contains-entity returns entities co-occurring in texts together with words using an EntityScan. This allows for a “combined search on a knowledge base and a text corpus, in which named entities from the knowledge base have been identified” [5]. This work implements three main changes, improving the full-text index of QLever. The first change modifies the way the text entities of the knowledge base, so-called literals, are added to the full-text index. QLever already provided an option to add all literals to the full-text index, but when querying a full-text index built from all literals, the corresponding literals were not shown in the result. Furthermore, adding all literals leads to many uninformative literals being part of the full-text index. With the change presented in this work, the user can apply a filter to the triples containing literals during index building. Choosing the right filter can lead to a smaller full-text index without loosing query result quality, potentially even improving it. Additionally, the literals are now shown in the results. The second change allows the user to use a simpler format for the text corpus. A simple text corpus only consists of one file containing all documents together with an identifier for each document. For QLever, the docsfile is exactly this, but QLever expected a docsfile and a so-called wordsfile. This wordsfile essentially contains all words and entities appearing in the documents of the docsfile. Since the wordsfile contains words from multiple so-called text records that are overlapping subsets of documents, the creation of your own wordsfile can be difficult. The reason documents were split up into these text records is the automated identification of entities in documents [6]. This logic is complicated and not easily understood. Therefore, the option to only use the simple docsfile for full-text index building was added. To still keep the functionality of ql:contains-entity, another option was added that only adds the entities of the wordsfile to the full-text index. This leads to similar functionality with a much simpler input. The third and last change simplifies the underlying full-text index structure and provides an option to choose the block size of the full-text index. More importantly, the change also removes the fixed prefix length of the WordScan. This means that whereas before the user could only use WordScans with prefixes having a minimum length of four, they can now use prefixes of arbitrary length like "com*" or even "*".
• Hannes Baumann
  Optimizing SPARQL FILTER Expressions in QLever by Introducing Prefilter Procedures  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  QLever (clever!) is a SPARQL engine developed at the Chair of Algorithms and Data Structures at the University of Freiburg. QLever enables users to efficiently query large knowledge graphs, such as Wikidata [1]. This thesis is an optimization contribution related to the frequently used FILTER expression. For example, FILTER(?var > 5) enforces that only rows with a value greater than 5 in the column associated with the variable ?var are included in the result. The previous evaluation of a query involved the procedure of scanning all index sections for a given scan specification through the INDEX SCAN operation related to the variable ?var. The involvement of variables in FILTER expressions was not taken into account during the scanning process. As a consequence, the evaluation of FILTER expression required iterating over a mostly unnecessary large number of rows, checking in this case the ?var-associated column value on the condition ?var > 5. A significant number of rows typically contain values that do not satisfy the FILTER expression. Thus, scanning all rows and subsequently iterating over them to evaluate the FILTER expression introduced an unnecessary computational overhead, especially since QLever stores its indexes in sorted order. These sorted indexes allow us to efficiently prefilter and subsequently scan only the index sections that contain values satisfying the expression ?var > 5. The objective of this thesis is to implement a prefilter procedure that reduces the evaluation overhead for such FILTER expressions.
• Ioannis Nezis
  Qlue-ls, a powerful SPARQL language server  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  The Resource Description Framework (RDF) formalizes a way to describe Information in a graph-like structure. SPARQL is the standard query language for interacting with RDF data, but writing queries can be challenging, especially without auto completion support. In this work I present Qlue-ls, a SPARQL language server. Powered by a parser that is able to parse incomplete queries, it’s able to provide support when writing SPARQL. By using the language server protocol Qlue-ls can be used by any editor that provides language server support.
• Tobias Bürger
  SQL-petrimaps: Visualizing Geospatial Data using PostgreSQL and PostGIS  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  petrimaps is a tool developed by the Chair of Algorithms and Data Structures at the Albert-Ludwig-University of Freiburg. petrimaps is able to visualize "hundreds of millions of geospatial query results while remaining responsive. This is in contrast to other tools that slow down or become unresponsive when the number of objects in the result is large" [1]. While this is a nice property, petrimaps is not yet a very stable or feature-rich tool. The original paper [1] proposes to support user-written SPARQL queries, displaying results as a heatmap or as full objects, and exporting the results as CSV, TSV or GeoJSON. Later, I implemented a responsive loading bar, additional user interface to conveniently send requests to the backend and the ability to upload GeoJSON files. This thesis introduces SQL-petrimaps to close a major gap in the list of supported features. We look at how we can evaluate the query results of any SQL query sent to a PostgreSQL database and use petrimaps as the platform to visualize contained geospatial data. We benchmark SQL-petrimaps using multiple datasets.

2024

• André Schlegel
  A Macro-Benchmarking Library for the QLever SPARQL Engine  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Comparing execution times of different algorithm implementations can be time and work intensive. This time and work is needed to cover every possible, generalized situation for the different algorithm implementations, otherwise, no true statements can be made about the execution times of different algorithm implementations. To make covering every possible, generalized situation for the different algorithm implementations easier, I’ve built an internal macro-benchmarking library for the, as named on the project page of [1], “QLever SPARQL engine”. The internal macro-benchmarking library for the QLever SPARQL engine offers a simple method for measuring the execution time of computer software in seconds, multiple ways to organize measured execution times, metadata support, and support for user-defined runtime configuration options, which should simplify the generation of measured execution times.
• Rico Andris
  Automated standard compliance testing and visualization for the QLever SPARQL engine  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  This thesis addresses the challenge of enhancing the reliability and standard compliance of the QLever SPARQL engine, a tool utilized for querying RDF data. The main focus of this work involves automating the process of executing a set of standardized tests (SPARQL 1.1 test suite) against the engine to identify errors and areas of non-compliance. To make the results easily accessible, a web-based visualization tool was developed, enabling developers to quickly identify and rectify discrepancies. Additionally, this work established the foundation for inte- grating these tools into the QLever project’s GitHub workflow, ensuring that the engine remains compliant with SPARQL 1.1 standards with each update. This enables developers, even those who are not well-versed in SPARQL standards, to promptly identify and resolve compliance issues.
• Nick Göckel
  Efficient Keyword Search For The QLever SPARQL Engine  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  QLever is an efficient SPARQL search engine that supports combined search on an RDF knowledge base and a collection of texts. In this thesis, we present a new implementation of text search for the QLever SPARQL engine, that simplifies the code and makes future improvements easier. We also present a new feature for QLever, that allows the user to retrieve the completed keywords for prefix keyword searches.
• Simon Bärmann
  Polar - a Centralized Digital Participation Platform for Political Groups and Organizations.  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Political groups and organizations, in particular small ones, struggle with using technology for their political practice. Incomplete email lists or Facebook groups often define which member has access to group-related information. Internal elections are still frequently conducted in person or with insecure tools only. We present Polar, a centralized solution for digital participation, and Eos, a transparent and secure election service. Polar provides functionality for the typical workflows of political groups, such as secure chat rooms (through Matrix integration), motion creation and discussions and an event system. It is integrated with Eos to perform secure elections, making use of Polar’s single-sign-on functionality. To validate the conception of both applications, we evaluate Polar and Eos through a user study, which resulted in predominantly positive feedback.

2023

• David Otte
  Improved Simple Question Answering over Wikidata  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  In Knowledge Graph Question Answering (KGQA), the goal is to answer natural language questions over knowledge graphs. Many previous works focused on question answering over Freebase, which support was cancelled in 2015. Instead, we further investigate question answering over the full Wikidata Knowledge Graph and propose a pipeline for question answering over Wikidata. We focus on simple questions, which are questions that can be answered with a SPARQL query that only uses a single triple. Still, our approach is principally not limited to simple questions and could be extended for complex questions. Given a natural language question, our pipeline generates a set of query candidates, ranks them according to collected features and takes the results of the highest ranked query as the answer to the question. One main focus of our work is the relation matching, where we propose a relation scorer based on the Sentence-BERT architecture for fast and accurate matching. We also discuss the quality of existing question answering datasets for Wikidata and experiment with generating additional questions from Wikipedia articles for fine-tuning. We evaluate our pipeline on three different benchmarks, achieving good results on each. On the SimpleQuestions-Wikidata benchmark, our pipeline achieves an accuracy of 0.816.
• Christina Davril
  Semantic SPARQL Templates  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Question Answering over Knowledge Graphs (KGQA) remains a very challenging problem, with some seemingly straight- forward questions requiring complex, nested queries to be answered. This thesis presents a novel, template-based approach by identifying knowledge graph-independent "semantic SPARQL templates". These templates constitute a comprehensive set of syntactic building blocks used to realize semantic aspects of users’ information needs. To assess the practical utility of the found templates, they were applied to a newly created benchmark. This benchmark, called Wikipedia Lists, leverages Wikipedia lists as a verifiable ground truth, ensuring, to some degree, the correctness of the query. The benchmark covers a wide range of query structures, addressing a limitation found in most other Wikidata-based benchmarks. The "semantic SPARQL templates" have been applied success- fully to all examples in the benchmark with the results of the template-based queries matching those of their hand-written counterparts. Moreover, using the templates may improve the quality of the resulting queries compared to queries written by hand. The general applicability of the templates translates to robust queries that return the desired outputs with varying input data. This stands in contrast to human-curated queries, which may rely on world knowledge, which can be incorrect or may only be applicable during a certain time. In addition, the application of the templates to the benchmark provided information about the templates’ usage frequencies, shedding light on structural patterns that appear in SPARQL queries and how they relate to patterns in the natural language (NL) question. In summary, this thesis establishes a foundation for a semantic templates-based KGQA system, while also contributing a new Wikidata-based benchmark and offering preliminary findings about structural patterns in Wikidata-based SPARQL queries.
• Christoph Röhrl
  Vorhersage des Privatbesitzes von Straßen mit Hilfe von Machine Learning  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Im Bereich der Planung von Glasfaserkabelverlegung spielt es eine große Rolle, ob sich eine Straße in Privatbesitz befindet oder nicht, da die Verlegung in privaten Straßen oftmals mit höheren Kosten einhergeht als in öffentlichen Straßen. Diese Information, also wem eine Straße gehört, kann oftmals nicht oder nur mit großem Aufwand herausgefunden werden. In dieser Arbeit untersuchen wir, inwiefern sich glaubwürdige Vorhersagen über den Privatbesitz einer Straße machen lassen. Hierfür werden wir öffentlich zugängliche Straßendaten von OpenStreetMap sowie verschiedene Machine Learning Methoden benutzen. Für das Trainieren und Testen der Machine Learning Modelle erstellen wir einen Referenzdatensatz mit Straßen der Stadt Heidelberg. Diesen Datensatz ergänzen wir mithilfe von offiziellen Straßendaten des städtischen Tiefbauamtes um die Information des Privatbesitzes. Mit diesen Daten trainieren wir zwei Machine Learning Modelle und evaluieren die Ergebnisse anschließend ausführlich, wobei beide Modelle miteinander verglichen und ihre Leistungen begutachtet werden. Zuletzt arbeiten wir noch die Aussagekraft der verschiedenen Straßenattribute heraus.
• Hendrik Henselmann
  Web Visualization Of Geographic Data Implementing A Thin Client Architecture  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  We present a system for efficiently visualizing large amounts of geographic data on a Web page. Our Web application implements a suitable architecture, the thin client architecture, that performs all computationally intensive operations on the server. These operations include requesting, processing and storing geographic data. The resulting image is then transmitted to the client and is finally displayed. In this thesis, we specifically deal with the visualization of OpenStreetMap data. OpenStreetMap is an open-source project regarding geographic data. We utilize the query engine QLever to execute queries that return a subset of the data. We highlight this subset on an interactive world map. Our results show that our approach is suitable for visualizing even millions of objects in seconds. It visualizes 2,000,000 points defined by 2,000,000 geographic coordinates in about half a second and 2,000,000 more complex geometries, like polygons, defined by about 8,500,000 geographic coordinates in about two seconds.
• Julius Heinzinger
  pdf2gtfs: Timetable Extraction from PDF Files  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  We present pdf2gtfs, which enables us to extract timetable data from PDF schedules and export it in the machine-readable GTFS format. This format requires the coordinates of the location of each stop. We use OpenStreetMap to search for the location of a stop, using only the stops name and the other stops of a route. We also introduce a new table extraction algorithm to pdf2gtfs that is row- and column-independent, meaning that we can process timetables regardless of their orientation. As further improvement to pdf2gtfs, we include additional information from OpenStreetMap about stops, such as the internationally unique IFOPT, or whether a stop is wheelchair-accessible. Finally, we create p2g-eval to evaluate the GTFS feed generated by pdf2gtfs based on a ground truth. This is to quantify the quality of the extracted information, and to help discover those parts that can still be improved. We show that the new table extraction algorithm achieves more accurate results, when compared to the previously used algorithm, and another, state-of-the-art table extraction tool. We also find that the detected locations are, in general, close to the true locations.
• Leon Freist
  x-search: A C++ Library for Fast External String Search  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  This thesis presents and describes x-search, a C++ library for string searching on externaldata. x-search provides a basic framework for implementing pipeline-based procedures. x-search provides a simple, ready to use API for searching patterns within file contents that can easily be included within C++ projects. The main goals of the x-search library include • Performance: optimized multi-thread accelerated I/O and search routines. • Usability: a simple yet powerful API for the most commonly used search result types (byte offsets, line indices, lines) and simple inclusion to other C++ projects. • Variability: a robust backbone that enables developers to optimize the process for more specific use cases or to extend it by additional features. The default components included in x-search work on text data encoded in UTF-8 and provide an interface for working on preprocessed data using x-search-specific preprocessing such as compression. We further introduce a GNU grep-like executable called xs grep which uses x-search as its backbone. We will show that xs grep performs multiple times faster than GNU grep (a standard in exact string searching software on external data) on single files. We further show that xs grep also outperforms ripgrep (a grep-like command line search tool with better performances than GNU grep) in scenarios, in which the search process dominates reading the data. Therefore, we present and discuss runtime comparisons of xs grep, GNU grep and ripgrep on different hardware and with different search complexities (e.g. case-insensitive or regex searches).

2022

• Urs Spiegelhalter
  Annotating OpenStreetMap data with elevation data  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  We present osmelevation, a tool to annotate OpenStreetMap data with elevation data obtained from the NASA Digital Elevation Model (NASADEM). By adding a tag ele=* containing the elevation to each node, we enrich the complete OpenStreetMap data with elevation data. NASADEM provides near-global coverage and a horizontal resolution of 1 arc-second, which is approximately 30 meters. This results in 376GB of uncompressed elevation data. In combination with the ever-growing OpenStreetMap data, our tool manages the large amount of data by splitting both the OpenStreetMap and elevation data into smaller data pieces and processing them one by one. Furthermore, we provide a second tool correctosmelevation. Based on already with elevation data annotated OpenStreetMap data from our first tool, we perform simple corrections on the elevation data. As a basis, we look at OpenStreetMap linear route map features like roads or rivers. Even with the high horizontal resolution of approximately 30 meters of the NASA Digital Elevation Model, obvious errors can be observed. For example, roads suddenly dropping by five meters, or rivers flowing uphill. Our tool correctosmelevation corrects those errors and updates the corresponding ele=* tags with the corrected elevation.
• Krisztina Agoston
  Context-based Sentence Segmentation for Irregular Domains  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Sentence segmentation is a fundamental task in Natural Language Processing (NLP). Its purpose is to find sentence boundaries within a text, divide a it into individual sentences, and provide them for follow-up processes in the NLP pipeline. However, sentence segmentation is regarded as a solved problem, but text from an irregular domain still presents a challenge. For this reason, we focus on specific domains with special syntax and a variety of punctuation. We propose for this task two context-based approaches: a Long Short-term Memory (LSTM) model trained on a large collection of sentences. We also present a variation of this model, the bidirectional LSTM, offering the ability to use not only the previous, but also the future information in a sequence. We compare these models to two state-of-the-art systems: NLTK and spaCy. Our system returns competitive results to the solutions of these systems, with an F1-Score of 91.39% on hard cases and 96.94% on randomly selected paragraphs from the Wikipedia corpus.
• Robin Textor-Falconi
  Efficient Export of SPARQL Query Results  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  This bachelor’s thesis documents an implementation of CONSTRUCT queries largely compliant with the SPARQL standard. It also discusses several approaches to make the process of exporting query results as fast as possible and compares the performance of a selection of those approaches in a real-world example. This includes environments with a limited bandwidth to the server by making use of compression algorithms and asynchronous processing.
• Benjamin Dietrich
  Efficient Wikipedia Entity Linking and Co-Reference Resolution in C++  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  A named entity is, for example, a person, product, or organization that its name can identify. Examples are ’Marie Curie’, ’Snickers’ or ’Microsoft’. Automatically recognizing and identifying named entities in texts is called entity linking. Automatically linking pronouns and entity types to the named entities they refer to in a text is called co-reference resolution. For example, the ship ’Titanic’ has the entity type ’ocean liner’ and can be referenced by the pronoun ’it’. The Python-based Wiki Entity Linker provides automatic entity linking and co-reference resolution on Wikipedia article texts. The system produces good results but has a long runtime. This thesis presents a redevelopment of the Wiki Entity Linker with a focus on efficiency. Two C++ versions of the Wiki Entity Linker were developed. Both systems have the same basic structure, but one uses an external Python-based natural language processing (NLP) library. The other system utilizes a complex set of rules. Both systems surpass the Wiki Entity Linker regarding runtime and result quality.
• Ievgen Markhai
  Entwicklung einer „Package Information Tracker“-Webanwendung  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Eines der Hauptprobleme bei der Zustellung von Paketen durch Paketdienstleister ist die Übergabe an den Endverbraucher, vor allem bei der Lieferung an andere anwesende Personen, was oftmals zu einem Verlust der Pakete führt. In dieser Arbeit wird die Entwicklung und Ausführung einer Webanwendung zur Lösung des Problems von verlorenen Paketen innerhalb großer Institutionen, Firmen oder Campusse ohne zentralen Concierge-Service dargestellt. Dafür werden Anforderungen für die Realisierung der Anwendung sowie ein Konzept für die Anwendungsarchitektur definiert. Es werden die Details der Umsetzung von Frontend und Benutzeroberfläche bis hin zur Backend-Implementierung und -Bereitstellung diskutiert. Außerdem wird eine Evaluation durchgeführt mit dem Ziel, die Anwendung weitestgehend zu optimieren. Eine Instanz für die Technische Fakultät der Universität Freiburg wird unter Berück-sichtigung von Evaluationsergebnissen bereitgestellt.
• Metty Kapgen
  Generating Low-Voltage Grid Benchmarks with OpenStreetMap  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  This bachelor’s thesis documents an implementation of a benchmark generation tool to evaluate low-voltage grid expansion algorithms. This is achieved through generating test grids with the help of OpenStreetMap. In a time in which the supply and expansion of energy infrastructure becomes more and more pressing it is especially important to develop efficient and correct expansion plan algorithms. The emphasis of this thesis lies in the ability to customize such grids to fit the user’s specialized needs. We provide the user of this benchmark tool, among other things, with a set of forest algorithms which can be selected to generate different states/scenarios on the same grid. Those grids can then be used to test, compare and verify different expansion plan algorithms on real-world scenarios. This implementa- tion will return a dataset which can be digested by expansion planning algorithms that use PyPSA[1].
• Robin Wu
  PublicTransitSnapper: Dynamic Map-Matching To Public Transit Vehicles  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  PublicTransitSnapper is an application for matching a user to the public transit vehicle the user is currently traveling on. We base the matching to a public transit vehicle on a sequence of timestamped locations. Public transit vehicles travel along a specific path at a specific time within their public transit network. Since location measurements are noisy, only ”snapping” to the closest road might not work. Map-matching can be used to match a sequence of locations to the most probable path in a static road network. For map-matching to a public transit vehicle we need to find a vehicle that follows a similar path to the locations and the vehicle must be at these locations at the measured times. In this thesis we present a solution to this dynamic map-matching problem. Similar to conventional map-matching, we utilize a Hidden Markov Model. Furthermore, we include time information from the schedule to find the most likely public transit vehicle.
• Gerrit Freiwald
  PublicTransitSnapper: Map Matching Mobile Phones to Public Transit Vehicles in Real Time  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  We match location data from a mobile phone to the most likely public transport vehicle, while using all information available in Google’s public transit schedule format GTFS. We explain how we succeeded in creating a backend that is capable of performing a ‘Public Transport Vehicle Matching’ algorithm and how we built a user-friendly web- and mobile app. We analyze our conducted user study to test the app in Freiburg, Hamburg, Munich and Zurich. The results suggest that our app works especially well with busses, but has room for improvement with underground services. As there is a lack of publicly available real time data on public transport vehicles in Germany, we discuss its current state and improvement prospects conducted by German authorities.
• Julian Mundhahs
  Typesafe SPARQL Query Parsing mit ANTLR  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Within the frame of this thesis, a parser for the SPARQL 1.1 Query Language (SPARQL QL) was finished. This parser uses the parser generator ANTLR v4. With the new parser, QLever is able to recognize the complete SPARQL QL. An improved version of the visitor pattern provided by ANTLR v4 is presented. The improved visitor makes the visitor type safe, prevents code duplication and provides metadata for error messages.

2021

• Denis Veil
  Efficient Presentation of GeoSPARQL-Results  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  QLever is a SPARQL engine, which can handle large datasets [1]. The engine should now be expanded to include geofunctionalities. In doing so, QLever returns results for certain queries that contain geometric data. This thesis describes a web application that is able to send SPARQL queries to the QLever engine via an API, then process large results and display these on a map. The result size of a query can exceed several million. With each entry containing potentially multiple data points the web browser struggles to render them at the same time. The main challenge of the application is to handle even larger results efficiently to deliver a user-friendly experience.
• Jianlan Shao
  Metro-Map Styled River Maps  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  In this thesis, we extract the waterway information from OpenStreetMap (OSM) data and organize it into a directed graph so that we can observe the tributaries of each river clearly. We rearrange the river map in such a way that each river looks like a single subway line starting at its source until its mouth, that is, each river segment is labeled with all its tributaries so far. For example, as a river drains off into the Rhine, the Neckar will be labeled on the Rhine as a parallel line. Eventually, the main stem of the Rhine will look like dozens of small subway lines next to each other. We use our tool LOOM (Line-Ordering Optimized Maps), which renders line graphs in a metro-map style, to present the result in the above-described way.
• Jonathan Zeller
  Planung von Mittelspannungsnetzen mithilfe eines Ameisenalgorithmus  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Diese Bachelorarbeit befasst sich mit der Planung von Mittelspannungsnetzen. Hierbei müssen die sogenannten Busse untereinander sowie mit einem Transformator verbunden werden. Busse sind elektrische Komponenten, an welche alle anderen relevanten Komponenten angeschlossen werden. Der Transformator liefert einen Großteil der Energie zur Versorgung der elektrischen Verbraucher. Diese Arbeit baut auf der Dissertation von Niklas Rotering auf. Sein Ansatz wird hierbei implementiert, erweitert und analysiert. Die Grundidee des Algorithmus besteht darin, einige Lösungen auf zufällige Art und Weise zu erzeugen. Die Lösungen werden anschließend bewertet und je nachdem wie gut die Lösungen sind erhalten die beteiligen Komponenten einen höheren Wert. Dieser Wert beeinflusst die Wahrscheinlichkeitsverteilung, nach welcher in der folgenden Iteration die Komponenten gewählt werden. Komponenten, welche an guten Lösungen beteiligt waren, werden dadurch häufiger gewählt. Mithilfe von dieser Heuristik soll nun in einem iterativen Verfahren eine möglichst gute Lösung gefunden werden.
• Michael Fleig
  Public Transit Map-Matching withGraphHopper  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  TransitRouter is a tool for generating high quality shape files for GTFS feeds. We solve the following map-matching problem: given an ordered sequence of stations and the underlying network, find the most likely route of a public transit vehicle.TransitRouter provides two map-matching approaches that are based on a hidden Markov Model: the GraphHopper Map-Matching library(GHMM) and our own TransitRouter Map-Matching(TRMM) with support for inter-hop) turn restrictions.We evaluate TransitRouter on real-world data and compare the results against pfaedle.
• Daniel Kemen
  QLever UI - Building an interactive SPARQL editor to explore knowledge bases  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  QLever (pronounced "clever") is an efficient full-text search engine (SPARQL + Text engine) that computes complex search queries on huge semantic knowledge bases and text corpora like Wikidata, OSM, and ClueWeb. The basic design of QLever was originally described in a paper for CIKM’17 by H. Bast and B. Buchhold[1]. Writing queries for specific information in very huge knowledge bases with billions of information requires prior knowledge about the contents and structure of the underlying data set. Therefore exploring huge data sets and writing comprehensive search queries can be complex and time-consuming. Together with Julian Bürklin, I developed the interactive SPARQL editor "QLever UI" that provides an easy-to-use interface to write search queries for the QLever engine. QLever UI makes it easy to write syntactically correct search queries in the SPARQL language. Due to its ability to parse and evaluate even complex SPARQL search queries it can provide some very helpful features like context-sensitive and ordered auto-suggestions, syntax highlighting, name lookups, and an inline search that finds data attributes by synonyms of their names. QLever UIs context-sensitive suggestions depend on the current cursor location inside the query and even evaluate partial and grossly incomplete parts of the query while the user is writing it. As the query becomes longer the suggestions become more relevant by evaluating all the already written parts of the query.
• Julian Bürklin
  QLever UI: A context-sensitive user interface for QLever  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  QLeverUI is a web user interface for QLever [1], an efficient query engine developed at the chair for algorithms and data structures at Albert-Ludwigs-Univerity Freiburg. The interface mainly consists of an input area where one can enter SPARQL queries which are then sent to a QLever back end. After evaluating the query, the query results will be returned by the back end and displayed in tabular form. The main focus of QLever UI lies in supporting the user with writing these SPARQL queries. It provides autocompletion and next word suggestion functionalities, both in a contextsensitive manner. To do this, QLever UI queries the same QLever back end that is also used for the user’s queries. In the following we will explain the basic architecture and functions and the key components of our user interface.
• Elias Kempf
  Segmentation of Layout-Based Documents  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  The Portable Document Format (PDF) continues to be one of the most prominent file formats for exchanging electronic documents. Thus, applications that extract high-quality text from PDF documents are also high in demand. However, PDF is a layout-based format that only stores characters and their positions rather than the plain text itself. PDF also does not store any whitespaces, and characters can be stored in an arbitrary order. Therefore, the task of extracting text in the correct reading order is unexpectedly hard to solve. In this thesis, we address an important subtask of text extraction, which is text block extraction. This task includes detecting text blocks and sorting them by reading order. In a separate step, we also split the extracted text blocks into individual words. We propose a top-down page segmentation algorithm based on the recursive XY-cut algorithm for text block detection. Additionally, we evaluate different strategies for detecting reading order, including learning-based approaches. On average, our application detected around 51% of the expected text blocks perfectly, about 13% were split too often, and about 15% were not split enough. For reading order, we achieved an average normalized Kendall-T-correlation [1] between expected and detected reading order of 0:873.
• Ziang Lu
  Spelling Correction and Autocompletion for Mobile Devices  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  With the ubiquity of the Internet, people are used to sending messages, writing e-mails, and querying search engines with smart mobile devices. To facilitate entering text with less keystrokes, and thereby save inputting time, ever smarter keyboards are developed. This paper aims to present how n-gram models and other relevant techniques could be used for the implementation of smart keyboards. In this paper, an English system keyboard for Android devices was developed to help in predicting, completing and correcting the next word. A detailed evaluation shows that n-gram models could contribute to the development of better keyboards and improve the user experience.

2020

• Florian Kramer
  Effcient Property Path Evaluation within the QLever Query Engine  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  This work is an implementation and evaluation of the property path feature from the SPARQL query language for the QLever query engine. This allows for searching for pairs of entities that are connected by a given path in a knowledge base. An example of such a query is: SELECT ? s c i e n t i s t ? c l a s s WHERE { ? s c i e n t i s t <ht tp : / / example / i s a>/<ht tp : / / example / i s a> ? c l a s s } This work also contains a comparison against Blazegraph in the form of an evaluation on a set of 39 property paths. On average the implementation presented here was about twice as fast as Blazegraph on the evaluation queries.
• Nico Gräf
  Entwicklung eines positionsbezogenen Spiels als Web-App für Freiburg  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Jedes Jahr werden innerhalb Deutschlands fast vier Millionen Umzüge über Gemeindegrenzen hinweg verzeichnet. Fehlende Verbundenheit und Ortskenntnisse, Einsamkeit und ein gemindertes Wohlbefinden gehören zu den Herausforderungen, denen Menschen nach einem Umzug begegnen. Befragungen und Studien weisen darauf hin, dass digitale Lösungen und Apps bei diesen Herausforderungen helfen könnten. In dieser Arbeit wurde prototypisch ein Spiel für Freiburg entwickelt, welches Wissen vermitteln, Ortskenntnisse verbessern, soziale Aktivitäten fördern und das allgemeine Wohlbefinden steigern soll. Dafür wurden über die Analyse von Studien Anforderungen an eine entsprechende App definiert. Anschließend wurde ein Konzept entworfen und die App designt. Konzept und Design wurden in die Entwicklung einer Web-App überführt und die implementierte App mit mehreren Testpersonen evaluiert. Die Evaluation hat gezeigt, dass die App auf spielerische Art Wissen und Ortskenntnisse vermitteln kann und dabei zur langfristigen Nutzung motiviert. Ebenfalls sind durch die Evaluation Schwachstellen im Konzept und dem Design aufgedeckt worden. Die soziale Aktivität der Testpersonen konnte durch die entwickelte App nicht gefördert werden. Anhand der Ergebnisse der Evaluation konnte eine Anforderungsliste für die weitere Entwicklung abgeleitet werden.
• Johannes Burkhard Roland Herrmann
  Evaluation of Investment Strategies for Cryptocurrencies  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  How to invest money most profitably is not only a field of research, but also a question that most people are confronted with at some point. The easiest approach is to invest the money and leave it there for an arbitrary time period. This is a common approach, not only for a savings account, but also for assets like crypto currency or stocks. Contrary to investing there is also day trading, where the asset is bought and sold within daily or sub-daily time frames. The aim of this approach is to generate a higher profit than simply investing would yield. Technical Analysis is a field which provides a lot of day trading strategies that are easy to interpret and easy to implement. The question we ask in this thesis is, if we can use one of the most popular day trading strategies to get a higher return on the used capital than if we would invest traditionally. This strategy is called Simple Moving Average Crossover (SMAC). To answer this question we will study the related literature on this topic, construct an asset-pricing model under which the SMAC strategy would be optimal and then perform a hypothesis test on three different asset classes. Literature and the constructed model do not provide any reasoning why the strategy would incur a higher return than a traditional investment. This causes us to hypothesise, that the strategy does not yield a higher return. By performing a one-tailed binomial test for every possible parameter setting of the SMAC strategy, we find that this hypothesis is rejected for at most half of all possible settings. Thus, if we choose one setting randomly, we have a chance of less than 30% that the SMAC strategy is significantly better than an investment. But there are also settings which have been recommended by self-proclaimed experts. Our tests show that if we chose one of these settings at random, in most cases we would have an even worse chance of using a SMAC setting that outperforms an investment.

2019

• Tanyu Tanev
  Accurate Word Extraction from Documents with Complex Layouts  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  PDF documents are commonly used to exchange and store information. Their compactand self-contained nature has kept them relevant for a long time. It also, however,leads to problems when trying to automate operations on them. An example of this isthe automatic extraction of textual content - a problem, which has not been entirelysolved to this day. Textual content within the documents is only stored at a characterlevel, which means that words and text lines have to be rebuilt from the groundup. There exist rule-based algorithms, which try to solve the problem by takingadvantage of the spacing within the documents. Using them on documents with astandard layout (e.g. scientific publications), which feature rectangular columns andfigures has achieved satisfactory results.It is, however, more challenging for documents, which have a complex layout. Somemagazine and news articles, for example, feature circular pull quotes in-between textcolumns, which are used to emphasize a certain point. This, in turn, makes it harderto deploy the rule-based algorithms, because the spacing in the documents becomesirregular.In the following thesis, this problem is tackled with the help of a deep learningapproach. The approach looks at the pages of a PDF document as a collection ofsequences, which are in the form of text lines. These sequences are then processed bya deep learning model and each character from them is grouped into its respectiveword. The usage of not only the distances between the characters, but also their valueand information about their font, as input features, enables the model to more easilyidentify complex elements (e.g. pull quotes) and accurately extract their textualcontents.
• Anushe Glushik
  Context Tracking for Question Answering with Aqqu  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  The goal of this work is to implement a context tracking functionality in the Aqqu question answering system and to study the influence of context tracking on the overall performance of Aqqu. A question answering system with context tracking functionality takes the context into account. To find the correct answer, the system not only processes the current question, but also the history of questions asked before. To implement context tracking for Aqqu, we developped a web user interface (UI) in the form of a chatbot. Additionally we added to it a data augmentation functionality. We call the Aqqu system with a context tracking functionality conversational Aqqu. We evaluated the conversational version of Aqqu against a newly created conversational version of the original WebQSP questions dataset. For this we transformed and reordered the original one-off questions into conversations about topic entities shared by the original questions. From the evaluation results it was apparent that the conversational question answering is slightly less accurate, when compared to a single-question answering. Yet taking into account, that it is a far more complicated task, the conversational system still showed a very good performance. Moreover context tracking brings more convenience into the question answering process.
• Patrick Bumüller
  Finding Names on University Web Pages  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  An der Universität Freiburg arbeiten 6.736 Personen, von denen viele eine eigene Webseite haben [1]. Die gesamte Anzahl an Webseiten der Universität übersteigt 300.000 Seiten (5.1.4). Beginnend bei der Startwebseite einer Universität einen Mitarbeiter zu finden ist umständlich. Ohne Vorwissen über die Struktur der Webseiten werden viele Klicks benötigt. In dieser Arbeit wird ein System vorgestellt, das für Bildungseinrichtungen die relevanten Webseiten für Mitarbeiter und andere Personen findet und bewertet. Es implementiert ein automatisches Programm, welches Hyperlinks in Webseiten folgen und Namen im sichtbaren Webseitentext erkennen kann. Es konnten in Stichproben durchschnittlich über 90 % der Mitarbeiterwebseiten gefunden werden (5.1.4).
• Mari Sverresdatter Hernaes
  Improved Dehyphenation of Line Breaks for PDF Text Extraction  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Words in layout-based documents can contain hyphens that divide the word into two parts across two lines. PDF documents only store information about individual characters, which makes it difficult to extract text correctly. Words which are hyphenated at the end of a line are especially problematic because in English there are some words where the hyphen should be kept, while others need to be merged. For example, “high-quality” can be a compound word. If this word splits on the hyphen across two lines, then the hyphen should be retained in the extracted text. The correct dehyphenation of line breaks requires the recognition of either words or sequences of characters. In this thesis, vocabulary-based baseline algorithms, logistic regression on the word level and a bi-LSTM Language Model on the character level are used to solve this problem. On the ClueWeb12 Extract data set, the vocabulary-based algorithm achieved a balanced accuracy (bACC) of 66.87%, the logistic regression 92.38% and the bi-LSTM Language Model 90.14%. Our investigations showed a trade-off effect between recognising words which naturally contain hyphens and predicting words without hyphens correctly.
• Leo Zeches
  Merging of Overlapping GTFS Feeds  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  The General Transit Feed Specification, GTFS for short, is a commonly used format for public transportation schedules and related geographical information. Sometimes, these feeds are covering the same network of public transportation and can overlap for certain stations, routes and trips. This undergraduate thesis describes a way to merge such trips in a manner that retains all the relevant information, as well as recognizing duplicate trips and merging trips that are partially included in each other.
• Felix Jablonski
  NEDard: Using Multi-Sense Embeddings for Named Entity Disambiguation  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  This thesis deals with the task of Named Entity Disambiguation. When analyzing a text, it is important to disambiguate mentions of entities such as people, companies, or concepts so that multiple appearances of the same entity can be identified as such. One way to disambiguate entities is to link them to their unique entity in a so-called knowledge base. A knowledge base is a source that stores information about objects like companies, fruits, or people. In this thesis given a text with mentions of such entities, ambiguous mentions are disambiguated and linked to the correct entity in Wikidata. For example "Apple" as fruit or as the company. This thesis proposes two new models (called NEDard and NEDardv2) to solve this task. Machine learning is used to derive a comparable representation of mentions depending on their textual context, and this representation is used to perform the disambiguation. The models are compared to other approaches on different evaluation sets. The evaluation has shown that the proposed models do not solve the NED task better than the baselines. However, it has been shown that there is potential in combining the proposed models with others.
• Pascal Muckenhirn
  Präzise Erkennung von Sonderzeichen aus layout-basierten Textdokumenten am Beispiel der häufigsten europäischen Sonderzeichen  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Das Ziel dieser Arbeit ist es, die Erkennung und Übersetzung von Sonderzeichen in layout-basierten Textdokumenten (hier: PDF) zu verbessern. Layout-basierte Textdokumente und insbesondere PDFs beinhalten einige Herausforderungen. Zum einen enthalten sie Ligaturen. Bei Ligaturen werden mehrere Buchstaben, die aufeinander folgen, näher zusammengeschrieben. Dies wird allerdings nur bei bestimmten Buchstabenfolgen angewandt. Gründe hierfür können stylistische oder historische sein. Ein Beispiel für solch eine Ligatur ist das Zeichen ”ffi”. Aufgrund von Ligaturen ist es dem Nutzer nur möglich nach dem Wort ”efficient” zu suchen, wenn er den Unicode des Zeichens ”ffi” als Teil des Wortes eingibt. Dieses Zeichen ist auf einem Tastaturlayout nicht zu finden, sodass der Benutzer sich den Unicode anderweitig beschaffen muss. Außerdem enthalten diese Dokumente auch kombiniert diakritische Zeichen, welche zumeist eine bestimmte Betonung signalisieren sollen. Sie werden häufig als zwei Zeichen gespeichert und müssen deshalb wieder zusammengebaut werden. Die Frage hierbei ist allerdings, wie dies gemacht wird. Für das Beispiel ”á” würde hierbei das Zeichen ”a” als Basiszeichen und das Zeichen ” ́” als diakritisches Zeichen gespeichert werden. Die größte Herausforderung ist allerdings, dass die Zeichen in bestimmten Fällen nur gezeichnet vorliegen. Hierbei ist also nur die Form des Zeichens und dessen Position zur Erkennung des Zeichens nutzbar. Um diese Ziele zu erreichen wird eine Kombination aus 2 Ansätzen genutzt. Zum einen wird die Form des Zeichens und zum anderen die umliegenden Zeichen analysiert. Diese beiden Ansätze werden mittels 2 getrennten Machine-Learning-Modellen umgesetzt, die im finalen Ablauf zusammenarbeiten. Durch Training der Modelle auf insgesamt 20 verschiedenen Schriftlayouts, zu je 100 PDFs, wird ein großes Spektrum an Dokumenten abgedeckt. Die Evaluation zeigte, dass das finale (kombinierte) Modell mehr als viermal genauer als aktuelle Ansätze ist.
• Marc Ingold
  Researcher Homepage Identification and Name Extraction  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  The topic of this thesis is the implementation and evaluation of a machine learning approach for the information extraction from researcher homepages. The key aspects in this work are the data acquisition from the non-profit organization Common Crawl and the development and assessment of two machine learning models. A model for the identification of researcher homepages from a dataset of arbitrary web documents and a model for the extraction of information from the researchers homepage. Exemplary, the researchers name was extracted. The algorithm choice for both models was restricted to methods that are fast to train and straight forward to interpret such as the Random Forest and linear models with Stochastic Gradient Descent learning. The classification of the web document type was done using a multi-view approach. On the basis of two disjoint feature sets, namely the URL surface patterns and the web page content features, two machine learning models were trained. The final prediction was obtained by combining both of the models. A F1 score of 68% was achieved for the identification of researcher homepages. The extraction of the researchers name was done by extending a simple heuristic with machine learning features. An increase of 6 percentage points in F1 score was achieved in comparison to the heuristic, resulting in a F1 score of 94% for the final researcher name extraction model.
• Katharina Matulla
  Wohin mit den Ladesäulen? Lösungsansätze zur optimalen Platzierung von Ladeinfrastruktur für Elektrofahrzeuge  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Recent growth of the electric vehicles – especially electric cars – market calls for setting up an efficient infrastructure for electric charging stations that doesn’t only accommodate this growth but also accounts for optimizing implementation costs and reducing drivers’ range anxiety. While there already exist multiple methods for calculating optimal locations for charging stations, most of these methods require costly or unavailable data. This thesis showcases three different algorithms that rely only on open-source Points of Interest (POIs) from OpenStreetMap (OSM) to calculate optimal placements of electric charging stations in a given area. The first algorithm is k-means clustering based on Euclidean distances. The second is a clustering method based on the betweenness centrality of POIs in a graph using shortest paths. The third is a genetic algorithm which solves the p-median problem while also using shortest paths. All three algorithms lead to consistent output; clusters of POIs where one POI is chosen as an optimal charging station for its cluster. For the purpose of this thesis, the aforementioned algorithms were applied to three areas: North-Amsterdam, North-Seattle and Davutpasa-Campus (Istanbul). The computed optimal outputs in all three areas are displayed on an interactive map in a webpage and are evaluated against optimal solutions gathered from past research. This undergraduate thesis is developed in connection to a project managed by the Fraunhofer Institute for Solar Energy Systems (ISE) called „EnStadt:Pfaff“. The project aims to transform a former industrial area in Kaiserslautern, Germany into a modern,climate neutral, urban quarter. The work presented here is supposed to not only be applicable for this area but several other areas in the future.

2018

• Olivier Puraye
  Dataset Format Analysis and Column Classification for CompleteSearch  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  In this thesis, we analyse tabular text files with the objective to find suitable parameters to make them searchable using the features of CompleteSearch. We solve this problem in two separate stages. In a first stage, we build a file analyser that parses the text files to gather relevant features related to the format of their content. In a second stage, we use a Naive Bayes classifier to associate the columns in the text files to their appropriate CompleteSearch parameter classes. Furthermore, we integrate this automatic parameter suggestion into the Complete-Search web application and incorporate its user feedback into the classifier training in order to further improve the suggested CompleteSearch configurations over time.
• Johannes Kalmbach
  Efficient and Effective Search on Wikidata Using the QLever Engine  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  The QLever engine allows effcient semantic search on a combination of RDF knowledge bases and fulltext corpora using an extension to the SPARQL query language. In this thesis we present several improvements to QLever that allow performing almost arbitrary SPARQL queries on the Wikidata knowledge base. Those improvements heavily reduce the RAM usage of QLever without significantly increasing the time needed for query processing.
• Jasmin Denk
  Finding Semantic Units in Deep Language Models  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  In this thesis, we want to reproduce the results of the paper \Learning to Generate Reviews and Discovering Sentiment" [Radford et al., 2017]. The authors achieved extraordinary results on sentiment analysis by training a neural language model on millions of product reviews to capture the concept of sentiment. Not only did their model achieve this task, it also evolved a single unit which is responsible for analysing the sentiment of the read data. Our goal is to implement our own language model and analyse its capability to evolve such a semantic, concept-containing unit following the approach described in the paper. We are also interested to observe the extent to which the size of the training data in uences the overall performance. In addition to product reviews,we train our language model on lyrics and emails. We want to see if a language model can also learn to recognize different semantic concepts, such as the mood of lyrics or to classify if an email is spam, with one single unit. While we do not quite reach the results of the paper, our model's best results approximates them. We also analyse the existence of such specific semantic units in other areas of text analysis. Furthermore, we describe a process with which we can identify potential semantic units in language models.
• Patrick Bühler
  GTFS-Editor  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Verkehrsbetriebe können die Daten ihrer Fahrpläne in Form von GTFS-Dateien (General Transit Feed Specification) im Internet bereitstellen. Diese sind in der Form von CSV-Textdateien in einer Zip-Datei gespeichert. Diese Dateien zu verändern kann ziemlich mühselig sein, da die Textdateien in den meisten Fällen sehr groß und unübersichtlich sind. Deswegen wäre es vorteilhaft, wenn man einen Editor hätte, mit dem man diese Feeds einfach verändern könnte. Dieser GTFS-Editor soll einfaches und benutzerfreundliches Editieren der Daten ermöglichen.
• Samuel Roth
  Identification and Information Extraction on Scientists Homepages in the Common Crawl Web Archive  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Aim of this work is the development of a system to detect personal Webpages of scientists and extract structured data - the scientist name, affiliation, gender, profession - from these personal Webpages. In addition we detect occurrences of the scientists in other Webpages text to use these texts as information sources for search queries about the scientist in question. As a source for raw data we use Common Crawl1 - an open Web archive of 3.16 billion+ crawled Webpages. For the classification task we reviewed recent work on categorizing Webpages and implementedWeb-specific features to train a supervised binary classifier using existing and manually labeled training data. To extract the correct name we utilized Named Entity Recognition techniques and Support Vector Machines with special features for gender, profession and affiliation combined with available lookup tables to improve performance. Finally we use the retrieved data to create a Broccoli [1] index so we can use the data to search for existing scientists in different contexts.
• Yannick Ries
  Programmierumgebung für den Informatikunterricht an Gymnasien  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  An Gymnasien in Baden-Württemberg wird der Informatikunterricht stark ausgebaut. Für den Unterricht werden neue, zeitgemäße und didaktisch sinnvolle Werkzeuge benötigt. Diese Arbeit befasst sich daher mit der Erstellung einer Programmierumgebung für den Unterricht. Zu diesem Zweck wurden zunächst Anforderungen an eine Programmierumgebung im Umfeld der Schule analysiert und bereits existierende Programmierumgebungen auf diese Anforderungen geprüft. Unter Beachtung der ermittelten Anforderungen und mit Kenntnis der wertvollen Komponenten der Alternativen wurde eine Programmierumgebung mithilfe des PyQt Frameworks erstellt. Sie erlaubt den Schülerinnen und Schülern (SuS) die praktische Auseinandersetzung mit den informationstechnischen Inhalten des Lehrplans mit Python. Sie bietet dabei zahlreiche, das Verständnis fördernde Features wie schrittweise Ausführung des Codes, schülergerechte Fehlermeldungen und Visualisierung des Schülercodes. Abschließend wurde die Programmierumgebung mit einer Schülergruppe im Unterricht getestet und evaluiert.
• Niklas Baumert
  Web-scalable Named-entity Recognition and Linking with a Wikipedia-backed Knowledge Base  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  This thesis is about WiNERLi, a software to solve the named-entity recognition and the entity linking tasks. It does so by utilizing a knowledge base built from Wikipedia. Its major function is to provide input files for QLever1, another system at the department. In the following I will define the named-entity recognition and entity linking tasks and take a look at how other studies tackled the tasks. A central aspect of WiNERLi is its Wikipedia-backed knowledge base. The knowledge base is built by extracting page titles, links and infoboxes from Wikipedia pages. WiNERLi uses sub-sequences of variable lengths to determine entities by querying those against the knowledge base. I performed general tests in entity detection, entity categorization and entity linking with two datasets. Its performance in those general tests is not particularly high. It has F1-Scores of 0.3810–0.4768 in entity detection; 0.1712–0.3912 in entity categorization; and 0.2857 in entity linking.
• Michael Lubitz
  Who drives the market? Sentiment analysis of financial news posted on Reddit and Financial Times  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  In this thesis, we evaluate whether the sentiment in financial news articles posted on Reddit can predict future stock market returns. For this purpose, we extracted all submissions that have been posted on the economics subreddit between January 2008 and July 2017. We evaluate the predictive power of Reddit by comparing the sentiment of all submitted articles posted on a trading day to the corresponding closing value of the S&P 500 stock index. The sentiment in these articles is calculated using a dictionary-based approach and supervised machine learning models based on different feature extraction methods. In addition, we perform a weighted sentiment calculation by incorporating the number of votes and comments for Reddit submissions into our models. News published in the Financial Times will act as a baseline. Our results suggest that the predictive power of Reddit is slightly better than using standard news paper analysis. We achieve 56.49% of accuracy in predicting the future direction of the stock market which corresponds to the results of recent academic research.

2017

• Jon Ezeiza Alvarez
  A review of word embedding and document similarity algorithms applied to academic text  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Thanks to the digitalization of academic literature and an increase in science funding,the speed of scholarly publications has been rapidly growing during the last decade. This is obviously very positive, but it leads to a few logistical problems we have been tackling lately. Article availability is, for the most part, a solved problem, a scientist can get access to virtually any publication on demand. There’s also a very comprehensive tool-set for retrieval of relevant articles by now and the last couple of years have seen a further surge, with a new wave of AI based retrieval tools. However, the latest global surveys about reading patterns suggest that it is now harder than ever for a professional scientist to keep up. There is no human endeavor that is better publicly documented than scientific progress, yet, we are starting to loose the grasp of it. It is no longer viable for a single person to keep a global view of science, not detailed enough or updated enough to be useful at least. Conversely, recent advancements in natural language processing (NLP) and high volume distributed computation are starting to open the door to an alternative. We propose the long term goal of creating an automatic toolbox for indexing, understanding and interpreting all scientific literature. This work is intended to be a small early step in that direction. Word embeddings, which facilitate working with abstract semantic concepts in numerical form, have become the foundation of modern NLP. Here we perform a thorough review of the most pivotal word embedding algorithms and perform an empirical evaluation on academic text to identify the best alternatives for the described use case. We also extend the concept of word embeddings to documents. We perform a similar review of recent document modeling algorithms and evaluate them on titles, abstracts and full articles.
• Jxxxxxx Pxxxxx
  Entwicklung einer vernetzten Bilderbuch-Anwendung für ältere Menschen mit geringer Medienkompetenz  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Das Thema dieser Bachelorarbeit ist die Entwicklung einer Anwendung, die älteren Menschen, mit niedriger Medienkompetenz, das Betrachten von digitalen Fotoal-ben ermöglichen soll. Durch eine einfache und intuitive Bedienung der Anwendung wurde versucht dies zu erreichen. Gegenüber klassischen, physischen Bilderalben hat das Programm den Vorteil, dass digitale Bilderbücher über das Internet an die Betrachter versandt werden können. Außerdem ist das nachträgliche Editieren und Ergänzen dieser möglich. Um die Bedürfnisse der Nutzer und deren Anforderungen an die Anwendung verstehen zu können, wurde durch eine Recherche erörtert, welche Probleme und Hürden ältere Menschen bei der Benutzung moderner Computertech-nologien haben. Anschließend wurde die sogenannte Persona-Methode angewandt, in welcher mithilfe von Anwenderprofilen, die verschiedene Nutzergruppen vertreten, die jeweiligen Anforderungen der Nutzer bestimmt wurden. Das gewonnene Wis-sen ist in die Entwicklung des Programms eingeflossen. Durch eine anschließende Evaluation wurde geprüft, inwiefern die entwickelte Anwendung den Anforderungen entspricht. Das Ergebnis der Evaluation bestätigte die Nutzbarkeit des Programms.
• Daniel Bindemann
  Erweitern von Aqqu durch AutoSklearn  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Seien es autonom fahrende Autos, Systeme für präazise Gesichtserkennung oder intelligente Anti-Spam-Filter – Eine Vielzahl heutiger Technologien verdankt ihren Erfolg den Fortschritten im Bereich des maschinelles Lernens. Ein Gebiet der Informatik, dessen Erfolg unter anderem auch auf maschinellem Lernen basiert, ist das Natural Language Processing (zu Deutsch auch als Computerlinguistik bezeichnet). In diesem Gebiet wird versucht, natürlichsprachliche Ausdrücke mit Hilfe des Computers zu analysieren und deren Bedeutung zu interpretieren, um zum Beispiel auf natürlichsprachliche Fragen die passende Antwort in einer Sammlung von Daten finden zu können. Insbesondere für Nutzer, welche nicht im Bereich der Informatik versiert sind und ihre Fragen nicht in formalen Abfragesprachen wie SQL oder SPARQL ausdrücken können, könnten solche Systeme es möglich machen, benötigte Informationen schnell und einfach durch einen kurzen Satz im Internet ausfindig zu machen. Aber auch Nutzer, welche formale Abfragesprachen beherrschen, könn- ten von solchen Systemen profitieren, da sie ohne Wissen über die genaue Art der Datenspeicherung und ohne umständliche Anfragen effizient Informationen aus Wis- sensdatenbanken extrahieren könnten. Da das maschinelle Lernen ein zentraler Bestandteil für den Erfolg solcher natürlich-sprachlicher Suchmaschinen ist und in vielen kürzlich entworfenen Systemen verwendet wird, wäre es ein sinnvoller Versuch, diese Systeme durch Fortschritte im Bereich des maschinellen Lernens zu erweitern. Das Ziel dieser Arbeit ist es, ein erfolgreiches System für das Beantworten natürlich-sprachlicher Fragen, Aqqu , mit einem modernen Toolkit für automatisiertes maschi- nelles Lernen,auto-sklearn, zu erweitern. Dadurch soll erreicht werden, dass Aqqu einen größeren Anteil an Fragen korrekt beantworten kann bzw. bei Fragen mit mehreren möglichen Antworten die Menge der korrekten Antworten präziser ausfindig machen kann. Im Folgenden stelle ich zunächst die Funktionsweise und wichtigsten Features dieser zwei Systeme vor (zusammengefasst aus den zugehörigen Papers [1] und [2]). Im Anschluss beschreibe ich meine Ansätze, um die Systeme miteinander zu verbinden und evaluiere schließlich die Ergebnisse dieser Ansätze.
• Claudius Decker
  Name Entity Recognition  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Das Thema dieser Bachelorarbeit ist die Entwicklung einer Anwendung, die Named Entities in natürlich-sprachlichen Texten erkennt und mit ihrem korrespondierenden Eintrag in einer Wissensbasis verbinden kann. Named Entities sind Objekte der realen Welt, wie Personen, Organisationen oder Orte, die mit einem Eigennamen bezeichnet werden. Die Erkennung der Named Entities wird mit zwei Algorithmen des maschinellen Lernens, dem Perzeptron und der logistischen Regression, umgesetzt. Dabei wird versucht, die Resultate durch ein Entity-Linking-Feature zu verbessern. Die beiden Algorithmen werden hinsichtlich ihrer Performanz ausgewertet und in ihrem theoretischen Hintergrund beleuchtet. Dabei zeigt sich, dass das Perzeptron in dieser speziellen Aufgabe der logistischen Regression überlegen ist. Während mit dem Perzeptron ein maximaler F1-Score von über 0,99 erreicht werden konnte, liegt der mit der logistischen Regression erreichte, maximale F1-Score bei 0.82.
• Zhiwei Zhang
  Public-Transit Data Extraction from OpenStreetMap Data  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  The major objective of this paper is to acquaint the reader with details on how to extract public transit data from OpenStreetMap 1 (OSM) data. To achieve this aim, we implement a program extracting train-related data from an OSM file and introduce its development to help the reader understand our method. Its development is broken into three basic incremental steps. In the first step, we search for the information related to trains with the assist of some particular attributes and store it into a railway network. In the second step we fix attention on completing the network step by step through solving some problems, i.e., incorrect order, gaps, missing class label and so on. In the last step we transform the network into a General Transit Feed Specification 2 (GTFS) feed. Through uploading the feed to Transit Visualization Client 3 (TRAVIC) and OpenTripPlanner 4 (OTP), this network turns visible and we can run some routing test. The visible displayed result in TRAVIC and test result in OTP demonstrate that our method works as expected. Due to the limitation of OSM data, some gaps are irreparable and bias exists in distinguishing between regional railway and long-distance railway. Therefore, further research is needed to improve the performance of this method.
• Phong Tran
  Semantischer Vergleich von Fahrplandaten  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Diese Bachelorarbeit beschäftigt sich mit der Entwicklung eines Programms, dass den Vergleich von zwei Fahrplandaten im GTFS (General Transit Feed Specification)Format ermöglicht. Viele Verkehrsunternehmen veröffentlichen ihre Fahrpläne als GTFS Feeds. Möchte man nun zwei Feeds zusammenfügen kann es zu Überschneidungen bei den Trips kommen, falls diese Feeds das gleiche Gebiet abdecken. Unser Programm vergleicht zwei gegebene Feeds und gibt Informationen zu abweichenden Servicezeiten, fehlenden Fahrten und Haltestellen aus. Diese Informationen können dann anschließend von weiteren Programmen verarbeitet werden.
• Eneko Pinzolas Murua
  Word Embeddings in Search Engines, Quality Evaluation  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  n the recent years, Neural networks have become very popu- lar. They are being used in almost any field of computer science, and several of them are turning out to be successful. Information retrieval requires a fast method that compares two batches of text and gives a score. That score has to represent how similar both texts are. Most approaches rely on basic text comparisons, while trying to grab extra information from the users to cater the results more to their liking. In this bachelor thesis, we propose the addition of neural network techniques to the comparison process. More specifically, the usage of word vectors. Revolving word vectors, various techniques have been documented and tested, and while most of them did not have positive results, the one that did has been more thoroughly analysed. The approach that is presented here relies on representing queries and documents as clusters of words, which are points in space. Then, to quickly compute the score, the average linkage has been selected as a comparison method, that is, the distance between the means of the clusters. This approach has given positive results over the baseline in both test databases, and the results have been documented below. The results show a high potential in the use of word vectors in the IR area.

2016

• Maximilian Dippel
  "Erkennung von Textparagraphen in wissenschaftlichen Publikationen mit Techniken des maschinellen Lernens"  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  m Rahmen dieser Arbeit werden Methoden zur automatisierten Erkennung und Visualisierung von menschlich-intuitiven Paragraphen in wissenschaftlichen Publikationen behandelt. Diese extrahierten Paragraphen sollen fur weitere Verwendungszwecke wie etwa eine Klassifizierung der Paragraphen in Uberschriften, Bildunterschriften, inhaltlichem Fließtext etc. bereitgestellt werden. Ferner sollen Teile der so klassifizierten Paragraphen perspektivisch als Basis einer semantischen Suche dienen. Es werden verschiedene Techniken des maschinellen Lernens eingesetzt und ihre Ergebnisse evaluiert. Hierzu werden geeignete Featurevektoren und entsprechende Trainingsdaten erstellt. Wir werden sehen, dass Support Vector Machines mit einer Precision von 0.98 und einem Recall von 0.98 die besten Ergebnisse liefern.
• Daniel Siebrecht
  Entwicklung eines Seniorenhandys auf der Basis einer Android App  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Die vorliegende Arbeit beschäftigt sich damit, existierende Smartphones durch eine Anwendung (App) auf ein Minimum an Funktionalität zu reduzieren, um die Bedienung für Senioren und Menschen mit Einschränkungen zu vereinfachen. Dazu wurde untersucht, welche sensorischen, körperlichen und geistigen Einschränkungen die Bedienung eines Smartphones beeinflussen können und welche Designaspekte diesen bei der Gestaltung der App entgegenwirken können. Außerdem wurde betrachtet, welche Anforderungen Senioren an ein Handy haben. Bezugnehmend auf diese Ergebnisse wurde eine App entwickelt, welche die Benutzeroberfläche von Android durch eine einfache Darstellung ersetzt. Die App verfügt außerdem über einige Assistenzfunktionen für den Nutzer, auf welche eine autorisierte Person über ihr eigenes Handy und eine separate App zugreifen kann. Zur Evaluation der App wurde überprüft, inwieweit die herausgearbeiteten Designaspekte umgesetzt wurden. Abschließend wurde getestet, ob Senioren ohne Smartphone-Kenntnisse die App bedienen können.
• David Spisla
  Erkennung von Fließtext in PDF-Dokumenten  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Diese Arbeit beschreibt ein Verfahren zur Erkennung und Extraktion von Fließtext in PDF-Dokumenten. Eine Extraktion von Fließtext erleichtert die inhaltliche Suche nach Informationen in einem PDF. Das Verfahren nutzt Techniken des Maschinellen Lernens, um den Fließtext in einem ersten Schritt von den übrigen Bestandteilen (Tabellen, Bil- der,Überschriften, Referenzen, usw.) auszusondern. Dies erleichtert den zweiten Schritt,in welchem zusammengehörende Abschnitte, die z.B. durch Bilder oder ein Seitenende getrennt werden, erkannt und zusammengeführt werden. In beiden Schritten wird die Erkennung mittels sorgfältig ausgewählter Featurevektoren ermöglicht. Dies ermöglicht zum Schluss eine Zusammenführung aller Fließtextelemente, die dann für eine inhaltliche Suche genutzt werden können. Trainings- und Testphasen werden mithilfe der Python- Bibliothek scikit-learn durchgeführt, welche eine Reihe von bekannten Lernalgorithmen bereitstellt. Die empirische Analyse hat für alle Lernmodelle nahezu identische Ergebnisse ergeben. 2 Varianten (einmal je 100 Trainings- und je 100 Testdaten und einmal 200 Trainingsdaten, die auch als Testdaten verwendet werden) werden ausgetestet. Bei Variante 1 werden für die Erkennung von Fließtext folgende durchschnittliche Analysewerte ermittelt: precision = 98 %, recall = 98 % und f1-score = 98 %. Bei Variante 2 liegen diese Werte alle bei 97 %. Für die Erkennung der zusammengehörenden Abschnitte werden in allen Analysewerten 100 % erreicht. Aufgrund der g ünstigen Laufzeit kommt das Lernmodell Bernoulli Naive Bayes im eigentlichen Extraktions-Programm zur Anwendung
• Matthias Urban
  Extended Question Answering on Freebase  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Diese Bachelorarbeit beschäftigt sich mit Erweiterungen an dem Question Answering System (dt. Fragebeantwortungssystem) Aqqu [2]. Aqqu ist in der Lage einfache, natürlichsprachliche Fragen in SPARQL-Abfragen für die Wissensdatenbank Freebase zu übersetzen. Wenn man diese SPARQL-Abfragen ausführt, erhält man die Antwort auf die entsprechende Frage. Bisher war Aqqu nicht in der Lage Superlativ-Fragen wie “Was ist das größte Land in Europa?” oder Temporal-Fragen wie “Wer war der erste Präsident der Vereinigten Staaten?” zu beantworten. Aqqu konnte außerdem nur Fragen beantworten, deren SPARQL-Abfrage nur aus einer (möglicherweise k-ären) Relation besteht. Deshalb konnten Fragen wie “Wer ist die Frau des Präsidenten der Vereinigten Staaten?” nicht beantwortet werden. Im Folgenden werden diese Probleme mit mehreren Erweiterungen an Aqqu gelöst, sodass Aqqu in der Lage sein wird Fragen dieser Typen zu beantworten. Des Weiteren ist das Answer Type Matching (dt. Antworttyperkennung) von Aqqu sehr einfach gehalten. Es wurde nur das Fragewort betrachtet. Diese Bachelorarbeit stellt ein verbessertes Answer Type Matching vor. Dieses basiert auf Machine Learning und betrachtet eine Reihe verschiedener Features (dt. Merkmale). Es funktioniert mit den Typen von Freebase und ist in der Lage die Antworttypen von mehr Fragen richtig zu bestimmen.
• Elke Schächtele
  Inhaltsbezogene Suche nach gleichartigen Klängen  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  In der vorliegenden Arbeit wurde ein Algorithmus für die inhaltsbezogene Suche nach gleichartigen Klängen implementiert. Eine Suchanfrage wird in Form einer Beispieldatei gestellt. Zu dieser sollen ähnlich klingende Audiodateien in einer Datenbank gefunden werden. Entscheidend für die Realisierung dieses Suchszenarios ist die Beantwortung der Frage, anhand welcher Merkmale zwei Klänge als ähnlich beurteilt werden können. Im Gegensatz zu einem Großteil der bisherigen Forschungsarbeiten wird in dieser Arbeit eine umfangreichen Literaturübersicht über verschiedene Forschungsperspektiven auf das Phänomen Klang und dessen Wahrnehmung durch den Menschen der Implementation des Algorithmus voran gestellt. Der Algorithmus wird anhand eines Benchmarks evaluiert, der mithilfe von empirischen Daten erstellt wurde. Das Resultat legt nahe, dass der typische Aufbau eines Algorithmus für die inhaltsbezogene Suche nach gleichartigen Klängen der menschlichen Wahrnehmung nur teilweise gerecht werden kann. Die Ergebnisse stehen im Einklang mit Erkenntnissen vergleichbarer Arbeiten: In diesen wurde in jüngster Zeit aufgrund der Komplexität des Forschungsgebiets zunehmend die Notwendigkeit des Ausbaus von interdisziplinärer Forschung betont.
• Natalie Prange
  Query Auto-Completion using an Abstract Language Model  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  In recent years, query auto-completion has become a common feature of search engines. While typing a query into a search engine’s input field, the user receives suggestions as to how his query could be completed or extended. Most approaches towards this issue rely on query logs in order to provide meaningful completion suggestions. Sufficiently large and recent query logs, however, might not be available for researchers or search engines with a small user base. Moreover, purely rely-ing on query logs means that queries which have not been seen before will not be suggested. In this bachelor thesis, we propose a novel approach using an abstract language model in which specific entities have been replaced by abstract categories. When at some point during query completion the language model suggests such a category as the most likely word to follow, it is replaced by an entity assigned to the same category. The possible entities are ranked using an entity prominence score and word vector similarity. The top k completions are o˙ered to the user as completion suggestions. We analyzed our approach on three datasets. For each dataset, we compared di˙erent versions of our query auto-completion algorithm to a baseline given by a basic version of our algorithm. The results illustrate the role of di˙erent components of our algorithm and indicate a high quality of our completion suggestions.

2015

• Rick Gelhausen
  Context-Aware Search Spaces for Queries with Spatial Relations  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Web-mapping services, like Google Maps, allow natural language queries, like \Hotels Freiburg". These queries are interpreted as \Hotels in Freiburg" or \Hotels near Freiburg". In this thesis, we introduce the two new spatial relation \between" and the compass directions, allowing queries like \Gas stations between Freiburg and Stuttgart" or \Hotels north of Freiburg". To achieve this, we analyse many different queries and decide whether they make sense in a given context. It might make sense to search for \cities between cities", whereas it makes less sense to search for \cities between countries". Then, we create a toolbox that returns a search polygon for every context-aware query. In a last step, we compare the results from our toolbox with our expectations. We show that nearly all of our queries return useful results and conclude what possibilities are open for future work.
• Simon Weidner
  Fine-Grained Population Estimation  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  This thesis introduces a new method to estimate population numbers for areas of various sizes. The main idea is to estimate population numbers of buildings by exploiting their environment. For this we use features as the count of nearby schools, supermarkets and many more. We obtain such data from OpenStreetMap, which is a volunteered project providing Google-Maps-like data. State of the art approaches mainly rely on costly three dimensional images and/or census data of the local areas. We use machine learning to predict population values. Therefore, our method can be used without local census data. For evaluation purposes we compared our results to the official census data of various cities, districts and villages. Our results indicate that our method basically works, but requires further research especially to distinguish between different types of houses more precisely.
• Jerôme Meinke
  In-memory OLAP aggregation on GPUs using CUDA Dynamic Parallelism  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Most queries involved with Online Analytical Processing (OLAP) depend on the functionality of aggregating data along the multidimensional hierarchies of an OLAP cube. In real-time OLAP, aggregated data for interactive operations e.g. roll-up and drill-down is computed on-the-fly. Fast response times are essential and can be accelerated significantly through data-parallel computation on graphics processing units (GPUs). In this thesis, an existing parallel algorithm is modified to use a technology called CUDA Dynamic Parallelism (CDP). Using this technology, GPU programs can be launched directly from within other GPU programs to extract more parallelism. Furthermore, we present a preaggregation method using the CUDA shuffle command to optimize both GPU implementations. For evaluation purposes, we additionally implement a sequential aggregation algorithm. Our experiments show that the single-threaded CPU implementation is outperformed by the GPU implementations by 16 to 218 times. The experiments further show that the CDP implementation reaches a speedup of 3.72 times over the non-CDP implementation when processing queries for an artificial OLAP cube. However, using CDP causes an average of 1.42x slowdown to the processing of queries in a typical OLAP scenario.
• Vivica Wirth
  Kostenrundung von Kanten auf Pfaden  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Diese Arbeit beschäftigt sich damit, Kosten an Kanten in Graphen zu runden. Grundlage dabei ist das mathematische Runden der einzelnen Kanten. Da dieses aber beliebig schlecht werden kann, soll ein besserer Algorithmus gefunden werden. Diese Arbeit befasst sich zunächst mit dem mathematischen Runden, um herauszufinden wo und wie dieses scheitert. Danach werden eigene Ideen entwickelt und präsentiert. Über alternierendes Runden, bei welchem Kanten abwechselnd auf- und abgerundet werden, gelangt man zu gewichtetem Runden. Bei diesem wird sich der Rundungsfehler gemerkt und in Abhängigkeit vom Rundungsfehler gerundet. Die empirische Auswertung zeigt dabei, dass das gewichtete Runden deutlich besser ist, als das mathematische Runden.
• Matthias Hertel
  Partitioning of Public Transit Networks  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  artitionierungen von öffentlichen Verkehrs-Netzwerken werden verwendet um die Berechnungszeit von Routen oder die Vorberechnungszeit bei Routenplanungs-Algorithmen zu beschleunigen. Das Ziel der Partitionierung ist es, kleine Partitionen der Haltestellen zu finden, die möglichst viel Verkehr in ihrem Inneren beinhalten, sodass möglichst wenige Verbindungen zwischen den Partitionen verkehren. Um solche Partitionen für das öffentliche Verkehrs-Netzwerk von Deutschland berechnen zu können, wird das öffentliche Verkehrs-Netzwerk als Graph modelliert, wobei Knoten Haltestellen repräsentieren und Kanten mit der Häufigkeit gewichtet werden, mit der Fahrzeuge zwischen den Haltestellen verkehren. Mit k-means-clustering, einem Fusions-basierten Algorithmus, partitioning using natural cut heuristics (PUNCH, engl. für “Partitionierung unter Verwendung von natürlichen Schnitt-Heuristiken”), und METIS werden vier Graph-PartitionierungsAlgorithmen getestet und mit einem Datensatz ausgewertet, der die Fahrpläne der Deutschen Bahn für das Jahr 2015 beinhaltet. Ergebnis der Auswertung ist, dass der Fusions-basierte Algorithmus und METIS kurze Laufzeiten haben und kleine Partitionen mit einem kleinen Schnitt erzeu- gen. K-means-clustering löst das Problem besser als erwartet. PUNCH wurde für ungewichtete Graphen entwickelt und benötigt einige Anpassungen für gewichtete Graphen.

2014

• Iradj Solouk
  A keyword query translator for Broccoli  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  A keyword query translator that is used by the semantic text search engine BROCCOLI will be introduced. This keyword translator interprets a string, which is given by the user, in a way that considers the underlying data structure of BROCCOLI and tries to consider the context of the given information. A GOOGLE-like keyword search field will be used. The keyword translation leads to user friendliness in terms of not requiring knowledge about the concept of the underlying ontology and the possibility of using keywords or parts of phrases as an input. This process provides a service that can be used in place of the normal incremental query creation process. The semantic interpretation of the input string requires natural-language-processing. WordNet, a lexical dabase for English words, and the Stanford part-of-speech tagger is used for part-of-speech tagging.
• Manuel Ruder
  Entitätserkennung auf einem Web-Korpus  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Broccoli ist eine semantische Suchmaschine, die für das Durchsuchen der englischsprachigen Wikipedia entwickelt wurde. In einer früheren Arbeit wurde damit begonnen, broccoli für das Durchsuchen allgemeiner Web-Seiten zu erweitern. Hierzu mussten sowohl der Entitätserkenner als auch die Komponente zum Parsen der Seiten angepasst bzw. verallgemeinert werden. Hierbei zeigten sich einige Schwierigkeiten, wie etwa eine hohe Zahl an Falscherkennungen von Entitäten. In dieser Arbeit soll die Qualität der Suche durch einen verbesserten Entitätserkenner gesteigert werden. Dazu wurde unter anderem die Erkennung von Eigennamen verbessert. Ein neu geschriebener Disambiguationsalgorithmus soll zudem im Text vorhandene Mehrdeutigkeiten auflösen. Durch eine ebenfalls neu geschriebene Evaluations-Komponente können Falscherkennungen genauer untersucht werden als bisher. Für die Evaluations-Komponente wurde eine Auswahl an Artikeln aus dem Korpus mit Ground Truth Annotationen versehen.
• Marcel Gangwisch
  Entwicklung von Algorithmen zur Berechnung der aerodynamischen Oberflächenrauigkeit für mikroskalige Strukturen  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Das thermische Wohlbefinden der Bewohner einer Stadt wird durch unterschiedliche meteorologische Größen beeinflusst. Eine wichtige Steuergröße stellt die Windgeschwindigkeit dar, da durch eine erhöhte Windgeschwindigkeit eine Reduzierung der thermischen Belastung stattfinden kann. Die bewegten Luftmassen in der Atmosphäre über einer Stadt werden durch die geometrischen Eigenschaften der Erdoberfläche beeinflusst. Insbesondere stellen Gebäude und die Vegetation ein Hindernis für die durchströmende Luft dar. Diese Wirkung wird durch die aerodynamische Oberflächenrauigkeit ausgedrückt. Zur Beurteilung dieser Wirkung wurden in der Arbeit verschiedene Ansätze zur Berechnung der Rauigkeit miteinander verglichen. Im Anschluss daran wurde das mikroskalige Modell “SkyHelios” vorbereitend für räumliche Berechnungen um eine räumliche Datenbank erweitert um das Management der Daten zu verbessern. Nachfolgend konnten der “Morphometrische Ansatz” (Lettau 1969), der “Effektive Höhen Ansatz” (Matzarakis und Mayer 1992; Mayer und Matzarakis 1992), sowie der “vereinfachte Ansatz” (Gál und Sümeghy 2007; Gál und Unger 2008) zur Berechnung der aerodynamischen Oberflächenrauigkeit implementiert werden. Dafür wurden die Daten in die Datenbank eingelesen und für jedes Gebäude mit der Rotationsmatrix für den zweidimensionalen Raum die frontale Fläche berechnet. Um eine räumliche Differenzierung der Oberflächenrauigkeit zu erhalten, wurde für jedes Gebäude eine Voronoizelle auf Basis der Gebäudeform berechnet. Im Anschluss daran konnte jeweils die Rauigkeit des Gebäudes auf Basis der Gebäudegeometrien bestimmt werden. Abschließend wurde das Verfahren für ein Modellgebiet in Stuttgart angewendet. Es wurden sowohl windrichtungsunabhängige Rauigkeitslängen, sowie effektive Höhen als auch windrichtungsabhängige Rauigkeitslängen berechnet. Die Ergebnisse der drei Ansätze wurden jeweils analysiert und miteinander verglichen.
• Philipp Bausch
  Semantische Suche auf einem WEB-Korpus  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Broccoli ist eine auf den Texten von Wikipedia basierte Suchmaschine, welche das Durchsuchen dieser Texte mit dem Durchsuchen von strukturierten Daten (z.B. Ontologien) vereint. Wikipedia beinhaltet aber oft keine Berichte und Beschreibungen für einzelne kleinere Ereignisse. Eine in Politik interessierte Person ist vielleicht auf der Suche nach bestimmten Steuererhöhungsbeschlüssen oder -vorschlägen in den USA. Auf Wikipedia sucht man nach diesen Informationen oft vergebens. Aus diesem Grund wird in dieser Arbeit darauf eingegangen, wie die bisher von broccoli verwendeten Wikipedia Texte durch ein allgemeineren Web-Korpus ersetzt werden. Dieser wurde aus den von CommonCrawl 2012 veröffentlichten Datensatz extrahiert. Dazu ist es nötig die Texte von HTML Formatierungen zu befreien, da die von CommonCrawl angebotenen HTML-losen Texte nicht gezielt abrufbar sind und die Navigation enthalten ist. Hierzu wurde das Programm boilerpipe verwendet. Der Datensatz umfasst 3,8 Milliarden Seiten, die für jeden frei zugänglich sind. Außerdem wird beschrieben, wie Entitäten in den Texten erkannt werden, da dies bisher mit vielen Annahmen über die Strukturen in Artikeln von Wikipedia gelöst wurde. Um die Funktionsweise zu demonstrieren, wird dies für einen Korpus von rund 4,5 Millionen Webseiten untersucht. Dieser besteht aus rund 4 Millionen Seiten der TLD1 .edu und aus den Archiven von 20 Nachrichten Seiten.
• Christian Ehrenfeld
  Touchscreen-basierte Bedienkonzepte am Beispiel eines Bedienpanels für Frequenzumrichter  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Diese Abschlussarbeit behandelt die Besonderheiten der Bedienung von berührungs- empfindlichen Anzeigen. Es wird gezeigt welche Möglichkeiten touch-bedienbare An- zeigen durch ihre direkte Steuerung bieten und welchen Einschränkungen sie unter- liegen. Für das Gestalten von Benutzeroberflächen für Touchscreens werden bewähr- te Methoden geschildert und der Unterschied zu Benutzeroberflächen, die mit Maus und Tastatur bedient werden, gezeigt. Auf der Grundlage dieser Erkenntnisse wurde die bestehende Benutzeroberfläche der Anwendung TruControl Power, welche für die Bedienung mit der Maus und Tastatur konzipiert wurde, so optimiert, dass diese auf einem Bedienpanel mit einem Touchscreen verwendet werden kann. Anschlie- ßend wurde eine Benutzerstudie durchgeführt um Bedienbarkeitsprobleme bei der Benutzung des Bedienpanels in Erfahrung zu bingen und beheben zu können.

2013

• Marius Stefan Bethge
  Detecting Duplicate Entities for Ontology Reconciliation  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Die stetig wachsende Nachfrage nach Ontologien, in Verbindung mit dem Vorhaben mancher Ontologien das menschliche Wissen über alle Gebiete hinweg zu vereinigen, führt zur immer größer werdenden Datenmengen. Diese domänenübergreifenden Ontolgien, wie z.B. Freebase, sammeln Daten von diversen Quellen, welches je- doch leicht dazu führen kann, dass mehrere Einträge für ein einzelnes Objekt der reellen Welt stehen können. Wir stellen einen Algorithmus vor, welcher durch Iden- tifizierung und Vereinigung von duplikaten Entitäten die Anzahl an duplikaten Ein- trägen in einer Ontologie vermindert. Es war uns möglich eine hohe Präzision mit einer beachtlichen Anzahl an Vereinigungen zu erreichen. In einer angepassten, auf Freebase Daten basierenden Ontologie mit 50 Millionen Entitäten war es uns möglich 1,2 Millionen Duplikate zu identifizieren.
• Axel Lehmann
  Ein Kursverwaltungssystem für programmierlastige Lehrveranstaltungen  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Daphne is a Coursemanagement System which is focused on programming courses. This work describes provided features and the required technical background. Daphen is used to manage participants, credits and deadlines. Using Subversion as verson control system and Jenkins to validate submission and provide feedback to participants.
• Anton Stepan
  Entity Unification for Semantic Search  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  In this paper we introduce and investigate a method to unify ontology datasets with location based data. The goal is to generate a bigger and more complex input set for semantic search engines. Our research explains a possible unification framework to solve this problem, outlines arising obstructions and demonstrates our algorithm with an application and an unification framework. The framework is based on the idea of awarding scores in the unification process, gathered from matching relations and only unifying two entities if they reach a specific score threshold. These scores and thresholds are very flexible as the user can define them in a config file, with the objective to tweak the result or set a specific weighting on a particular comparison category. With an experiment we review the performance and quality of our approach by unifying two datasets, based on Geonames (37 MB) and Freebase (244 MB) and achive more than 50% unification of the smaller ontology with an average execution time of 20 seconds.
• Benjamin Malte Meier
  High-Level Feature Extraktion aus Bewegungsdaten von Parkinson-Patienten  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Seit über 20 Jahren wird untersucht, auf welche Weise Beschleunigungssensoren als Diagnose- und Therapieunterstützung für die sich als Bewegungsstörung manifestie- rende Parkinson-Krankheit eingesetzt werden können. Immer komplexere Sensoren und bessere Bewegungsmodelle in silicio erlauben es, diese Ansätze fortzuführen und die Bewegungen von Parkinson-Patienten als Ganzes zu untersuchen, anstatt anstatt sich auf einzelne Bereiche zu konzentrieren. Diese Arbeit steht am Beginn dieser Untersuchung und dokumentiert die Extraktion und Auswertung von ersten, komplexen High-Level Features aus Bewegungsdaten. Es werden zum Beispiel die Geschwindigkeit und die Positionen einzelner Körperteile verwendet, um die Posi- tionen einzelner Schritte oder die Vorwärtsneigung beim Gehen zu bestimmen. Mit einem Fokus auf die Auswertung der Schrittlänge beim Gehen, werden nicht nur Unterschiede zwischen Parkinson-Patienten und gesunden Versuchspersonen darge- stellt, sondern auch weitere Ansätze zur Analyse von Bewegungsdaten gezeigt.

2012

• Christiane Schaffer
  Automatische Relationsextraktion für die semantische Volltextsuche  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Gegegeben seien Daten einer Ontologie. Das Ziel ist es, eine bestehende geografische Relation um zusätzliche Fakten zu erweitern. Dazu soll eine umfassendere, auf die Relation spezialisierte Datenbank verwendet werden. Die Herausforderung dabei liegt in der nicht vereinheitlichten Namensgebung von Ontologie und Datenbank. Da letztere weitaus mehr Fakten speichert als die bestehende Ontologie, müssen Lösungen für auftretende Mehrdeutigkeiten gefunden werden. Es werden verschie- dene Möglichkeiten beschrieben, Zuordnungen für die Relation zu finden, sowie eine Analyse dieser vorgenommen.
• Robin Schirrmeister
  Automatische Vorschläge zur Vervollständigung von Wikipedia Listen - Listenerkennung, Benutzeroberfläche  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Diese Arbeit beschreibt das von Simon Skilevic und mir erstellte Programm WikiListSuggest, dass automatische Vorschläge zur Vervollständigung von Wikipedia-Listen generiert. In der Online-Enzyklopädie Wikipedia gibt es viele Listen zu bestimmten Themen, z.B. die Liste essbarer Blätter. Diese Wikipedia-Artikel werden von Hand erstellt und können unvollständig sein. Unser Programm WikiListSuggest versucht automatisch Vorschläge zur Erweiterung solch eines existierenden Artikels zu erstellen. Dazu versucht es im Wikipedia-Artikel die tätsächliche Liste zu erkennen und, mit Hilfe der semantischen Suchmaschine Broccoli, Vorschläge für weitere in die Liste gehörende Elemente zu generieren. In dieser Arbeit wird hauptsächlich die automatisierte Erkennung der Liste sowie die Benutzeroberfläche beschrieben.
• Simon Skilevic
  Automatische Vorschläge zur Vervollständigung von Wikipedia-Listen - Evaluation,Anfragegenerierung  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Wikipedia-Listen sind Wikipedia-Artikel, die Listen zu einem Thema enthalten. Zum Beispiel enthält die Wikipedia-Liste mit dem Thema „essbare Pilze“ als Lis- tenelemente unterschiedliche Arten von Pilzen, die man ohne Risiko für die eigene Gesundheit verzehren kann. Da solche Listen manuell erstellt werden, können sie unvollständig sein. In dieser Arbeit beschreiben wir ein Programm, WikiListSuggest, das Vorschläge zur Vervollständigung solcher Listen liefert. Dafür extrahiert das Programm entsprechende Listenelemente einer Wikipedia-Liste und generiert automatisch eine Anfrage an die Semantische Suchmaschine “Broccoli”. Durch diese Anfrage soll WikiListSuggest möglichst die vollständige Liste zum Thema der Wikipedia-Liste erhalten. Diese Liste kann dann zur Vervollständigung der Wikipedia-Liste verwendet werden. Schwerpunkte dieser Arbeit sind die Anfragegenerierung sowie die Evaluation.

2011

• Ina Baumgarten
  Semantische Suche - Entitätenerkennung  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  This paper introduces an entity recognition for german articles, which extends the functionality of an already implemented semantic search engine at the University of Freiburg. Entities are defined as unique meaning of words and are stored by using a trie. For achieving a working entity recognition, previous knowledge was generated, consisting of a set of entities, articles and stopwords. Using the previous knowledge the entity recognition is performed in two essential steps: recognition of unambiguous entities and recognition of ambiguous entities. Moreover several methods are used for improving the results: scoring, postagging, stemming and decompounding. The entity recognition assigns with a sensitivity of 82% and an accuracy of 97% the correct meaning to an entity. Excluded are impossible entities, for which no fitting entity exist. In the future it is possible to improve the entity recognition by several modifications.
• Niklas Meinzer
  Semantische Suche in Zeitungstexten  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Im Gegensatz zur klassischen Volltextsuche, bei der wörtliche Vorkommen der Suchanfrage in den durchsuchten Dokumenten gefunden werden, ist die Semantische Suche ein Verfahren, bei dem die Suchanfrage zunächst auf ihre Bedeutung untersucht wird. Ziel ist es, dem Benutzer zu ermöglichen, Anfragen in einer natürlicheren Form zu verfassen und abstraktere Formulierungen zu wählen. Broccoli ist eine existierende semantische Suchmaschine, die zum Beispiel die online Enzyklopädie Wikipedia durchsucht. Wir präsentieren eine semantische Suchmaschine für deutsche Nachrichtentexte, die auf Broccoli aufbaut. Das zentrale Problem hierbei ist die Entitätserkennung in deutschen Texten. Weitere Teilprobleme sind die automatisierte Datenbeschaffung von Online-Ressourcen und das Erstellen der Eingabedaten für Broccoli. In der anschließenden Evaluation der Entitätserkennung erreichen wir konstant sehr gute Werte.

2010

• Mirko Brodesser
  Fast Approximate Title Matching  Präsentation
  » Abstract anzeigen « Abstract verbergen
  Abstract

  Given a set of titles and a query, we want to find the title with the largest similarity to the query. The queries may contain spelling mistakes and words which are not part of the correct entry. Furthermore, no word separators in the query are expected and words of the correct title may be missing. Titles are usually short and consist of multiple words and numbers. We analyse several existing similarity measures like Edit distance and Jaccard similarity. Besides the quality, eÿciency is the other requirement of our algorithm and therefore we analyse and compare the best existing algorithms for eÿcient fuzzy match [CGGM03] and eÿcient duplicate detection [XWLY08]. We propose a new similarity measure as well as algorithm for its eÿcient computation in order to improve the existing algorithms in terms of quality and eÿciency. We show on two di˙erent collections that our algorithm is in most of the cases more eÿcient than the related work, yet achieves better quality.