[dbis logo]

.Lehre.Semesterübersicht
[Institut fuer Informatik] [Leerraum] [Humboldt-Universitaet zu Berlin]

Forschungsseminar: Neue Entwicklungen im Datenbankbereich

Dieses Seminar wird von Mitgliedern der Lehr- und Forschungseinheit als Forum der Diskussion und des Austauschs genutzt. Studierende und Gäste sind herzlich eingeladen.

 

Das Seminar findet Mittwochs von 13-15 Uhr in RUD 25, Raum 4.113 statt. Wer per Email Einladungen zum Forschungsseminar erhalten möchte, sendet bitte eine Email an Thomas Morgenstern um sich in die Mailingliste ein- bzw. austragen zu lassen.

Termine

Datum Beginn Raum Vortragende(r) Titel
15.04.2015 11 Uhr c.t. ESZ 1'307 Fabian Schulz "Konzept und Implementation eines Experimentiersystems für Event Pattern Matching Algorithmen"
01.04.2015 11 Uhr c.t. ESZ 1'307 Taras Iks "Konzept und Implementierung eines QTM-DLB auf Basis von PostgreSQL"
18.03.2015 11 Uhr c.t. ESZ 1'307 Michael Prietzel "Analyse des Event Pattern Matching Algorithmus des Complex Event Processing Systems Esper"
25.02.2015 12 Uhr s.t. ESZ 1'307 Daniel Janusz "D2Pt: Privacy-Aware Multiparty Data Publication"
25.02.2015 11 Uhr c.t. ESZ 1'307 Mihail Vieru "Graph Distance and Textual Similarity Joins on Big Data using Apache Flink"
19.02.2015 11 Uhr c.t. Rud 25 3.113 Daniel Janusz "D2Pt: Privacy-Aware Multiparty Data Publication"
10.02.2015 11 Uhr c.t. Humboldt Kabinett Prof. Nikolaus Augsten, PhD "On-the-fly token similarity joins in relational databases"
04.02.2015 11 Uhr c.t. ESZ 1'307 Dennis Schneider "Kostenschätzung in verteilten Datenverarbeitungssystemen"
14.01.2015 11 Uhr c.t. ESZ 1'307 Dimitar Dimitrov "Implementierung von Algorithmen zur Datenanonymisierung in DB2"
07.01.2015 11 Uhr c.t. ESZ 1'307 Mihail Vieru "Design and Implementation of a Bloom Filter Semi-Join in Stratosphere"
26.11.2014 11 Uhr c.t. ESZ 1'307 Zheng Wang "Main Memory Tuning of Stratosphere"
19.11.2014 11 Uhr c.t. ESZ 1'307 Tino Schernickau "Ein adaptiver Index für verteilte, strukturierte Laufzeitstatistiken"
12.11.2014 11 Uhr c.t. ESZ 1'307 Robert Przewozny "Erweiterung von Datenflussprogrammen um Operatoren zur Statistiksammlung"
29.10.2014 11 Uhr c.t. ESZ 1'307 Florian Hönicke "Optimizing Set-Similarity Joins on MapReduce "

Zusammenfassungen

Konzept und Implementation eines Experimentiersystems für Event Pattern Matching Algorithmen (Fabian Schultz)

Beim Event Pattern Matching (EPM) wird ein zeitlich geordneter Eingabestrom von Ereignissen (Event) mit einem Muster (Pattern) verglichen. Die Ausgabe ist eine Menge von Treffern (Matches) für das Muster im Eingabestrom. Anwendung findet EPM in vielen Bereichen, wie zum Beispiel in der RFID-Lagerverwaltung, bei der Clickstream-Analyse, in Gesundheitsinformationssystemen und im Finanzsektor. Verschiedene Algorithmen wurden bereits vorgeschlagen, um das EPM-Problem zu lösen. Allerdings gibt es aktuell keine einheitliche Methode, um die Stärken und Schwächen von EPM-Algorithmen zu untersuchen und um EPM-Algorithmen objektiv zu vergleichen. Ziel dieser Studienarbeit ist ein Experimentiersystem für EPM-Algorithmen zu konzipieren und zu implementieren. Damit sollen sowohl Stärken und Schwächen einzelner Algorithmen untersucht als auch Algorithmen miteinander verglichen werden können.

