Dissertation, Otto-Friedrich-Universität Bamberg, 2019

Space is everywhere, and so is spatial data. The digital revolution has led to an enormous pool of available spatial data, and the amount of newly generated spatial data is increasing day by day. Often, this spatial data is two-dimensional point data that in addition is associated with data objects such as media objects (e.g. pictures or texts). As a consequence of the huge amount of data objects which is generated and then has to be maintained, there is a need for effective and efficient search systems which are capable of addressing the spatial properties of the data objects. In this context, different search scenarios exist: The data objects might be maintained in a distributed system (i.e. on a set of different machines) or in a centralized system (i.e. on a single machine) which, in each case, leads to varying requirements for appropriate search systems. However, in both scenarios, the concept of resource description and selection is an applicable paradigm for conducting similarity searches with regard to the spatial properties of the data objects. Hereby, when focusing on the spatial aspects, a resource is an abstract entity that administers spatial point data. For describing the spatial footprint of a resource, its spatial data point set can be ‘summarized' by means of geometrically delineated areas which cover this data point set. These resource descriptions are then usable for a targeted selection of the resources which administer the relevant data objects based on spatial properties.

This thesis is concerned with the effective and efficient summarization of two-dimensional spatial point data as a means for resource description and selection in spatial application scenarios. The term ‘effective' refers to a spatially very accurate geometric delineation of the data point set to describe whereas the term ‘efficient' relates to its storage-space-efficient representation. Two search-based spatial application scenarios are assessed in this thesis, and in both, the search task can be modelled by adhering to the concept of resource description and selection.

The first scenario is a distributed application scenario in which spatial point data is maintained by a set of independent resources such as peers in a peer-to-peer network. Given a concrete query, the resource descriptions shall enable the targeted selection of the peers administering the relevant data points while ignoring ‘irrelevant' resources. The distributed application scenario is the main part of this thesis, and our summarization approaches are specifically developed for this purpose. Hereby, a variety of concepts is considered which include the compression of the data points, the use of arbitrarily complex bounding volumes to delineate them, the representation of complex objects (such as complex bounding volumes) with a set of simple objects, and a division of the data point set to describe into groups and the subsequent concise delineation of each group. Overall, 14 summarization approaches are presented in this thesis which can be categorized into data partitioning approaches, space partitioning approaches, and hybrid approaches. Following the specification of suitable resource selection schemes which are based on the various summaries, an extensive evaluation is conducted by means of assessing the approaches' performances for k nearest neighbor (kNN) queries. The evaluation considers different data collections and varying environmental conditions in order to assess the robustness of the approaches.

In the second application scenario, a utilization of our summarization approaches in a multidimensional data structure is assessed---which constitutes a centralized application scenario. More specifically, the two summarization approaches of the distributed application scenario which are most suitable for this purpose are integrated into an R-tree which administers sets of two-dimensional point data. The R-tree is a tree-based, centralized multidimensional data structure which has been the subject of intensive research over many years, starting in 1984. Within an R-tree, the ‘resources' are the nodes of the hierarchical tree structure. The resource descriptions shall enable the targeted traversal of paths in the tree structure when searching for the relevant data points given a specific query. Traditionally, these nodes are described by Minimum Bounding Rectangles (MBRs) which are very storage-space-efficient but rather coarse descriptions of a spatial footprint. After presenting the classical R-tree, the modifications to the R-tree that are necessary to integrate our summarization approaches are discussed. Also, appropriate algorithms for calculating summaries from a set of rectangles are outlined as this is a prerequisite for the efficient use of our sophisticated summarization approaches in R-trees. Following the specification of appropriate range query and kNN query algorithms, an extensive evaluation is conducted which assesses both the improvement potential over the traditional R-tree using MBR summaries as well as the degree of achievement by means of the straightforward approach to the integration that we pursue. Also in this evaluation, different data collections and varying environmental conditions are considered.

