Progressive Indexing of Geospatial Data

In today’s world, more and especially fast-moving data is being generated. To derive knowledge from this data, it must be analyzed. That also applies to geospatial data, which is exchanged in the form of files in CityGML format, for example. Traditionally, databases are used to manage and query large amounts of data. They are highly optimized to deliver low response times by loading data into an internal format and creating indexes. However, indexing and loading usually take place in advance, introducing latency between data arrival and actual analysis. Due to the fast-moving nature of data, it is important to achieve low latency to quickly analyze newly arriving data. Thus, the challenge is to achieve both a low latency and a low response time.
Ad-hoc requests, which are queries executed directly on the raw file without acceleration structures, introduce no initial overhead but have a poor response time compared to accelerated queries. In this work, we present a prototype that extends the ad-hoc approach by creating acceleration structures while performing queries. These structures are an index that is created alongside, and a list that stores the positions of objects from the file and is created during the first request on a file. As a result, analysis can be started directly and response times improve over time. We test our approach on a real dataset and compare it to the ad-hoc approach. The results of our evaluation show that both the index and the Offset-List improve response times compared to an ad-hoc solution. However, especially creating the Offset-List represents an additional cost for the first query, which must be compensated for within the subsequent queries.

In der heutigen Welt werden immer mehr und vor allem schnelllebige Daten erzeugt. Um aus diesen Daten Wissen abzuleiten, müssen sie analysiert werden. Das gilt auch für Geodaten, die z. B. in Form von Dateien im CityGML Dateiformat ausgetauscht werden. Traditionell werden Datenbanken für das Verwalten und Abfragen von großen Datenmengen eingesetzt. Diese sind stark optimiert, um niedrige Antwortzeiten zu erreichen, indem sie Daten in ein internes Format laden und Indexe erstellen. Die Indexierung und das Laden von Daten erfolgen in der Regel jedoch im Voraus, sodass zwischen der Ankunft der Daten und der eigentlichen Analyse eine Latenzzeit entsteht. Aufgrund der Schnelllebigkeit der Daten ist es wichtig, eine niedrige Latenzzeit zu erreichen, um neu eintreffende Daten schnell analysieren zu können. Die Herausforderung besteht also darin, sowohl eine niedrige Latenzzeit als auch eine niedrige Antwortzeit zu erreichen. Ad-hoc Anfragen, das heißt Abfragen, die direkt auf der Rohdatei ohne Beschleunigungsstrukturen ausgeführt werde, verursachen keinen initialen Overhead. Sie haben jedoch im Vergleich zu beschleunigten Abfragen eine schlechtere Antwortzeit. In dieser Arbeit stellen wir einen Prototyp vor, der den Ad-hoc-Ansatz durch die Erstellung von Beschleunigungsstrukturen während der Ausführung von Abfragen erweitert. Bei diesen Strukturen handelt es sich um einen Index, der parallel zu den Abfragen erstellt wird und eine Liste, welche Positionen von Objekten aus der Datei speichert und bei der ersten Abfrage auf die Datei erstellt wird. Dadurch kann direkt mit der Analyse begonnen werden und die Antwortzeiten
werden im Schnitt von Anfrage zu Anfrage besser. Wir testen unseren Ansatz an einem realen Datensatz und vergleichen ihn mit dem Ad-hoc Ansatz. Die Ergebnisse unserer Auswertung zeigen, dass sowohl der Index als auch die Offset-List die Antwortzeiten im Vergleich zu einer Ad-hoc-Lösung verbessern. Allerdings stellt insbesondere die Erstellung der Offset-Liste einen zusätzlichen Aufwand dar, der bei den nachfolgenden Abfragen kompensiert werden muss.