Konzept und Implementierung eines QTM-DLB auf Basis von PostgreSQL(Taras Iks)

In den letzten Jahrzehnten veröffentlichte Untersuchungen zeigen, dass Datenbanksysteme die Vorteile der heutigen Prozessor-Architekturen nicht ausschöpfen. Es werden unterschiedliche Ansätze vorgeschlagen, um eine bessere Ausnutzung der Cache-Hierarchien zu bewirken. Diese Arbeit geht auf zwei Techniken ein, indem die Blockgröße der verarbeiteten Daten sowie Scheduling-Strategien näher untersucht werden. Die Blockgröße beschreibt die Anzahl der Tupel, welche von Operatoren verarbeitet werden, die Scheduling-Strategie steuert hingegen die Reihenfolge der Verarbeitung von Operatoren. Das Query Task Model (QTM) wird eingeführt und dient zur Modellierung der parallelen Abarbeitung von Abfragen, sodass der Ausführungsplan als eine Menge von Tasks modelliert wird. Der Query Task Model-Dynamic Load Balancer (QTM-DLB) stellt dessen Laufzeitimplementierung dar. Hiermit eröffnet sich die Möglichkeit zum Einsatz der Intra- Operator-Parallelisierung auf unterschiedlichen Datensätzen sowie der Inter-Operator- Parallelisierung als eine Erweiterung in PostgreSQL. Die Leistung des Systems in der Verarbeitung der Datenbankabfragen wird anhand TPC-H Benchmarks ausgewertet, um auf den Effekt des gewählten Ansatzes zu schließen.

Analyse des Event Pattern Matching Algorithmus des Complex Event Processing Systems Esper (Michael Prietzel)

Event Pattern Matching (EPM) vergleicht ein vordefiniertes Muster (Pattern) mit Ereignissen (Events) aus einem Datenstrom (Event Stream) und gibt bei Übereinstimmung eine Menge an Treffern (Matches) zurück. Anwendungsgebiete des EPM sind unter anderen der Finanzsektor, Netzwerküberwachung, und eingebettete Systeme. Das Complex Event Processing (CEP) System Esper ist ein quelloffenes System, das EPM implementiert und in Forschung und Praxis weit verbreitet ist. Bis jetzt wurde der EPM-Algorithmus von Esper noch nie im Detail untersucht. Ziel meiner Bachelorarbeit ist den EPM-Algorithmus von Esper aus dem Open-Source-System zu extrahieren und den Algorithmus experimentell und theoretisch zu untersuchen. In diesem Vortrag stelle ich das Exposé dieser Bachelorarbeit vor.

"Graph Distance and Textual Similarity Joins on Big Data using Apache Flink" (Mihail Vieru)

A common operation for big data analysis platforms such as Apache Flink is the joining of data sets with both graph and textual dimensions. Graph data may be a representation of a social network like Facebook or of a collection of linked documents like the World Wide Web. In the latter case, the text contained in a web site can be represented as a set of words. The web sites are interconnected through hyperlinks that represent the graph edges. A frequent operation on this data is finding all vertex pairs containing similar textual information in the graph, e.g. users with similar interests or web sites with similar content. A usual condition posed is that the vertices must be within a specified distance from each other, i.e., the number of connecting edges must not exceed a specified threshold value. In this thesis we will design, implement and evaluate joins that combine both textual similarity and graph distance at the same time using Apache Flink. We focus our work on the efficient combination of parallel and distributed approaches for the all-pairs-shortest-path and set similarity join problems.

"D2Pt: Privacy-Aware Multiparty Data Publication" (Daniel Janusz)