Overall, the thesis presents a wide variety of summarization approaches for describing sets of two-dimensional point data. These summarization approaches are excellently suited for usage in the investigated distributed application scenario. Furthermore, we assess the utilization of the two summarization approaches which are most appropriate for this purpose in an already very intensively researched centralized application scenario. Here, we examine further improvement potentials and identify important obstacles which are to overcome for our summarization approaches in such an environment.

Raum ist überall, und das gilt auch für räumliche Daten. Die digitale Revolution hat zu einem enormen Bestand an räumlichen Daten geführt, und die Menge der neu erzeugten räumlichen Daten nimmt von Tag zu Tag zu. Häufig handelt es sich bei diesen räumlichen Daten um zweidimensionale Punktdaten, die zusätzlich mit Datenobjekten wie z.B. Medienobjekten (etwa Bildern oder Texten) verknüpft sind. Aufgrund der großen Menge an Datenobjekten, die erzeugt werden und anschließend zu verwalten sind, besteht ein Bedarf an effektiven und effizienten Suchsystemen, die in der Lage sind, die räumlichen Eigenschaften dieser Datenobjekte zu adressieren. In diesem Zusammenhang sind verschiedene Suchszenarien vorstellbar: Die Datenobjekte können in einem verteilten System (d.h. auf einer Reihe von verschiedenen Maschinen) oder in einem zentralisierten System (d.h. auf einer einzelnen Maschine) verwaltet werden, was in beiden Fällen zu unterschiedlichen Anforderungen an die entsprechenden Suchsysteme führt. Jedoch ist in beiden Szenarien das Konzept der Ressourcenbeschreibung und -auswahl ein anwendbares Paradigma für Ähnlichkeitssuchen, die in Bezug auf die räumlichen Eigenschaften der Datenobjekte durchgeführt werden. Wenn man sich auf den räumlichen Aspekt konzentriert, ist eine Ressource dabei eine abstrakte Entität, die eine Menge räumlicher Punktdaten verwaltet. Zur Beschreibung des räumlichen Fußabdrucks einer Ressource können die von ihr verwalteten Punktdaten mittels geometrisch abgegrenzter Flächen, die die Punktmenge der Ressource räumlich überdecken, „zusammengefasst“ werden. Diese Ressourcenbeschreibungen können dann für eine gezielte Auswahl der Ressourcen, welche die in Hinblick auf räumliche Eigenschaften relevanten Datenobjekte verwalten, verwendet werden.

Die vorliegende Arbeit beschäftigt sich mit der effektiven und effizienten Zusammenfassung von Mengen zweidimensionaler, räumlicher Punktdaten zum Zwecke der Ressourcenbeschreibung und -auswahl in verschiedenen „räumlichen“ Anwendungsszenarien. Der Begriff „effektiv“ bezieht sich auf eine räumlich sehr genaue geometrische Abgrenzung der zu beschreibenden Datenpunktmengen, wohingegen der Begriff „effizient“ sich auf ihre speicherplatzsparende Repräsentation bezieht. In der vorliegenden Arbeit werden zwei suchbasierte „räumliche“ Anwendungsszenarien untersucht, und in beiden kann die Suchaufgabe über das Konzept der Ressourcenbeschreibung und -auswahl modelliert werden.

