Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Big data: sublinear algorithms for distributed data streams
Ort / Verlag
Paderborn
Erscheinungsjahr
2019
Verknüpfte Titel
Beschreibungen/Notizen
Tag der Verteidigung: 15.02.2019
ger: 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.
eng: 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.