Diploma Thesis DIP-2743

BibliographyGirgis, Alexander: Effiziente Verarbeitung topologischer Anfragen in räumlich partitionierten Datenbanken mobiler Objekte.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Diploma Thesis No. 2743 (2008).
94 pages, german.
Abstract

Moving Object Databases speichern Bewegungsdaten mobiler Objekte, wie die Trajekto­rien von Frachtcontainern, Transportfahrzeugen oder Mobiltelefonen, und stellen eine Schnittstelle für Anfragen über den Datenbestand zur Verfügung. Es können drei Klassen von räumlich-zeitlichen Anfragen unterschieden werden: Trajektorienbasierte Anfragen liefern Informationen zur Trajektorie eines gegebenen Objektes, wie beispielsweise die Höchst- oder Durchschnittsgeschwindigkeit, in einem gegebenen Zeitintervall. Koor­dinatenbasierte Anfragen, wie z.B. räumlich-zeitliche Gebietsanfragen, liefern Aussagen über alle mobilen Objekte, die sich im Anfragezeitraum innerhalb eines Zielgebietes oder in der Umgebung eines Punktes aufgehalten haben. Schließlich setzen topologische Anfragen die Trajektorie eines einzelnen Objektes mit einem Anfragezeitraum und ei­nem Zielgebiet in Beziehung. Sie können sowohl als trajektorienbasierte als auch als koordinatenbasierte Anfragen ausgewertet werden. Zentralisierte Datenbanksysteme sind für große Moving Objects Databases nur einge­schränkt verwendbar, da sie weder mit dem abzudeckenden Dienstgebiet noch mit der Anzahl der mobilen Objekte, deren Bewegungsdaten sie verarbeiten, skalieren. Räumlich partitionierte Datenbanksysteme teilen das Dienstgebiet in disjunkte Dienstregionen auf, für die jeweils ein Datenbankserver verantwortlich ist. Jeder Datenbankserver speichert die in seiner Dienstregion anfallenden Daten. Räumlich partitionierte Datenbanksysteme besitzen bessere Skalierungseigenschaften, stellen aber besondere Anforderungen an die zur Aktualisierung und zur Anfragenverarbeitung verwendeten Algorithmen. Insbeson­dere für das Routing von Anfragen und Teilergebnissen sowie die Ergebnisaggregation werden in einer solchen Datenbanksystem spezielle Algorithmen benötigt. Entsprechende Algorithmen wurden bisher vornehmlich für trajektorienbasierte An­fragen entwickelt. In der vorliegenden Arbeit werden diese Ansätze analysiert und anschließend Algorithmen zur Verarbeitung koordinatenbasierter Anfragen erforscht. Koordinatenbasierte Anfragen ermöglichen es, die beteiligten Datenbankserver auf Basis des Anfragegebietes zu bestimmen, so dass Anfragen direkt an diese verteilt, weit­gehend parallel bearbeitet und die Ergebnisaggregationen auf die beteiligten Knoten verteilt werden können. Durch geeignete Algorithmen kann außerdem die entstehende Netzwerklast minimiert werden. Aufbauend auf diesen Algorithmen wird anschließend ein Ansatz zur effizienten, verteilten Verarbeitung topologischer Anfragen entwickelt. Die wesentliche Herausfor­derung in der Bearbeitung topologischer Anfragen ist die dynamische Entscheidung zu Gunsten einer trajektorien- oder koordinatenbasierten Auswertung für eine gegebene Anfrage. Die vorliegende Arbeit diskutiert die Parameter eines geeigneten Entschei­dungsverfahrens.

Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Superviser(s)Rothermel, Prof. Kurt; Lange, Ralph
Entry dateJune 30, 2023
   Publ. Computer Science