Das erste Szenario ist ein verteiltes Anwendungsszenario, bei dem Mengen räumlicher Punktdaten von einer Reihe unabhängiger Ressourcen wie Peers in einem Peer-to-Peer-Netzwerk verwaltet werden. Die Ressourcenbeschreibungen sollen eine gezielte Auswahl der Peers, die die für eine konkrete Anfrage relevanten Datenpunkte verwalten, ermöglichen. Gleichzeitig sollen „irrelevante“ Ressourcen bei der Anfragebearbeitung möglichst nicht kontaktiert werden. Das verteilte Anwendungsszenario ist der Hauptteil dieser Arbeit, und unsere Zusammenfassungsansätze sind speziell für diesen Zweck entwickelt worden. Für diese Ansätze wird eine Vielzahl von Konzepten betrachtet, die die Kompression der Datenpunkte, die Verwendung beliebig komplexer Hüllkörper, die Repräsentation komplexer Objekte (z.B. komplexer Hüllkörper) über eine Menge einfacherer Objekte sowie eine Aufteilung der zu beschreibenden Datenpunktmenge in Gruppen und die anschließende präzise Abgrenzung jeder einzelnen Gruppe beinhalten. Insgesamt werden in dieser Arbeit 14 Zusammenfassungsansätze vorgestellt, die in die Kategorien Datenpartitionierungsansätze (data partitioning approaches), Raumpartitionierungsansätze (space partitioning approaches) und hybride Ansätze (hybrid approaches) unterteilt werden können. Im Anschluss an die Spezifikation geeigneter Ressourcenauswahltechniken, die auf den verschiedenen Zusammenfassungen aufbauen, wird eine umfassende Evaluation der Zusammenfassungsansätze auf Basis von k-Nächste-Nachbarn-Anfragen (kNN-Anfragen) durchgeführt. Die Evaluation berücksichtigt dabei verschiedene Datenkollektionen und unterschiedliche Rahmenbedingungen, um die Robustheit der verschiedenen Ansätze zu untersuchen.

Im zweiten Anwendungsszenario wird eine Nutzung unserer Zusammenfassungsansätze in einer multidimensionalen Datenstruktur untersucht, was ein zentralisiertes Anwendungsszenario darstellt. Konkret werden die beiden für diesen Zweck am besten geeigneten Zusammenfassungsansätze aus dem verteilten Anwendungsszenario in einen R-Baum integriert, welcher Mengen zweidimensionaler Punktdaten verwaltet. Der R-Baum ist eine baumbasierte, zentralisierte multidimensionale Datenstruktur, die von 1984 an über viele Jahre intensiv erforscht wurde. Die „Ressourcen“ innerhalb eines R-Baums sind die Knoten der hierarchischen Baumstruktur. Die Ressourcenbeschreibungen sollen das gezielte Traversieren von Pfaden der Baumstruktur bei der Suche nach den für eine gegebene Anfrage relevanten Datenpunkten ermöglichen. Traditionell werden diese Knoten durch Minimum Bounding Rectangles (MBRs) beschrieben, die sehr speicherplatzeffizient sind, aber eher grobe Beschreibungen des räumlichen Fußabdrucks darstellen. Nach einer Präsentation des klassischen R-Baums werden in der Arbeit die notwendigen Modifikationen am R-Baum, welche zur Integration unserer Zusammenfassungsansätze notwendig sind, diskutiert. Außerdem werden geeignete Algorithmen zur Berechnung von Zusammenfassungen für eine gegebene Menge von Rechtecken entwickelt, da dies eine Voraussetzung für den effizienten Einsatz unserer komplexen Zusammenfassungsansätze in R-Bäumen ist. Im Anschluss an die Spezifikation geeigneter Algorithmen für Bereichs- und kNN-Anfragen wird eine umfangreiche Evaluation durchgeführt, die sowohl das Verbesserungspotenzial gegenüber dem „traditionellen“ R-Baum (der MBR-Zusammenfassungen verwendet) als auch den Zielerreichungsgrad unter Verwendung des geradlinigen Integrationsansatzes, den wir verfolgen, bewertet. Auch in dieser Evaluation werden verschiedene Datenkollektionen und unterschiedliche Rahmenbedingungen berücksichtigt.

Insgesamt präsentiert die Arbeit eine Vielzahl von Zusammenfassungsansätzen für die Beschreibung von Mengen zweidimensionaler Punktdaten. Diese Zusammenfassungsansätze eignen sich hervorragend für den Einsatz innerhalb des untersuchten verteilten Anwendungsszenarios. Darüber hinaus untersuchen wir einen Einsatz der beiden am besten dafür geeigneten Zusammenfassungsansätze in einem sehr intensiv erforschten zentralisierten Anwendungsszenario. Hierbei legen wir Verbesserungspotenziale dar und identifizieren wichtige Hindernisse, die es für unsere Zusammenfassungsansätze innerhalb eines solchen Umfeldes zu überwinden gilt.