Bitte wenden Sie sich für einen Termin per E-Mail an das Sekretariat von Prof. Sanders, blancani ∂does-not-exist.kit edu, und nennen Sie Ihren vollständigen Namen, Ihre Matrikelnummer sowie die Version der Prüfungsordnung, nach der Sie studieren.

The Lecture on Monday, January 25th will be given by Julian Shun from MIT:

Parallel Algorithms for Density-Based and Structural Clustering

Abstract: This talk presents new parallel algorithms for density-based
spatial clustering (DBSCAN) on point sets and structural clustering
(SCAN) on graphs, two problems that have received significant
attention due to their applicability in a variety of data analysis
tasks.

Existing parallel algorithms for DBSCAN require much more work than
their sequential counterparts, making them inefficient for large
datasets.  We bridge the gap between theory and practice of parallel
DBSCAN by presenting new parallel algorithms for Euclidean exact
DBSCAN and approximate DBSCAN that match the work bounds of their
sequential counterparts, and are highly parallel (polylogarithmic
depth).  For graphs, we present the first parallel index-based SCAN
algorithm, based a recent sequential algorithm, which enables users to
efficiently explore many different parameter settings for cluster
generation. Our parallel algorithm has a better work bound than the
sequential algorithm, and achieves logarithmic depth. We also apply
locality-sensitive hashing to design a novel approximate SCAN
algorithm and prove guarantees for its clustering quality.  We present
optimized implementations of our algorithms which achieve good
parallel scalability and outperform existing parallel implementations
by up to several orders of magnitude.

Bio: Julian Shun is the Douglas T. Ross Career Development Assistant
Professor of Software Technology in EECS and CSAIL at MIT.  Prior to
coming to MIT, he was a Miller Research Fellow at UC Berkeley.  He
received his Ph.D. from Carnegie Mellon University and his B.A. from
UC Berkeley.  His research focuses on the theory and practice of
parallel algorithms and programming frameworks.  He has received the
NSF CAREER Award, DOE Early Career Award, ACM Doctoral Dissertation
Award, CMU School of Computer Science Doctoral Dissertation Award,
Facebook Graduate Fellowship, Google Faculty Research Award, and best
paper awards at PLDI, SPAA, and DCC. 

General Information

English verison below

Deutsch:

Die Vorlesung findet im Wintersemester 2020/2021 online statt. Dazu werden die Vorlesungen vor-aufgezeichnet auf YouTube zur Verfügung gestellt. Der Vorlesungstermin wird für eine Videokonferenz über Zoom genutzt, die nach dem Flipped Classroom Konzept abläuft.

Die Vortragssprache ist in diesem Jahr ist Englisch. Deutsche Folien und eine deutsche Aufzeichnung aus vorherigen Jahren stehen aber weitgehend zur Verfügung. In der Videokonferenz können wir Deutsch und Englisch mischen. Insofern kann man die Vorlesung dieses Jahr als zweisprachig ansehen.

Der Zoom-Link zur Videokonferenz wird über Ilias bekannt gegeben. Zusätzlich findet ein verpflichtender Übungsbetrieb statt. Details werden in der Vorlesung und über Ilias bekannt gegeben.

English:

In the winter term 2020/2021 this lecture will be held online. Prerecorded lectures will be uploaded to YouTube. The stated lecture time will be used for a video conference using Zoom that will follow the flipped classroom concept.

Lectures will be held in English this year but German slides and a German recording from previous years are available. During the video conference German and English can be mixed so the lecture can be seen as bi-lingual this year.

The link for the video conference will be posted via Ilias. Additionally, there will be a mandatory exercise. Details will be announced in the lecture and via Ilias.

Additional Material

Connecting MapReduce Computations to Realistic Machine Models