Go to page
 

Bibliographic Metadata

Title
Big data: sublinear algorithms for distributed data streams / Manuel Malatyali ; [Reviewer: Prof. Dr. Friedhelm Meyer auf der Heide, University of Paderborn, Prof. Dr. Christian Scheideler, University of Paderborn]
AuthorMalatyali, Manuel
ParticipantsMeyer auf der Heide, Friedhelm ; Scheideler, Christian
PublishedPaderborn, 2019
Edition
Elektronische Ressource
Description1 Online-Ressource (VII, 130 Seiten)
Institutional NoteUniversität Paderborn, Dissertation, 2019
Annotation
Tag der Verteidigung: 15.02.2019
Defended on2019-02-15
LanguageGerman
Document TypesDissertation (PhD)
URNurn:nbn:de:hbz:466:2-35244 
DOI10.17619/UNIPB/1-766 
Files
Big data: sublinear algorithms for distributed data streams [0.83 mb]
Links
Reference
Classification
Abstract (German)

Wir betrachten ein Sensornetzwerk aus zahlreichen Knoten, die die Umgebung beobachten und in der Lage sind, diese Informationen an einen Server zu übermitteln. Der Server evaluiert eine Funktion (z.B.\ Maximum, etc.) basierend auf den Informationen, die aktuell bei den Sensorknoten vorliegen.Zu diesem Zweck können die Sensorknoten und der Server Nachrichten schicken. Die Sensorknoten können an den Server, der Server wiederum eine Nachrichten direkt an einen Sensorknoten oder an alle Sensorknoten senden. Dabei haben alle oben genannten Nachrichten einheitliche Kosten. Das Ziel ist es, die gesamte Kommunikation zu minimieren, während der Server die gegebene Funktion berechnet. In diesem Setting wenden wir zwei verschiedene Techniken an: Zunächst betrachten wir filterbasierte Protokolle und vergleichen Protokolle mit einem optimalen Offline-Algorithmus, der die Eingabe im Voraus kennt und die Filter optimal bestimmt. Zweitens entwerfen und analysieren wir Protokolle im Rahmen von dynamischen Algorithmen. Das bedeutet, zwischen zwei Zeitpunkten an denen eine Ausgabe berechnet wird, ändert sich nur für ein Bruchteil der Sensorknoten die beobachte Information. Es werden Kommunikationsprotokolle entwickelt mit einem Kommunikationsaufwand abhängig von der Anzahl der geänderten Sensoren.

Abstract (English)

We consider a sensor network comprised of numerous nodes which sense the environment and are equipped with communication capabilities to convey this information to a server. The server evaluates a function (e.g., Maximum, etc.) based on the information at the sensor nodes currently observed. To fulfill this task, the sensor nodes can send their observations to the server, and in turn, the server can send messages directly to a sensor node or broadcast a message to all sensor nodes with unit costs. The objective is to minimize the total communication while the server computes the function. We apply two different techniques to tackle this situation:First, we consider filter-based protocols and compare protocols against an optimal offline algorithm which knows the whole input in advance and sets filters in an optimal way. Second, we design and analyze protocols in the framework of dynamic algorithms. That is, given observations at a specific time step, we assume that only a fraction of the sensorsidentify a change in their observation in comparison to the previous time step. We aim at communication protocols which use communication depending on this fraction.

License
CC-BY-License (4.0)Creative Commons Attribution 4.0 International License