Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Wissensmanagement in der Bioinformatik

Neue Entwicklungen im Datenbankbereich und in der Bioinformatik

• wann? Dienstag, 11-13 c.t.
• wo? RUD 25, 4.112

Dieses Seminar wird von den Mitgliedern der beiden Arbeitsgruppen als Forum der Diskussion und des Austauschs genutzt. Studenten und Gäste sind herzlich eingeladen.

Folgende Termine und Vorträge sind bisher vorgesehen:

Zusammenfassungen

Prefix Tree Indexing for Similarity Search and Similarity Join on Genomic Data - Probevortrag SSDBM (Astrid Rheinländer)

Similarity search and similarity join on strings are important for applications such as duplicate detection, error detection, data cleans- ing, or comparison of biological sequences. Especially DNA sequencing produces large collections of erreneous strings which need to be searched, compared, and merged. However, current RDBMS offer similarity oper- ations only in a very limited and inefficient form that does not scale to the amount of data produced in Life Science projects. We present PETER, a prefix tree based indexing algorithm supporting approximate search and approximate joins. Our tool supports Hamming and edit distance as similarity measure and is available as C++ library, as Unix command line tool, and as cartridge for a commercial database. It combines an efficient implementation of compressed prefix trees with advanced pre-filtering techniques that exclude many candidate strings early. The achieved speed-ups are dramatic, especially for DNA with its small alphabet. We evaluate our tool on several collections of long strings containing up to 5,000,000 entries of length up to 3,500. We compare its performance to agrep, nrgrep, and user-defined functions inside a relational database. Our experiments reveal that PETER is faster by orders of magnitude compared to the command-line tools. Compared to RDBMS, it computes similarity joins in minutes for which UDFs did not finish within a day and outperforms the built-in join methods even in the exact case.

Erkennung naher Duplikate von Nachrichten im Web (Cristian Müller)

Das Wissen um Duplikate eröffnet Vorteile beim verarbeiten und speichern von großen Mengen aus Datenobjekten. Dies trifft ebenfalls zu, wenn es sich bei besagten Datenobjekten um Fließtext handelt. In diesem speziellen Fall sind weitere Anwendungsmöglichkeiten denkbar z.B. das Auffinden von Texten mit ähnlichen Themen oder das Auffinden von Plagiaten.  Diese Anwendungsmöglichkeiten basieren auf der Fähigkeit außer echten Duplikaten auch nahe Duplikate zu erkennen. Also Duplikate, die sich nicht signifikant unterscheiden, aber keine Kopien voneinander sind. Ein beliebtes Mittel, um solche "nähe" zu bewerten, ist die Verwendung eines Ähnlichkeitsmaßes. Ein Ähnlichkeitsmaß bildet ein Paar von Objekten auf einen numerischen Wert ab. Liegt dieser Wert oberhalb eines Schwellwertes werden die beiden Objekte als Duplikate betrachtet. In der Studienarbeit wurde untersucht in wie weit sich ein Ähnlichkeitsmaß eignet, um nahe Duplikate in Nachrichten zu finden. Diese Nachrichten entsprangen  HTML-Seiten. Zusätzlich zu dem Kernproblem des Auffindens von Duplikaten  ergab sich das Problem die Nachrichten aus den HTML-Seiten zu extrahieren. Dieser Vortrag stellt die verwendeten Mittel, Vorgehensweisen und Ergebnisse vor.

Effiziente Anfragebearbeitung in Peer-Daten-Management-Systemen (Armin Roth)

Peer-Daten-Management-Systeme (PDMS) bestehen aus einer dynamischen Menge von Peers, die Anfragen sowohl unter Zugriff auf lokale Daten als auch durch Weiterreichen an benachbarte Peers beantworten. PDMS sind aufgrund ihrer dezentralen Natur hochflexibel, leiden aber aufgrund der massiven Redundanz in den beschrittenen Weiterreichungspfaden bei zunehmender Anzahl von Peers unter erheblichen Effizienzproblemen. Darüber hinaus führen die zum Weiterreichen notwendigen Anfragetrans- formationen oftmals zu einem unerwünschten Informationsverlust.
Die Dissertation basiert auf der Idee, die Vollständigkeit von Anfrage-ergebnissen als Optimierungsziel zu betrachten. Peers können dazu solche Pfade von der weiteren Anfragebearbeitung ausschliessen, von denen sie ein ungünstiges Verhältnis von Ergebnisgröße zu Kosten erwarten. Die Erwartungen basieren auf Schätzungen derErgebniskar-dinalität, die über selbstadaptive Histogramme implementiert werden. Die Aktualisierung dieser Histogramme basiert aber wiederum auf ausgeführten Weiterreichungen, was zu einem weiteren Zielkonflikt zwischen Schätzgenauigkeit und Zeitaufwand führt.
In der Arbeit werden verschiedene Verfahren entwickelt und evaluiert, die einen geeigneten Kompromiss zwischen Nutzen und Kosten der indivi-duellen Weiterreichungen suchen. In einer lokalen Optimierungsstrategie limitieren wir das insgesamt für die Anfragebearbeitung verwendete Zeit-Budget. In einem zweiten Optimierungsansatz nutzen wir mehrdimen-sionale Histogramme über die Überlappung zweier Datenquellen zur gezielten Verminderung der Redundanz in der Anfragebearbeitung. Experimente mit einem neu entwickelten PDMS, dem System P, zeigen Effizienzgewinne von einer Größenordnung und mehr.

Semantic Integration of Natural Person Schemata in the European Union (Martin Herzog)

In the European Union, the schemata used to describe a natural person are very different. Each member state is free to apply its own model to various administrative applications. As a result there is a lack of semantic interoperability between countries when personal data needs to be exchanged across national boundaries. The purpose of this work is to find a way to establish semantic interoperability among the different data about natural persons. To this end, the national personal schemata are mapped to a specific global schema. On this basis, a semi-automatic process for the semantic integration of personal schemata is developed. It is based on automatic schema matching on one hand and the manual modification of schema mappings on the other hand. The talk gives insights into the proposed process and shows the experimental results of a use case with four personal schemata.

Selecting Materialized Views for RDF Data (Roger Castillo)

In the design of a relational database, the administrator has to decide, given a fixed or estimated workload, which indexes should be created. This so called index selection problem is an non-trivial optimization problem in relational databases. We describe a novel approach for index selection on RDF data sets. We propose an algorithm to automatically suggest a set of indexes as materialized views based on a workload of SPARQL queries. The selected set of indexes aims to decrease the cost of the workload. We also provide a cost model to estimate the potential impact of candidate indexes on query performance and an algorithm to select an optimal set of indexes. This algorithm may be integrated into an existing SPARQL query engine.

TBA (Johannes Starlinger)

TBA