Bibliography | Girgis, 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 Trajektorien 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. Koordinatenbasierte 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 einem 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 eingeschrä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. Insbesondere 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 Anfragen 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, weitgehend 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 Herausforderung 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 Entscheidungsverfahrens.
|