Today, publication of medical data faces high legal barriers. On the one hand, publishing medical data is important for medical research. On the other hand, it is neccessary to protect peoples’ privacy by ensuring that the relationship between individuals and their related medical data remains unknown to third parties. Various data anonymization techniques remove as little identifying information as possible to maintain a high data utility while satisfying the strict demands of privacy laws. Current research in this area proposes a multitude of concepts for data anonymization. The concept of k-anonymity allows data publication by hiding identifying information without losing its semantics. Based on k-anonymity, the concept of t-closeness incorporates semantic relationships between personal data values, therefore increasing the strength of the anonymization. However, these concepts are restricted to a centralized data source. In this paper, we extend existing data privacy mechanisms to enable joint data publication among multiple participating institutions. In particular, we adapt the concept of t-closeness for distributed data anonymization. We introduce Distributed two-Party t-closeness (D2Pt), a protocol that utilizes cryptographic algorithms to avoid a central component when anonymizing data adhering the t-closeness property. That is, without a trusted third party, we achieve a data privacy based on the notion of t-closeness.

"On-the-fly token similarity joins in relational databases" (Prof. Nikolaus Augsten, PhD)

This talk will discuss the integration of token similarity joins into relational database systems. Token similarity joins represent data items as sets of tokens, for example, strings are represented as sets of q-grams. Two items are considered similar and match if their token sets have a large overlap. In previous work, the tokens are assumed to preexist in the database, and the token generation cannot be expressed as part of the query. Our goal is to efficiently compute token similarity joins on-the-fly, i.e., without any precomputed tokens or indexes. We define "tokenize", a new relational operator that generates tokens and allows the similarity join to be fully integrated into relational databases. This allows us to (1) optimize the token generation as part of the query plan, (2) provide the query optimizer with cardinality estimates for tokens, (3) choose efficient algorithms based on the query context. We implemented the new operator in the kernel of PostgreSQL and empirically evaluated its performance for similarity joins. Algebraic properties, cardinality estimates, and an efficient iterator algorithm for tokenize will be discussed.

Nikolaus Augsten is a full professor in computer science at the University of Salzburg, where he heads the Database Group. He received his PhD from Aalborg University, Denmark, in 2008. Prior to joining the University of Salzburg in 2013, he was an assistant professor at the Free University of Bozen-Bolzano, Italy. His main research interests include data-centric applications in database and information systems with a particular focus on similarity queries, efficient indexing techniques, and load balancing problems. The results of his research were published in the most prestigious outlets in the database area; for his work on top-k queries over tree data he received the ICDE 2010 Best Paper Award. Currently, he serves as an associate editor for the VLDB Journal.

"Kostenschätzung in verteilten Datenverarbeitungssystemen" (Dennis Schneider)

Verteilte Datenverarbeitungssysteme (VDVS) wie Hadoop oder Apache Flink werden immer häufiger eingesetzt, um große Datenmengen einfach und hochparallel zu verarbeiten. Zur effizienten Verarbeitung werden Anfragen an solche Systeme vor der Ausführung optimiert. Bei der Optimierung treten für VDVS spezifische Herausforderungen auf. So wird z.B. nicht garantiert, dass über die zu verarbeitenden Daten bei der Optimierung Informationen vorliegen. Dies erschwert die Anfrageoptimierung. In der vorgestellten Diplomarbeit wird der Rahmen eines Kostenschätzers für VDVS entworfen, der plattformübergreifend eingesetzt werden kann. Er operiert auf algebraischen Anfrageplänen und berücksichtigt einige Besonderheiten von VDVS. Die geschätzten Kosten eines Anfrageplans werden mit einer Güte versehen, die angibt, wie zuversichtlich der Kostenschätzer ist, dass der angegebene Wert zutrifft. Ein Optimierer kann anhand der so geschätzten Kosten aus verschiedenen Plänen anhand verschiedener Kriterien den besten Plan auswählen. Dabei lassen sich anhand der Güte Pläne mit nur groben Kostenschätzungen von solchen mit sehr präzisen Kostenschätzungen unterscheiden. Der Kostenschätzer wurde exemplarisch in Stratosphere umgesetzt und evaluiert.

"Implementierung von Algorithmen zur Datenanonymisierung in DB2" (Dimitar Dimitrov)

