Hasso-Plattner-Institut
Prof. Dr. Felix Naumann
 

Neue Entwicklungen im Bereich Informationssysteme

Im Rahmen dieses Forschungsseminars stellen Mitarbeiter und Studenten ihre Forschungsarbeiten auf diesem Gebiet vor. Studenten und Gäste sind herzlich eingeladen.

Das Forschungsseminar wird von Christoph Böhm koordiniert.

Termine

  • 26.09.2011, 11:00 - 12:00, A.1-1
    • Benedikt Forchhammer, Thorsten Papenbrock, Thomas Stening, Sven Viehmeier: Duplicate Detection on GPUs
  • 30.08.2011, 11:00 - 12:00, A.1-1
    • Uwe Draisbach: A Generalization of Blocking and Windowing Algorithms for Duplicate Detection
  • 25.08.2011, 11:00 - 12:00, A.1-1
    • Matthias Pohl: Automatisierte Konfiguration des D-Indexes zur Ähnlichkeitssuche (Verteidigung der Masterarbeit)
  • 02.08.2011, 11:00 - 12:00, A.1-1
    • Daniel Hefenbrock: Scalable Peer-to-Peer RDF Data Storage Infrastructure for Analytical Workloads (MA Results)
  • 21.07.2011, 11:00 - 12:00, A.1-1
    • Dandy Fenz: Effiziente Ähnlichkeitssuche in einer großen Menge von Zeichenketten mittels Key/Value-Store (Verteidigung der Masterarbeit)
  • 04.07.2011, 11:00 - 12:30, A.1-1
  • 27.06.2011, 11:00 - 12:30, A.1-1
  • 23.06.2011, 13:00 - 14:30, SNB-E.9/10
  • 21.06.2011, 11:00 - 12:00, A-1.1
    • Mohammed AbuJarour: Automatic Sampling of Web Services (Practice Talk for 9th International Conference on Web Services)
  • 10.05.2011, 14:00 - 15:00, A-1.2
    • Johannes Gosda: Überlappendes Clustering Annotierter Graphen durch Motif-Perkolation (MA Ergebnisse)

Abstracts

  • A Generalization of Blocking and Windowing Algorithms for Duplicate Detection
    Uwe Draisbach

    Duplicate detection is the process of finding multiple records in a dataset that represent the same real-world entity. Due to the enormous costs of an exhaustive comparison, typical algorithms select only promising record pairs for comparison. Two competing approaches are blocking and windowing. Blocking methods partition records into disjoint subsets, while windowing methods, in particular the Sorted Neighborhood Method, slide a window over the sorted records and compare records only within the window. We present a new algorithm called Sorted Blocks in several variants, which generalizes both approaches. To evaluate Sorted Blocks, we have conducted extensive experiments with different datasets. These show that our new algorithm needs fewer comparisons to find the same number of duplicates.
  • Automatisierte Konfiguration des D-Index zur Ähnlichkeitssuche
    Matthias Pohl

    Diese Masterarbeit beschäftigt sich mit der Konfiguration des D-Index, einer metrischen Indexstruktur zum Durchführen der Ähnlichkeitssuche. Es wird ein Verfahren zum Indexaufbau vorgestellt, das die Komplexität des Konfigurationsprozesses reduziert, indem es von den Konfigurationsparametern des D-Index abstrahiert. Mit Hilfe eines genetischen Algorithmus wird eine D-Index-Datenstruktur erstellt, die sich an dem zu indexierenden Datensatz orientiert. Zusätzlich werden zwei Erweiterungen für die Suche nach den k nächsten Nachbarn vorgestellt. Die entwickelten Verfahren werden auf verschiedenen homogenen aber auch heterogenen Datensätzen mit unterschiedlichen Distanzverteilungen getestet. Die durchgeführten Experimente zeigen, dass diese Verfahren im Vergleich zu State-of-the-Art-Algorithmen zu besseren D-Index-Datenstrukturen führen. Nach meinem Dafürhalten wird erstmalig auch die Suche nach den k nächsten Nachbarn umfassend evaluiert.

  • Effiziente Ähnlichkeitssuche in einer großen Menge von Zeichenketten mittels Key/Value-Store
    Dandy Fenz

    Eine effiziente Ähnlichkeitssuche in einer großen Menge von Zeichenketten spielt in vielen Bereichen eine wichtige Rolle. Insbesondere bei der Suche in Texten, der Bioinformatik oder der Signalverarbeitung kommt diese Technik zum Einsatz. Die Ähnlichkeitssuche in einer großen Menge von Zeichenketten versucht dabei Zeichenketten zu identifizieren, die mindestens eine gegebene Ähnlichkeit zu einer Suchanfrage aufweisen. Da es sich meist um zeitkritische Anwendungen handelt, sollten Anfragen in wenigen Millisekunden beantwortet werden können. Vorhandene Ansätze aus wie TITAN oder FastSS benötigen zum Lösen dieses Problems in der Regel sehr viel Hauptspeicher und können meist nur mit einer beschränkten Menge von Zeichenketten umgehen. Diese Masterarbeit stellt zunächst ausgewählte Methoden aus der Literatur vor und analysiert diese. Dabei wurden insbesondere Methoden ausgewählt, die auf die Levenshtein-Distanz als Abstandsfunktion spezialisiert sind. Anschließend wird eine neue Methode State-Set-Index vorgestellt, die die Probleme vorhandener Ansätze löst und mit einer großen Menge von Zeichenketten effizient umgehen kann. Der State-Set-Index basiert auf einen nicht deterministischen Automaten (NDA) und speichert ausschließlich existierende Zustände, Zustandsübergänge können abgeleitet werden. Die Datenhaltung der Zeichenketten erfolgt dabei in einem Key/Value-Store. Es wird gezeigt, dass diese Methode in vielen Fällen, sowohl bei der Indexierung als auch bei der Anfragebearbeitung, effizienter arbeitet als andere Techniken. So konnten Anfragen mit dem State-Set-Index teilweise zehnmal schneller beantwortet werden als mit TITAN.
  • Automatic Sampling of Web Services
    Mohammed AbuJarour and Sebastian Oergel

    With the widespread of Service-oriented Computing (SOC) and the increasing number of available web services in several domains, service discovery has become one of the main challenges in SOC. Lack of rich service descriptions is one of the several factors that exacerbate this challenge. Therefore, additional information about web services is required. Several approaches and sources have been proposed in the community to gather this information, such as domain experts, service providers, service consumers, etc. However, the increasing number of web services requires automatic approaches and additional sources of information. In this paper, we introduce a novel approach to generate annotations for web services, e.g., tags, by sampling their automatic invocations. The generated annotations are integrated in web forms that are used for future calls of these web services. Providing correct values for input parameters of web services is one of the main challenges involved in this work. We use four sources to assign values for input parameters, namely, random values, outputs of other operations within the same web service, other web services, and external data sources, e.g., DBpedia, WordNet. We have implemented our approach in the context of our service registry and validated it through several experiments.