[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.

 

Termine

Datum Beginn Raum Vortragende(r) Titel
05.03.2014 11:00 Uhr c.t. RUD 25, 3.113 Steffen Zeuch "Adapting Tree Structures for Processing with SIMD Instructions"
12.02.2014 12:00 Uhr s.t. RUD 25, 3.113 Robert Przewozny "Erweiterung von Datenflussprogrammen um Operatoren zur Statistiksammlung"
12.02.2014 11:00 Uhr c.t. RUD 25, 3.113 Tino Schernickau "Distributed Statistics-Store"
05.02.2014 11:00 Uhr c.t. RUD 25, 3.113 Steffen Andre "Anfrageausführung im Semantic Web of Linked Data unter Berücksichtung des Robots Exclusion Protocols"
04.12.2013 11:00 Uhr c.t. RUD 25, 3.113 Jochen Taeschner "Evaluation des Algorithmus FtEDPP2GA"
27.11.2013 11:00 Uhr c.t. RUD 25, 3.113 Zheng Wang "Adaptive Memory Assignment for Concurrently Running Tasks"
20.11.2013 11:00 Uhr c.t. RUD 25, 3.113 Matthias J. Sax "Constraint-based Performance Optimization for Distributed Stream Processing"

Zusammenfassungen

"Adapting Tree Structures for Processing with SIMD Instructions" (Steffen Zeuch)

In this paper, we accelerate the processing of tree-based in- dex structures by using SIMD instructions. We adapt the B+-Tree and pre x B-Tree (trie) by changing the search al- gorithm on inner nodes from binary search to k-ary search. The k-ary search enables the use of SIMD instructions, which are commonly available on most modern processors today. The main challenge for using SIMD instructions on CPUs is their inherent requirement for consecutive memory loads. The data for one SIMD load instruction must be located in consecutive memory locations and cannot be scattered over the entire memory. The original layout of tree-based index structures does not satisfy this constraint and must be adapted to enable SIMD usage. Thus, we introduce two tree adaptations that satisfy the speci c constraints of SIMD instructions. We present two di erent algorithms for trans- forming the original tree layout into a SIMD-friendly layout. Additionally, we introduce two SIMD-friendly search algo- rithms designed for the new layout. Our adapted B+-Tree speeds up search processes by a fac- tor of up to eight for small data types compared to the origi- nal B+-Tree using binary search. Furthermore, our adapted pre x B-Tree enables a high search performance even for larger data types. We report a constant 14 fold speedup and an 8 fold reduction in memory consumption compared to the original B+-Tree.

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

Das Ziel dieser Diplomarbeit im Forschungsprojekt Stratosphere ist die Entwicklung einer anfragebasierten Statistiksammlung. Sopremo, das algebraische Operatormodell von Stratosphere, unterstützt den Einsatz von benutzerdefinierten Operatoren mit unbekannter Semantik. Die Kostenschätzung eines Sopremo-Plans erfordert daher das Sammeln von Statistiken über den Zwischenergebnissen von ausgewählten Teilplänen. Bei der Optimierung eines Plans wird eine Vielzahl von Statistiken angefragt, deren vollständige Berechnung in der Regel unverhältnismäßig ist. Ein Schwerpunkt dieser Arbeit ist die Bewertung und Auswahl der zu sammelnden Statistiken basierend auf früheren Anfragen an den Statistikspeicher. Die Berechnung der ausgewählten Statistiken wird durch eine Erweiterung des auszuführenden Plans realisiert. Eine Herausforderung hierbei ist die Begrenzung des durch die hinzugefügten Operatoren entstehenden Mehraufwandes. In diesem Vortrag sollen die Ergebnisse der Arbeit vorgestellt und diskutiert werden.

"Distributed Statistics-Store" (Tino Schernickau)

Das sich in der Entwicklung befindliche Statistikframework wird Ausführungspläne in Stratosphere anhand von Statistiken zur Laufzeit reoptimieren. Ziel der Diplomarbeit mit dem Titel ?Ein adaptiver Index für verteilte, strukturierte Laufzeitstatistiken? ist der Entwurf eines Speichersystems für Statistiken. Trotz der verteilten Speicherung ermöglicht das System einen zentralen Zugriff auf die Statistiken, deren Speicherort anhand einer Indexstruktur verwaltet wird. In der Arbeit wird das Modell einer in konfigurierbarer Weise komprimierten Indexstruktur entworfen, wozu insbesondere Methoden aus dem Bereich des Information Retrieval auf ihre Anwendbarkeit untersucht werden.

"Anfrageausführung im Semantic Web of Linked Data unter Berücksichtung des Robots Exclusion Protocols" (Steffen Andre)

Der Vortrag stellt das Thema der Diplomarbeit vor. Die darin verwendete verweisbasierte Anfrageausführung, die Suchanfragen im Semantic Web of Linked Data bearbeitet, wird dabei an Serverbenutzungsrestriktionen gebunden. Das von Crawlern (Agenten zum Indexieren von Internetseiten) benutzte Robots Exclusion Protocol (REP) wird zu diesem Zweck für die verweisbasierte Anfrageausführung nutzbar gemacht. Eine serverfreundliche Anfrageausführung entsteht. Ein Problem der verweisbasierten Anfrageausführung sind hohe Lastspitzen, die auf einzelnen Servern während einer Anfrageausführung auftreten können. Ziel ist es, Abfragen, die benötigt werden, gleichmäßiger zu verteilen und Lastspitzen zu vermeiden. In der Diplomarbeit wurde ein Ansatz erarbeitet, der diese Anforderung erfüllt.

"Evaluation des Algorithmus FtEDPP2GA" (Jochen Taeschner)

Um Datenbanken mit personenbezogenen Daten weitergeben oder veröffentlichen zu dürfen, müssen diese anonymisiert werden. Man bedient sich hier unter anderem der Konzepte der k-Anonymität und der t-Closeness. In Nielsens Diplomarbeit "Verteilte Anonymisierung von vertikal partitionierten Daten" wurde der Fragmenting t-Closeness Enhanced Distributed Privacy-Preserving two-Party Generic Anonymizer (FtEDPP2GA) vorgestellt, der dies im verteilten Fall für die t-Closeness erreicht. Dieser Algorithmus wurde im Rahmen einer Studienarbeit implementiert und evaluiert. Dabei standen vor allem die übertragenen Datenmengen und die Auswirkungen der Verteiltheit auf die Anonymisierung im Mittelpunkt der Untersuchungen. Durch eine umfangreiche Simulationen konnte für viele Testfälle ein Vergleich zur unverteilten t-Closeness und zur verteilten k-Anonymität gezogen werden. Die Ergebnisse sollen in diesem Vortrag vorgestellt werden.

"Adaptive Memory Assignment for Concurrently Running Tasks" (Zheng Wang)

In this talk a memory tuning method is shown that adjusts the memory assignment between join operators to improve Stratospheres execution efficiency. To tackle this problem without interfering the execution of join operators an asynchronuous memory tuning algorithm is used. This algorithm uses the memory manager as a broker to guide the memory tuning progress and avoid interferences caused by contacts between join operators. To measure the memory utilization of each join and decide which join operator should get more memory or lose some a metric called Return on Consumption (ROC) is applied. To cope with memory tuning at runtime all join operators must be memory adaptive. By applying asynchronuous memory tuning with memory adaptive join operators we provide a mechanism to increase the memory utilization for joins.

"Constraint-based Performance Optimization for Distributed Stream Processing" (Matthias J. Sax)

Distributed stream processing got more attention in research and industry in the last years. Current work is inspired by the MapReduce idea and applies it to data stream processing. Last year we developed Aeolus, an optimization layer on top of the distributed intra-node-parallel streaming system Storm. Aeolus provides a transparent batching layer that can improve Storm's throughput by an order of magnitude. 'Transparent' means, that neither the Storm system nor the user written data flow programs must be adopted to use Aeolus' batching layer. Furthermore, Aeolus provides an optimizer that computes an optimum degree-of-parallelism for each node in a given data flow program. The optimizer also exploits the batching layer and computes an optimum batch size for each node in a data flow.

While Aeolus' objective is to maximize the throughput, the latency for individual tuples increases because of batching tuple. However, low latency processing is a core feature for stream processing. In our current work, we constrain the throughput-optimization by a latency goal, i.e., each input tuple must be completely processed within this specified latency boundary. Hence, the optimizer must compute the parallelism and batch sizes accordingly. We developed an latency model for Aeolus' batching approach that enables the optimizer to compute the expected latency for a given data flow configuration. Right now we integrate this model into the current optimization algorithm. The goal is to extend the optimizer s.t. the optimized data flow program meets the latency constraint.

In this talk I will give a short overview about Aeolus' cost model, batching layer, and basic optimization approach. Additionally, I will explain the developed latency model and show some experimental verification results for the model. If time permits, a demo of Aeolus will be shown.



[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

[Punkt]  Wintersemester 2014/15

[Punkt]  Sommersemester 2014

[aktiver 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