Für eine Anonymisierung von Mikrodaten ist die De-Identifikation, d.h. das Entfernen direkt identifizierender Merkmale, nicht ausreichend. Deshalb wurden Algorithmen entwickelt, die Konzepte wie k-Anonymity, l-Diversity oder t-Closeness implementieren. Nur wenige Toolkits für Datenanonymisierung sind frei verfügbar. Existierende Implementationen, wie das Cornell Anonymization Toolkit oder die UTD Anonymization ToolBox benutzen Datenbanken höchstens als Daten-Speicher. Das Ziel dieser Bachelorarbeit ist die Implementation von Algorithmen zur Datenanonymisierung als Routinen in einer Datenbank. Routinen in DBMS ermöglichen die Ausführung von komplexer Logik auf Daten. Routinen sind eng mit der Datenbank verknüpft, was eine effiziente Ausführung erlaubt. Zunächst soll ein Algorithmus zur k-Anonymisierung, der Datafly-Algorithmus, als externe Routine und als SQL Routine implementiert werden und die Laufzeit der zwei Implementationen verglichen werden. Anhand der Ergebnisse sollen weitere Algorithmen als externe oder SQL Routinen implementiert werden. Die Bachelorarbeit soll weiterhin eine Aussage darüber treffen, was für eine Auswirkung die Implementation der Algorithmen als Routinen auf deren Performance hat. Dabei soll bewertet werden, inwiefern und welche Art von Routinen für die Implementation der Algorithmen geeignet sind.

"Design and Implementation of a Bloom-Filter-Semi-Join in Stratosphere" (Mihail Vieru)

In big data analysis systems such as Stratosphere, network traffic is one of the main cost drivers for query processing due to the system's distributed architecture. The network traffic for transferring a data set depends on the cardinality, i.e. number of records, and on the record sizes of the respective data set. The generated network traffic for a specific operator in the PACT data flow of Stratosphere depends on the output cardinality of the previous operator in the graph. For both input data sets in a join, the output cardinality can be minimized by inserting a semi-join operator as a pre-processing step before the actual join operator in the graph. We have designed and implemented a Bloom-Filter-Semi-Join (BFSJ) operator for Stratosphere in this thesis. Like a Bloom filter, the BFSJ output may contain false positives, but false negatives are guaranteed not to occur. We have experimentally evaluated the BFSJ operator and have shown significant reductions in network traffic for low selectivity join queries.

"Main Memory Tuning of Stratosphere" (Zheng Wang)

This study aims to introduce the memory self tuning to Stratosphere to improve its performance by optimizing the efficiency of the memory usage. Memory self tuning adjusts the memory assignment between database operators without interrupting the their execution. We observe the performance of each database operator at the runtime. Based on the observation we evaluate the performance of them by Return on Consumption model, which is a time - memory allocation metrics for measuring the memory utilization of operators. We shift memory from the operators with low efficiency to the operators with high efficiency. We introduce an asynchronous tuning algorithm to avoid the time cost of synchronizations between operators for memory adjustment by using the memory manager as a broker. To cope with the memory self tuning, we rebuild all database operators to memory adaptive operators, which can adapt and optimize their algorithm to the changing memory allocation.

"Ein adaptiver Index für verteilte, strukturierte Laufzeitstatistiken" (Tino Schernickau)

Inhalt dieser Diplomarbeit ist die Entwicklung eines Konzepts zum effizienten Zugriff auf Statistiken, die zur Anfrageausführungsplanoptimierung in Stratosphere erzeugt werden. Die im Zuge der Arbeit entwickelte Softwarekomponente stellt ein Statistikdepot dar, dass zur Laufzeit erzeugte Statistiken verwaltet und verteilt speichert. Zusätzlich ermöglicht es einen zentralen Zugriff auf die Statistiken mithilfe einer Indexstruktur. Neben einem effizienten Zugriff stellt ein geringer Ressourchenverbrauch die zentrale Anforderung an die entworfene Indexstruktur dar. Da kein dedizierter Rechenknoten verwendet werden sollte, wurde, um den Speicherplatzverbrauch der Indexstruktur an den zur Verfügung stehenden Hauptspeicherplatz und die zu speichernde Datenmenge anzupassen, eine Datenkompressionsmethode angewandt, die eine Steigerung der Stärke der Kompression zur Laufzeit ermöglicht.

"Erweiterung von Datenflussprogrammen um Operatoren zur Statistiksammlung" (Robert Przewozny)

