Distributed graph processing and partitioning for spatiotemporal queries in the context of camera networks

Abstract

This work presents a scalable, distributed architecture for processing spatiotemporal queries in the context of camera networks based on a graph structure. With the ever-increasing presence of cameras and the emergence of camera-networks, e.g., in the context of campus security, it becomes increasingly important to provide a robust and scalable architecture to store and retrieve detected events. In this work a distributed graph processing engine will be presented which is well suited for read and write tasks in the environment of spatiotemporal image-similarity based workloads. The key ideas presented in this work are the architecture of a scalable graph processing system well-suited for processing spatio-temporal queries and the design of a distributed and robust vertex-partitioning strategy for the graph which is being defined by the spatiotemporal attributes of the stored events. The work will show multiple lightweight heuristics for partitioning the graph among the nodes participating in the system, focusing on load-balancing between workers and high edge-locality for vertices. The system and the partitioning strategies will be evaluated, showing that the system scales with the number of workers and the problem size and is able to answer proportionally more queries per second. It will also be shown that the lightweight heuristics for partitioning the graph produce a relatively good balancing of the vertices on the worker-nodes and can be executed in an online-fashion, resulting in similar performance when compared to a traditional hash-partitioning while providing far superior edge-locality.

Diese Arbeit stellt eine verteilte und skalierbare Architektur zur Verarbeitung von räumlich-zeitlichen Anfragen auf Kamera-Netzwerken vor und basiert dabei auf einer Graph-Struktur. Aufgrund der allgegenwärtigen Präsenz von Kameras und dem Aufkommen von Kamera-Netzwerken, zum Beispiel im Bereich der Überwachung eines Universitätsgeländes, wird es immer wichtiger, eine robuste und skalierbare Architektur zur Speicherung und Auffindung von detektierten Ereignissen anzubieten. In dieser Arbeit soll daher eine verteilte Graph-Verarbeitungs-Architektur vorgestellt werden, welche für die Verarbeitung von Einfüge- und Anfrage-Operationen im Umfeld von räumlich-zeitlichen Bild-Ähnlichkeits-basierten Aufgaben gut geeignet ist. Die Haupt-Ideen dieser Arbeit sind dabei die Architektur eines skalierbaren Graph-Verarbeitungs-Systems zur Ausführung der räumlich-zeitlichen Anfragen und der Entwurf verteilter und robuster Knoten-Partitionierungs-Schemas für den Graph der detektierten Ereignisse. Dafür werden mehrere, leichtgewichtigte Heuristiken zur Partitionierung des Graphen zwischen den am System teilnehmenden Rechner-Knoten vorgestellt, wobei der Fokus auf einer Lasten-Verteilung zwischen den Rechner-Knoten des Systems liegt, bei gleichzeitiger Optimierung der Kanten-Lokalität. Das dabei entstehende System und die Partitionierungsstrategien werden evaluiert, wobei die Skalierbarkeit des Systems sowohl in der Zahl der teilnehmenden Rechner-Knoten als auch der Größe des Graphen demonstriert wird, dies hat einen höheren Durchsatz an Anfragen pro Sekunde bei größerer Anzahl an verfügbaren Rechner-Knoten als Konsequenz. Zudem wird für die leichtgewichtigten Heuristiken zur Partitionierung des Graphen gezeigt, dass diese eine relativ gute Lastverteilung aufweisen und parallel zu anderen Systemfunktionen ausgeführt werden können, dies erlaubt ein ähnliches Performanz-Verhalten wie eine naive, traditionelle Hash-basierende Partitionierung, weist allerdings eine deutlich verbesserte Kanten-Lokalität auf.