Viele Systeme zur verteilten Datenanalyse wie Asterix, Scope oder Stratosphere definieren Sprachen zur Formulierung von deklarativen Anfragen. Um die Ausführungsdauer dieser Anfragen zu verringern, kann auf Techniken der kostenbasierten Optimierung zurückgegriffen werden, die seit Jahrzehnten in relationalen Datenbanksystemen zum Einsatz kommen. Im Kontext der verteilten Datenanalyse sind die für die Optimierung erforderlichen Statistiken über den Eingabedaten jedoch häufig nicht verfügbar und können erst während der Anfrageausführung effizient generiert werden. Das Ziel dieser Diplomarbeit im Forschungsprojekt Stratosphere ist die Entwicklung einer integrierten Statistiksammlung, um eine kostenbasierte Optimierung von Anfragen zu ermöglichen. Zu diesem Zweck wurde ein Statistik-Injektor entworfen und implementiert, welcher einen gegebenen Plan des algebraischen Operatormodells Sopremo um Operatoren zur Berechnung von Statistiken erweitert. Ein Schwerpunkt der Arbeit ist die Auswahl einer geeigneten Menge von Statistiken, die durch eine Erweiterung des auszuführenden Plans berechnet werden sollen, sowie die Begrenzung des hierbei entstehenden Mehraufwandes. Der vorgestellte Ansatz zur Auswahl von Statistiken basiert auf Metriken, welche die geschätzten Kosten der Statistiksammlung sowie den Nutzen für die Optimierung zukünftiger Anfragen beschreiben. Anhand von Experimenten konnte eine Optimierung von Anfragen basierend auf den vom Injektor gewählten Statistiken gezeigt werden. Der Mehraufwand für die Erhebung der Statistiken wurde durch die aufgrund der Optimierung der nachfolgenden Anfragen eingesparte Laufzeit amortisiert.

"Optimizing Set-Similarity Joins on MapReduce" (Florian Hönicke)

The state of the art algorithms V-SMART-Join, Vernica-Join, and Mass-Join are MapReduce-based, distributed, parallel algorithms for determining set similarities in parallel. The sets can be text documents, where each word represents an element. Given a set of sets, the algorithms compute all pairs of sets which satisfy a specified set-similarity condition. The aim of this thesis is to show, that the algorithms do not fully exploit the characteristics of the input data set. More precisely, we develop a hybrid algorithm called PSI-Join (Partition and SuffIx filter) which combines the partition-based approach of the Mass-Join with the suffix filtering of the Vernica-Join. We demonstrate, that the runtime of the algorithms depends on the degree of parallelization (dop), while the optimal dop varies between different input sets. To address this problem, we incorporate a dop optimizer in the PSI-Join to estimate the optimal dop. A statistical test proves the statistical significance of our approach.



[Punkt]  Sommersemester 2019

[Punkt]  Wintersemester 2018/19

[Punkt]  Sommersemester 2018

[Punkt]  Wintersemester 2017/18

[Punkt]  Sommersemester 2017

[Punkt]  Sommersemester 2016

[Punkt]  Wintersemester 2015/16

[Punkt]  Sommersemester 2015

[aktiver Punkt]  Wintersemester 2014/15

[Punkt]  Sommersemester 2014

[Punkt]  Wintersemester 2013/14

[Punkt]  Sommersemester 2013

[Punkt]  Wintersemester 2012/13

[Punkt]  Sommersemester 2012

[Punkt]  Wintersemester 2011/12

[Punkt]  Sommersemester 2011

[Punkt]  Wintersemester 2010/11

[Punkt]  Sommersemester 2010

[Punkt]  Wintersemester 2009/10

[Punkt]  Sommersemester 2009

[Punkt]  Wintersemester 2008/09

[Punkt]  Sommersemester 2008

[Punkt]  Wintersemester 2007/08

[Punkt]  Sommersemester 2007

[Punkt]  Wintersemester 2006/07

[Punkt]  Sommersemester 2006

[Punkt]  Wintersemester 2005/06

[Punkt]  Sommersemester 2005

[Punkt]  Wintersemester 2004/05



Ansprechpartner

+49 30 2093-5466