24. GI-Workshop ”Grundlagen von Datenbanken“
der 24. Workshop ”Grundlagen von Datenbanken“ (GvD) 2012 fand in Lu¨bbenau, Spreewald, statt. Dieser vierta¨gige Workshop wird allja¨hrlich vom GI-Arbeitskreis Grundlagen von Informationssystemen im Fachbereich Datenbanken und Informationssysteme (DBIS) veranstaltet und hat die theoretischen, konzeptionellen und methodischen Grundlagen von Datenbanken und Informationssystemen zum Thema. Organisiert wurde der Workshop 2012 von der Forschungsgruppe Datenbank- und Informationssysteme am Institut fu¨r Informatik, Informations- und Medientechnik an der Brandenburgischen Technischen Universita¨t Cottbus.
Der Workshop soll die Kommunikation zwischen Wissenschaftlern/-innen im deutschsprachigen Raum fo¨rdern, die sich grundlagenorientiert mit Datenbanken und Informationssystemen bescha¨ftigen. Er ist insbesondere als Forum fu¨r Nachwuchswissenschafter/-innen gedacht, die ihre aktuellen Arbeiten in einem gro¨ßeren Forum vorstellen wollen. Das VattenfallTagungshotel Lu¨bbenau bot fu¨r eine erfolgreiche Diskussion optimale Rahmenbedingungen in der landschaftlich sehr reizvollen Umgebung des Spreewaldes.
Insgesamt wurden fu¨r den Workshop 15 Arbeiten eingereicht und jeweils von drei Gutachtern bewertet. Die Einfu¨hrung des Begutachtungsprozesses in den letzten Jahren sorgt schon im Vorfeld des Workshops fu¨r eine hohe Qualita¨t der Arbeiten. Die Einreichungen spannten den Bogen von klassischen Themen wie Indexverwaltung u¨ber weitere Themen wie mobile Systeme, ra¨umliche Datenbanken, Data Warehousing und XML-Verwaltung bis hin zu aktuellen Themen wie Self-Tuning, SaaS, Cloud Computing sowie probabilistische Datenbanken. Diese große Bandbreite der Gebiete reflektiert die Bandbreite von Problemen in der Datenbankgemeinde, wie sie auf großen Datenbankkonferenzen diskutiert werden. Dabei werden die Grenzen zwischen klassischen Datenbankthemen und benachbarten Bereichen immer durchla¨ssiger. Gerade diese thematische Bandbreite und die damit einher gehende Spezialisierung auf einzelne Themen macht es fu¨r Doktoranden schwierig, die eigene Arbeit richtig einzuordnen und interessante Querverweise zu benachbarten Bereichen zu sehen. Die zwanglose Diskussion in einer offenen Atmospha¨re des Workshop soll helfen, diese Lu¨cke zu schließen.
Fu¨r die Keynote-Vortra¨ge wurden Gu¨nther Specht, der Ausrichter des GvD-Workshops vom letzten Jahr und Bernhard Thalheim eingeladen. Ihnen sei an dieser Stelle fu¨r ihre Bereitschaft und ihr Kommen gedankt.
Des Weiteren danken wir dem Programmkomitee und allen Gutachtern fu¨r ihre Arbeit. Das Organisations-Komitee und dabei besonders Sandy Schneider, Marcel Zierenberg und Sascha Saretz haben den Großteil der Arbeit geleistet. Ohne ihren Einsatz und Engagement wa¨re der 24. Workshop nicht mo¨glich gewesen. Herzlichen Dank. Besonderen Dank auch an oEniksseySstcehmalelneh“n,wuenlcdheHdaigeenOrHgao¨npifsnaetriosnowseiehrdkeomnsGtrIu-kAtribvebitesgklreeitiset”hGarbuennd.lZaguemn SvcohnluIsnsfomrmo¨cahttieich allen Mitgliedern meines Lehrstuhl sowie den Autoren und Vortragenden fu¨r ihren Anteil am Gelingen am Workshop herzlich danken.
Programm-Komitee • Wolf-Tilo Balke, TU Braunschweig • Stefan Brass, Universita¨t Halle • Stefan Conrad, Universita¨t Du¨sseldorf • Erik Buchmann, Karlsruher Institut fu¨r Technologie • Torsten Grust, Universita¨t Tu¨bingen • Andreas Henrich, Universita¨t Bamberg • Hagen Ho¨pfner, Bauhaus-Universita¨t Weimar • Harald Kosch, Universita¨t Passau • Klaus Meyer-Wegener, Universita¨t Erlangen • Daniela Nicklas, Universita¨t Oldenburg • Gunter Saake, Universita¨t Magdeburg • Eike Schallehn, Universita¨t Magdeburg • Ingo Schmitt, BTU Cottbus • Holger Schwarz, Universita¨t Stuttgart • Gu¨nther Specht, Universita¨t Innsbruck Organisations-Komitee • Ingo Schmitt, BTU Cottbus • Sascha Saretz, BTU Cottbus • Marcel Zierenberg, BTU Cottbus • Sandy Schneider, BTU Cottbus Weitere Gutachter • Alexander Schulze, BTU Cottbus • Sascha Saretz, BTU Cottbus • Marcel Zierenberg, BTU Cottbus • Daniel Blank, Universita¨t Bamberg • Martin Scha¨ler, Universita¨t Magdeburg • Maik Mory, Universita¨t Magdeburg • Norbert Siegmund, Universita¨t Magdeburg
Datenbanken und Informationssysteme
Institut für Informatik Universität Innsbruck, Österreich guenther.specht@uibk.ac.at
KURZFASSUNG Woher? und Wohin? sind die bewegenden Fragen des Lebens, der Forschung und der Wissenschaft. Auch der Datenbanktechnologie. Dieser Vortrag gibt sich nicht mit der Antwort 42 zufrieden, sondern spannt einen Bogen bis hin zur interdisziplina¨ren Vernetzung der Datenbanken und Informationssysteme mit der Genetik. Dort gelang es heuer in der Haplogruppeneinteilung der Frage ”Out of Africa?“ mittels massivem IT- und DB-Einsatz eine neue Antwort zu geben. . .
Privacy-Enhanced Information Systems
Lehrstuhl für Technologie der Informationssysteme
Institut für Informatik
Christian-Albrechts-Universität zu Kiel thalheim@is.informatik.uni-kiel.de
KURZFASSUNG Nach einem kurzen U¨ berblick u¨ber den State-of-the-Art der Nutzung des Internets werden Prinzipien, Trends und Technologie fu¨r die Wahrung der Privatspha¨re dargestellt. Daraus lassen sich vielfa¨ltige Modellierungs-, Infrastruktur-, Technologie-, Sozial- und Rechtsprojekte zur Unterstu¨tzung von Privatspha¨re im Internet ableiten. Ziel ist die Entwicklung einer erweiterten Infrastruktur, in der Privatheit auch im Internet mo¨glich ist. Im Detail stellen wir Ansa¨tze vor, mit denen die Privatheit an Daten gesichert werden kann. Dazu ist ein Sicherheitsmodell, ein Inhaltemodell und ein Sicherungsmodell notwendig. Darauf kann ein Koordinationsmodell aufgesetzt werden. Techniken zur Stu¨tzung von Privatheit ko¨nnen darauf aufgesetzt werden. Dies wird anhand von zwei Datenbank-Ansa¨tzen gezeigt.
Bauhaus-Universität Weimar
Media Department / Mobile Media Group
Bauhausstraße 11, 99423 Weimar, Germany hoepfner@acm.org, maximilian.schirmer@uni-weimar.de Location, Location Modeling, Poly-Hierarchies, Enclave Problem, Multiple Belonging Location models are formal descriptions of locations (i. e., named sets of geographical positions) as well as of semantic relationships among locations. There exist various location models that vary in the considered location information, their level of detail, the kind of modelled relations and the used formal representation. In fact, more complex location models cover more aspects required for implementing location-aware or location-dependent systems, but also require more complex algorithms. As each application domain requires only a limited set of features, limiting a model to those features helps to improve system performance. In this paper, we discuss a novel location model called location poly-hierarchies that models the belonging of one location to one ore more other locations. Furthermore, we present an approach for creating location poly-hierarchies from a given set of locations.
INTRODUCTION AND MOTIVATION
In February 2004, the authors of [
Copyright is held by the author/owner(s). the Bauhausstraße 11 in Weimar, Germany and the assumption being that such information is usually more meaningful to the user.
Hence, we should use a service that maps positions to locations.
However, location-based applications differ in their required
precision [
The aforementioned example also illustrates another issue that is common for locations. In many cases, semantic locations form hierarchical structures. For example, in a hierarchical location model, earth is divided into continents, continents into countries, countries into states, states into cities, cities into streets and streets into street numbers, and so on. However, modelling locations as monohierarchies oversimplifies the reality and does not support multiple belongings. While, e. g., Weimar is part of Germany, Germany of Europe, etc., Istanbul is part of Turkey, but also of Europe and Asia.
Please note, we focus on geographic belongs-to-relationships
(subset and overlap) rather than on geopolitical ones. Location
hierarchies benefit from the fact that determining low-level location
information determines upper levels, too. Location poly-hierarchies
cure the mentioned model incompleteness while keeping the
benefit of a “fast” lookup of the correct path within the poly-hierarchy
(cf., [
How can one algorithmically create location poly-hierarchies from a given set of locations?
The remainder of this paper is structured as follows: Section 2 surveys related work. Section 3 introduces the concept of location poly-hierarchies. Section 4 presents our approach for creating them. Section 5 discusses implementation aspects. Section 6 summarises the paper and gives an outlook on future research. 2.
RELATED WORK
There has been a lot of active research on suitable models and representations for location data in the field of location models.
Location models are a core component of location-based
applications. They represent not only location information, but also spatial
(or even spatio-temporal [
The authors of [
However, there exist various real-world issues that require a polyhierarchical representation of locations. For example, Istanbul as the capital of Turkey, belongs to the continents Europe and Asia.
Hence, LIstanbul 6⊂ LEurope and LIstanbul 6⊂ LAsia hold. The same issue holds for Russia, which is located in Europe and in Asia, too. Another problem results from enclaves. Kaliningrad, e.g., is part of Russia, but this information is insufficient to decide whether Kaliningrad is part of Europe or part of Asia. The solution for these problems is the use of set overlaps in combination with containment relationships that form a location poly-hierarchy. cation model concepts. In the illustrated examples, the set-based approach is the least expressive one, as it only models the fact that there are two distinct locations within a set of locations, and a set of coordinates is assigned to each location. The hierarchical model adds containment information, and the graph-based model adds connectedness and distance in the form of edge weights.
Hierarchical location models as a special case of set-based
models represent containment relationships between different levels of
the model and are widely used as basis for location-based
applications [
LOCATION POLY-HIERARCHIES
The authors of [
For example, in a two-dimensional coordinate system1, the location of a building, lets say a train station (ts), is given as set Lts = {(x1, y1), . . . , (xn, yn)}, where each position (point) (xi, yi), 1 ≤ i ≤ n belongs to the train station building’s area. We discuss the calculation of the point set in Section 5.1. Consequently, we can characterise the location of an object or a person as a relationship between sets. A person, lets say Tanja, is located at the train station if LTanja ⊂ Lts holds. Recent positioning technologies like GPS 1For simplification purposes, we use two-dimensional coordinates in this paper. However, the formalism can easily be adapted to three dimensions.
Figure 2 illustrates the simplified poly-hierarchies for Istanbul and Kaliningrad. From the definition of poly-hierarchies, we know that they can be represented by a directed acyclic graph LP H = (V, E). Each node v ∈ V is a location and each directed edge e = (v1, v2) with v1, v2 ∈ V represents that the child node v2 belongs (semantically) to the parent node v1. Each location poly-hierarchy has an unique root node vr ∈ V with ¬∃vx ∈ V |(vx, vr), because the entire coordinate system is closed in case of locations (all considerable positions are elements of the set of all positions on earth).
Finally, for each leaf node vl ∈ V that must not have any child node ¬∃vx ∈ V |(vl, vx) holds.
From an implementation point of view, each node in the polyhierarchy graph has the structure (n, P, C) where n is the name of the location Ln, P is a set of edges to the parent nodes and C is a set of edges to child nodes. The root node r = (earth, P, C) is the only node in LP H for which P = ∅ ∧ C 6= ∅ must hold. For leaf nodes P 6= ∅ ∧ C = ∅, and for inner nodes P 6= ∅ ∧ C 6= ∅ hold. For the concept described in the remainder of this paper, it is required to know the level of each node within this graph. The level level(m) of a node m is defined as the number of nodes on the longest direct path from r to m, plus one. As illustrated in Figure 2(b), level(Russia) = 2 and level(Kaliningrad) = 3.
In a location mono-hierarchy each edge between a parent node and a child node represents the fact that all points of the location that corresponds to the child node are also elements of the location that corresponds to the parent node. However, as discussed before, it is not sufficient to use subset relationships only. The semantics of edges in the poly-hierarchical graph representation is as follows.
Given a (child) node c = (nc, Pc, Cc) the following relations hold:
Lnp 6= ∅. • For each parent node p ∈ V referenced in Pc having level(p) with ¬∃p0 ∈ Pc|p0 6= p ∧ level(p) = level(p0) the edge (p, c) ∈ E represents the subset relationship Lnc ⊂ Lnp . • For each (parent) node p ∈ V referenced in Pc having level(p) with ∃p0 ∈ Pc|p0 6= p ∧ level(p) = level(p0) the edge (p, c) ∈ E represents the overlapping relationship Lnc ∩
In other words this means that per hierarchy level each edge between a single parent node and the child node means an subset relationship. If a child node has more than only one parent node in the same level, then those links represent an overlap relationship. Furthermore, we know that the in the latter case, due to the directed nature of the edges, the child node must be a subset of the union of the respective parent nodes (i. e., the conjunction of the overlap relationships per level holds).
Europe level=1
Asia level=1
Europe level=1
Asia level=1
Figure 3 illustrates the link semantics for the Istanbul and the Kaliningrad examples. As one can see in Subfigure 3(a),LIstanbul ⊂ LTurkey as Turkey is the only parent node of Istanbul at level two.
Since Istanbul has two parent nodes on level one (i. e., Europe and Asia), these links represent the overlaps LIstanbul ∩ LEurope 6= ∅ and LIstanbul ∩ LAsia 6= ∅. The facts that (in addition) LTurkey ∩ LEurope 6= ∅ ∧ LTurkey ∩ LAsia 6= ∅ holds, also implies LIstanbul ⊂ LEurope ∩ LAsia.
We could use this “transitive” conclusion in a similar way for the Kaliningrad example, too. However, as show in Subfigure 3(b) it would reduce the expressivity of this LP H. Kaliningrad is only part of Europe but not of Asia. Hence, the Europe node is the only parent node of the Kaliningrad node at level one. 4. LPH CREATION
As discussed in Section 3 one could create an LP H using overlap relationships only. We already pointed out that, in order to be as expressive as possible, an LP H must use as many subset relationships as possible. Algorithm 1 creates the LP H from a given set L = {L1, . . . , Lk} of locations. For illustration purposes, we assume that names of locations are unique. However, one could also use location IDs instead of the names to guarantee uniqueness.
Our algorithm uses four main steps. In the first step (lines 7-24), it creates two subgraphs, one (V ⊂, E⊂) containing all subset reAlgorithm 1 Creating a location poly-hierarchy from a location set Input:
L = {L1, . . . , Lk} // location set Output:
LP H = (V, E)
// location poly-hierarchy lationships and one (V ∩, E∩) for all (additional) overlap relationships. Figure 4 illustrates these subgraphs for the Istanbul and the Kaliningrad examples. Obviously, step 1 might generate redundant edges (cf., Figure 4(c)) earth→Russia→Kaliningrad and earth→Kaliningrad) or (later on) unnecessary edges (cf., Figure 4(a) earth→Turkey). Furthermore, it generates loops in the overlap subgraph as overlap relations have a symmetric nature (cf., Figure 4(b) and Figure 4(d)). We illustrated those needless edges using dotted arrows.
Step 2 (lines 26-34) of the algorithm cleans up the overlap subgraph, i. e., it breaks the loops. Therefore, each node of this subgraph is analysed (cf. Figure 5). If the location represented by a node is a subset of the union of all its direct child nodes, then we remove the outgoing edges.
checking Europe Europe Asia
Russia
checking Asia Europe Asia
Russia
checking Russia Europe Asia
Russia
Figure 6 illustrates step 2 for the Istanbul example. After checking the nodes for Europe and Asia, the node for Turkey is checked.
So far, it has the child nodes Europe and Asia. As all points of Turkey belong to Europe or Asia, both must not be represented by child nodes of the Turkey node. So, these edges are removed. The same procedure removes the edges Istanbul→Europe and Istanbul→Asia.
a4er checking (1) Europe, (2) Asia
Europe
Asia Turkey Istanbul
Step 3 (lines 35-47) cleans up the subset subgraph using the transitivity property of subset relationships. In contrast to many graph optimisation approaches, we do not aim for reducing the number of edges in general, but for finding the minimal number of edges necessary for representing correct semantics (cf. Section 3). For the first optimisation (lines 36-39), we first calculate for each node the set of parent nodes having parent nodes themselves. Afterwards, we remove all direct edges from grandparents nodes as they can be reached through the parents. In our examples, this removes the edges earth→Istanbul and earth→Kaliningrad. A second optimisation (lines 40-46) checks whether a node is contained in the union of its sibling locations. If this is the case, we can remove the edge from the parent node (in our examples earth→Turkey and earth→Russia), even if this fragments the subgraph (cf. Figure 7).
Joining the subset subgraph(s) with the overlap subgraph, as it is done in the final step 4 (line 48), results in a connectedLP H. The fragmentation, that might have happened in step 2, is cured as the removed edges resulted from an overlap relationship between the involved nodes. For our examples, Algorithm 1 therefore creates the location poly-hierarchies shown in Figure 3.
Limiting factors Algorithm 1 requires a complete and closed set of locations. Without the location Asia, the Kaliningrad example graph would loose the LP H properties discussed in Section 3 as removing the Asia node also removes the edge Asia→Russia. Without this edge, the relationship Europe→Russia would be semantically wrongly interpreted as subset relationship. In fact, Algorithm 1 could be adapted in order to recognise this case through topologic sorting as the condition in line 33 would evaluate to false. Consequently, E∩ would still contain loops after step 2. Furthermore, the algorithm does not support differently named locations with equal sets of position points (i. e., La ⊆ Lb ∧ Lb ⊆ La holds). Step 1 would missinterpret this case as overlap relationship. Consequently, step 2 would nondeterministically remove one of the edges. A solution to this problem would be a cleanup phase that unifies those locations before starting Algorithm 1.
IMPLEMENTATION ASPECTS
As the “towards” in the title of this paper denotes, the presented
results are subject to ongoing research. We were not able to
finish the import of the evaluation database before the deadline. In
fact, importing the OpenStreetMap database containing data about
Europe (http://download.geofabrik.de/osm) using an
slightly adapted version of the osm2postgresql_05rc4.sh
script, which can be downloaded from http://sourceforge.
net/projects/osm2postgresql, is still in progress. So
far it took more than two weeks (PosgreSQL 9.1 [
Point sets of locations
The formal definition of locations and location poly-hierarchies as discussed in Section 3 is based on set theory. From a theoretical point of view, those sets are infinite. A common approach to handle this infinity problem is to decrease the precision of set elements through quantisation. However, it would not be useful or even possible to physically store (materialise) all points of all locations. Hence, for the implementation of our approach we decided to use a polygon-based representation of locations, where a set of polygons describes the boundaries of the locations. In principal, all points that are inside of one of these polygons belong to the location. The OpenStreetMap data model provides an additional multipolygon relation (cf., http://wiki.openstreetmap.org/ wiki/Multipolygon_relation) for representing more complex areas. It allows, e. g., for areas within a location that do not belong to this particular location. Hence, from an implementation point of view, a location is represented as a database view. The location name corresponds to the name of the view and the point set is defined by a database query resulting in the location outline (multi)polygon. 5.2
Set operations
Interpreting locations as (multi)polygons necessitates a different interpretation of the used set operations, too. As discussed in Section 4, Algorithm 1 has to check subset and set overlap relationships. Remember, a location La contains another location Lb if and only if Lb ⊂ La holds. Hence, La must contain all points (xb, yb) ∈ Lb. For the polygon-based locations, the subset relation means that the (multi)polygon describing La must cover those of Lb completely. Similarly, an overlap relation of two locations implies that the boundary (multi)polygons overlap (and vice versa).
Most geographical information system extensions, such as
PostGIS, provide the corresponding operators (cf. [
SUMMARY AND OUTLOOK
We presented a novel approach to model (geographical) relationships among locations. We extended the effective, but not complete location hierarchy approach in order to support enclaves and overlapping locations. We formally introduced the new location polyhierarchy model and presented an algorithm for creating a location poly-hierarchy from a given (closed and complete) set of locations.
We discussed limitations of the algorithm and also pointed out potential solutions to handle them. Finally, we discussed some issues that need to be considered for the implementation of our strategy.
However, there are many open issues that lead to future research directions. First of all we plan to evaluate the algorithm with real world data. We expect that the algorithm works properly, but we are aware of the huge amount of data that needs to be processed.
Hence, we will have to optimise the algorithm in order to avoid unnecessary (database) operations. Furthermore, we will research whether it would be better to explicitly keep the information about the type of the relationships. This extended graph model would, of course, ease the interpretability of the final location poly-hierarchy, but it would also increase the complexity of the model.
Bauhaus-Universität Weimar
Media Department / Mobile Media Group
Bauhausstraße 11, 99423 Weimar, Germany maximilian.schirmer@uni-weimar.de, hoepfner@acm.org Keywords Location Determination, Location Poly-Hierarchies, Energy Efficiency ABSTRACT Location awareness is a key feature of mobile information systems.
Typically, location is determined by interpreting a set of measured positions. Various approaches for position determination do exist.
They vary greatly in their precision, applicability, and energy requirements. As mobile devices are battery-driven, energy is one of the most limiting factors for the system’s uptime. Locations have a hierarchical nature and location-based applications differ in their required precision. In this paper, we present three approaches that utilise location poly-hierarchies in order to reduce the energy demand of continuous location determination: (1) We analyse the dependencies among the different hierarchy levels, (2) we incorporate an adaptive delay between measurements based on the hierarchy level and the calculated minimal required time to change, and (3) we select appropriate positioning techniques for each hierarchy level. We implemented and evaluated our approaches.
INTRODUCTION AND MOTIVATION
Navigation systems, social network apps, tourist information systems, event information systems, shop finders and many more heavily rely on position data of their users. Consequently, almost all modern smartphones supply positioning techniques. The most popular positioning technique is the Global Positioning System (GPS).
However, even devices that do not provide GPS hardware are able
to locate themselves using alternative techniques such as geotagged
Wi-Fi hotspot and cell tower databases (db), wireless signal
triangulation/lateration, or geotagging. Although all of them allow
localisation of a mobile device, they vary dramatically in precision,
applicability, hardware requirements, and energy demands. A GPS
request requires a GPS receiver with a much higher energy demand
compared to an on-device database lookup that is based on already
localised cell towers or Wi-Fi hotspots [
Copyright is held by the author/owner(s). other hand, indoor GPS positioning is almost impossible because of the occlusion and shielding of satellite signals created by building structures.
Mobile devices are battery-driven. So, energy is one of the most
limiting factors for their uptime. Additionally, the user acceptance
of location-based or context-aware mobile applications is
negatively influenced when the applications heavily strain the mobile
devices’ batteries. Furthermore, location-based applications differ
in their required precision [
minimal time that is required for leaving the current location. 3. We select appropriate positioning techniques for each hierar
chy level.
Our preliminary experimental results show that there is a strong potential in these techniques to reduce the energy demand compared to continuous GPS polling.
The remainder of the paper is structured as follows: Section 2 discusses related work. Section 3 introduces the concept of location hierarchies. Section 4 presents the three aforementioned approaches. Section 5 describes the evaluation approach and the results. Section 6 summarises the paper.
RELATED WORK
Our work mainly overlaps with the research fieldslocation models and energy-aware computing. Location models form the basis for all high-level operations on location data. Consequently, the frequent and enduring use of location data in mobile computing immediately raises the issue of the mobile devices’ limited energy Towards Using Location Poly-Hierarchies for Energy-E cient Continuous Location Determination resources. The field of energy-aware computing presents a variety of concepts and methods to compensate for these constraints.
Location Models
Location models as core components of location-based
applications represent location information and spatial (or even
spatiotemporal [
The authors of [
Hierarchical location models as a special case of set-based
models represent containment relationships between different levels of
the model and are widely used as basis for location-based
applications [
Energy-aware Computing
Energy-aware computing recognises the need for energy as a
factor in modelling and implementing computing systems in
order to manage and reduce their energy demand. This includes both
hardware and software systems. While energy-aware hardware has
been under active research for many years, energy-aware software
is still a novel and underestimated field of research. Hardware
solutions such as sleep modes or performance scaling cannot be directly
transferred or adapted to software systems. Energy-aware software
requires dedicated software engineering with new concepts and
algorithms [
One concept of energy-aware computing is resource substitution
[
The authors of [
TERMS AND DEFINITIONS
According to [
However, reality requires a more sophisticated location model.
Istanbul, as the capital of Turkey, belongs to Europe and Asia. The
same issue holds for Russia, which is located in Europe and in Asia,
too. Another problem results from enclaves: Kaliningrad is part
of Russia, but this information is not sufficient to decide whether
Kaliningrad belongs to Europe or Asia. The solution for these
problems is to use set overlaps instead of containment relationships in
combination with a poly-hierarchical location model [
Figure 2 illustrates the simplified poly-hierarchies for Istanbul and Kaliningrad, represented as directed acyclic graphs. Each node is a location and each directed edge represents that the child node belongs (semantically) to the parent node(s). Moreover, the location poly-hierarchy LP H has a unique root node because the entire coordinate system is closed in case of locations (all considerable positions are elements of the set of all positions on earth). We do not discuss the construction of LP H in this paper, but assume that an
ANWENDUNGSBEISPIEL Das folgende Anwendungsbeispiel illustriert eine logikbasierte Ähnlichkeitsanfrage anhand mehrerer Features.
Gegeben sei eine Datenbank mit Bildern verschiedener Pilze und Informationen über deren Art und Giftigkeit. Ziel sei es nun anhand eines Anfragebildes eines gesammelten Pilzes, die Art des Pilzes zu ermitteln und so zu bestimmen, ob der Pilz essbar ist. Die aus den Bildern extrahierten Features umfassen dabei aus den Pixeldaten erzeugte Farb- (color ) und Formfeatures (shape) sowie aus den Metadaten stammende Informationen, wie das Datum der Bildaufnahme (date) oder die GPS-Koordinaten des Aufnahmeortes (gps).
Zur Ermittlung der (Un-)Ähnlichkeit von Objekten werden jeweils
für das Feature geeignete Distanzfunktionen genutzt,
beispielsweise die Earth Mover’s Distanzfunktion [
Eine Anfrage, bestehend aus nur einem Feature, genügt nicht, um eine korrekte Zuordnung der Pilzarten vorzunehmen. So kann zum Beispiel allein anhand der Farbfeatures eines Pilzes nicht immer ein Rückschluss auf dessen Art gezogen werden, wenn sich etwa die Form stark von der des Anfragebildes unterscheidet. In diesem Fall ist eine UND-Verknüpfung der Features nötig: shape≈ ∧ color ≈. Für den Fall, dass der Pilz des Anfragebildes eine für seine Art sehr untypische Form aufweist (¬shape≈) und daher anhand dieser nicht zugeordnet werden kann, soll stattdessen allein anhand der GPS-Koordinaten des Bildes (gps≈) auf dessen Art geschlossen werden. Als zusätzliche relationale (scharfe) Bedingung sollen nur Pilze betrachtet werden, die im selben Monat gesammelt wurden, wie der Pilz des Anfragebildes (date=). Eine logische Verknüpfung der Features eines Anfragebildes sieht dann wie folgt aus, wobei θ1, θ2 für Parameter stehen, die eine unterschiedliche Gewichtung der Teilbedingungen ermöglichen.
date= ∧ ((shape≈ ∧ color ≈) ∨θ1,θ2 (¬shape≈ ∧ gps≈)) (2)
Nach einer DNF-Normalisierung und Transformation anhand der in Abschnitt 2.2 beschriebenen Transformationsregeln, ergibt sich aus dem booleschen Ausdruck (2) folgende arithmetische Formel: (θ1 ∗ date= ∗ shape≈ ∗ color ≈) + (θ2 ∗ date= ∗ (1 − shape≈) ∗ gps≈) (3)
ANFORDERUNGEN
In [
Flexibilität: Multi-Feature-Anfragen setzen sich aus unterschiedlichen Features und Distanzfunktionen zusammen, das Indexierungsverfahren muss daher unabhängig von Art und Struktur der Features sein und ein breites Spektrum an Distanzfunktionen unterstützen. Die Anzahl der unterschiedlichen zur Verfügung stehenden Features ist potentiell hoch. Das Indexierungsverfahren muss daher mit einer großen Menge von Features umgehen können, auch wenn nur eine Teilmenge dieser für eine Anfrage genutzt wird. Je nach Anfrage können sich die genutzten Features unterscheiden.
Ebenso sind unterschiedliche logische Kombinationen und unterschiedliche Gewichtungen der selben Features möglich. Das Indexierungsverfahren darf daher nicht nur auf eine logische Kombination zugeschnitten werden, sondern muss mit beliebigen logischen Kombinationen und Gewichtungen umgehen können.
Sucheffizienz: Die Anzahl der nötigen Berechnungen der
Distanzfunktion und die Anzahl von I/O-Operationen (Seitenzugriffe)
dienen als Effizienzmaß für Indexierungsverfahren. Die Grundlage
für die Bewertung der Sucheffizienz bildet der Vergleich mit dem
Suchaufwand des linearen Scans der Datenbank. Ein effizientes
Indexierungsverfahren sollte diesen linearen Aufwand stets
unterbieten. Es existieren zwar Verfahren, welche eine sehr hohe
Sucheffizienz bieten, dabei aber einen nicht realisierbar hohen
Speicherverbrauch verursachen (vgl. [
Skalierbarkeit: Ein inhärentes Problem der Ähnlichkeitssuche
ist der Fluch der hohen Dimensionen (FdhD [
Die Kombination von Features bewirkt hier ebenfalls eine Erhöhung der (intrinsischen) Dimensionalität. Ein geeignetes Indexierungsverfahren für Multi-Feature-Anfragen muss daher Möglichkeiten bieten, mit dem FdhD umzugehen und möglichst ohne Effizienzeinbußen skalierbar bezüglich der (intrinsischen) Dimensionalität einzelner Features und der Kombination mehrerer Features sein.
STAND DER TECHNIK Der folgende Abschnitt geht auf den Stand der Technik auf dem Gebiet der effizienten Verarbeitung von Multi-Feature-Anfragen ein. Die existierenden Verfahren werden kurz vorgestellt und ausschnittsweise hinsichtlich der in Abschnitt 4 definierten Anforderungen bewertet. Wir beschränken uns dabei auf Verfahren für die exakte Suche der nächsten Nachbarn und gehen nicht auf Spezialfälle wie die approximative Suche oder zusätzliche Anfragearten wie getNext (Ranking-Anfrage) ein. 5.1
Combiner-Algorithmen
Combiner-Algorithmen [
Combiner-Algorithmen sind keine Indexierungsverfahren, sondern arbeiten auf einer darüber liegenden Ebene. Sie legen nicht fest, wie die sortierten Listen bereitgestellt werden. Um eine effiziente Suche zu ermöglichen, sollte der Zugriff über Indexierungsverfahren mit Unterstützung von getNext-Anfragen umgesetzt werden.
Combiner-Algorithmen erlauben eine dynamische Auswahl der
verwendeten Features sowie unterschiedliche
Aggregationsfunktionen und Gewichtungen. Aufgrund der Forderung nach globaler
Monotonie kommen sie jedoch nicht für alle logikbasierten
MultiFeature-Anfragen in Frage. Formel 3 ist beispielsweise nicht
global monoton steigend, da eine Erhöhung des Ähnlichkeitswerts
shape≈ nicht in jedem Fall zu einer Erhöhung des aggregierten
Ähnlichkeitswerts führt. Ein weiterer Nachteil ist die geforderte
Bereitstellung der sortierten Listen, da Indexstrukturen mit
effizienten getNext-Anfragen nicht immer zur Verfügung stehen und sich
durch die getrennte Verwaltung jedes einzelnen Index ein
Mehraufwand ergibt.
3Die Dimensionalität eines Features ergibt sich aus der Anzahl
seiner Featurewerte. Die intrisische Dimensionalität lässt sich
beispielsweise anhand der paarweisen Distanzen zwischen den
Featurewerten der Datenbankobjekte abschätzen und ist dann definiert
als ρ = μ2/2 ∗ σ2 [
Räumliche Indexierung Räumliche Indexierungsverfahren gehen davon aus, dass die Features in Form von Vektoren vorliegen und die euklidsche Distanzfunktion (L2-Distanzfunktion) zur Berechnung der Unähnlichkeit zwischen den Featurevektoren verwendet wird. Da diese Beschränkung im Widerspruch zur Flexibilität steht, scheidet die Verwendung räumlicher Indexierungsverfahren aus. Dennoch soll im Folgenden auf sie eingegangen werden, da ihre Konzepte teilweise übertragbar sind.
Hierarchische Verfahren, wie zum Beispiel der R-Baum [
Die Sucheffizienz des Verfahrens ergibt sich daraus, dass die
Bitsignaturen in der Filterphase sequentiell aus Signaturdateien
gelesen werden und durch den Ausschluss von Objekten die
Anzahl teurer, wahlfreier Zugriffe in der Verfeinerungsphase
verringert wird. Für Multi-Feature-Anfragen ist eine Anpassung der
VADatei nötig.
GeVAS [
Liegen die einzelnen VA-Dateien auf der gleichen Festplatte
(HDD) ergeben sich für GeVAS Effizienzprobleme beim Lesen der
Daten vom Sekundärspeicher, da statt jede VA-Datei einzeln
sequentiell zu lesen, der Lesekopf der Festplatte zwischen den
verschiedenen VA-Dateien hin und her springen muss [
Metrische Indexierung Metrische Indexierungsverfahren stellen keine Anforderungen an die Art der Featuredaten. Im Gegensatz zu räumlichen Indexierungsverfahren erlauben sie daher auch die Indexierung von Features bei denen es sich nicht um Vektoren handelt (zum Beispiel textuelle Daten) oder die nicht die euklidsche Distanzfunktion verwenden. Sie erfordern lediglich das Vorliegen einer Metrik.
Eine Metrik δ ist eine Distanzfunktion, für die folgenden Eigenschaften für alle oi, oj , ok ∈ U gelten: δ(oi, oj ) > 0 für oi 6= oj (Positivität), δ(oi, oi) = 0 (Selbstidentität), δ(oi, oj ) = δ(oj , oi) (Symmetrie) und δ(oi, ok) ≤ δ(oi, oj ) + δ(oj , ok) (Dreiecksungleichung).
Der Ausschluss von Objekten wird mithilfe der Dreiecksungleichung erreicht, die es ermöglicht, untere und obere Grenzen bezüglich der Distanz von Anfrageobjekt und Datenbankobjekten zu bestimmen. Die Grenzen können effizient anhand von vorberechneten Distanzen zu einem oder mehreren Referenzobjekten5 ermittelt werden. Die untere und die obere Grenze für die Distanz δ(q, oi) und ein Referenzobjekt p sind wie folgt definiert: (4)
Analog zu räumlichen Indexierungsverfahren lässt sich zwischen
hierarchischen (M-Baum [
Der Großteil der existierenden metrischen
Indexierungsverfahren ist auf die Indexierung anhand einer einzigen
Distanzfunktion ausgelegt. Die Forderung nach der Unterstützung beliebiger
logischer Kombinationen kann daher nicht erfüllt werden.
MultiMetrische Indexierungsverfahren [
Der M2-Baum verlangt die lokale Monotonie der
Aggregationsfunktion. Die arithmetische Formel 3 erfüllt jedoch auch
diese Eigenschaft nicht. Analog zu GeVAS lässt sich die
MonotonieEigenschaft aber auch hier so abschwächen, dass beliebige,
logikbasierte Multi-Feature-Anfragen möglich werden (siehe
Abschnitt 6.1). Der M2-Baum erlaubt somit beliebige, logische
Kombinationen und eine dynamische Auswahl der tatsächlich genutzten
Features. Da es sich beim M2-Baum um ein hierarchisches
Verfahren handelt, nimmt die Sucheffizienz jedoch aufgrund des Fluchs
der hohen Dimensionen mit steigender intrinsischer
Dimensionalität der Features stärker ab, als bei nicht-hierarchischen Verfahren
[
Pivot-Objekt, die das gleiche Konzept widerspiegeln.
KONZEPT Dieser Abschnitt beschreibt das Konzept eines Indexierungsverfahrens zur effizienten Verarbeitung logikbasierter Multi-FeatureAnfragen. Dazu wird zuerst auf die Berechnung aggregierter Distanzgrenzen eingegangen. Die Übertragung des GeVAS-Ansatzes auf den metrischen Raum stellt den Kern des Konzepts dar. Wir wählen GeVAS aufgrund seiner Flexibilität im Bezug auf Featureanzahl und -auswahl sowie aufgrund seiner besseren Skalierbarkeit im Bezug auf die Dimensionalität als hierarchische Verfahren.
Zusätzliche Anpassungen, wie die direkte Berechnung exakter
Distanzen für eine Teilmenge der Features, dienen dazu, die
Sucheffizienz des entworfenen Verfahrens bei steigender Featureanzahl zu
verbessern.
Die korrekte Berechnung aggregierter Distanzgrenzen6 hängt von
der Monotonie der Aggregationsfunktion ab. Zur Berechnung der
oberen Distanzgrenze einer global monoton steigenden
Aggregationsfunktion müssen die oberen Grenzen aller Teildistanzen in die
Aggregationsfunktion eingesetzt werden [
Für die obere Distanzgrenze lokal monotoner Aggregationsfunktionen kommt es auf die Monotonie der einzelnen Argumente an.
Bei monoton steigenden Argumenten muss die obere
Distanzgrenze und bei monoton fallenden Argumenten die untere
Distanzgrenze eingesetzt werden [
Die arithmetische Formel (3) ist nicht lokal monoton. Jedoch liegt eine Monotonie vor, für die wir den Begriff fixe Monotonie einführen. Hierbei hängt die Monotonie eines Arguments der Aggregationsfunktion von den Wertebelegungen der anderen Argumente ab. Eine fix monotone Funktion kann also in einem Argument für bestimmte Wertebelegungen monoton fallend und für alle andere Wertebelegungen monoton steigend sein. In Formel (3) ergibt sich die fixe Monotonie daraus, dass das Argument shape≈ in einem Teil der Formel negiert und in einem anderen Teil nichtnegiert auftritt.
Die aggregierte obere Distanzgrenze für fix monotone Funktionen ergibt sich durch das Einsetzen aller möglichen Kombinationen von oberen und unteren Grenzen in die Aggregationsfunktion und einer Auswahl des maximalen Ergebnisses.
C = dl1b , d1ub
× · · · × {dlmb , dumb } daugbg = max agg(c) c∈C (5) (6) Wie zuvor erwähnt, lässt sich die Berechnung der aggregierten Grenzen in GeVAS und M2-Baum entsprechend anpassen.
Es kann gezeigt werden, dass alle mithilfe von CQQL erzeugten arithmetischen Formeln eine der beschriebenen Monotonien erfüllen. Die Monotonie kann dabei allein anhand der Syntax der Anfrage bestimmt werden. Auf die Darstellung der Beweise dieser Eigenschaften wird an dieser Stelle aus Platzgründen verzichtet. 6.2
Metrisches Filter-Refinement Im Gegensatz zu GeVAS werden die Signaturen beim metrischen Filter-Refinementnicht anhand der Featuredaten der Datenbankobjekte ermittelt, sondern ergeben sich aus den Distanzen der Datenbankobjekte zu Referenzobjekten. Jede Signaturdatei besteht daher aus den Bitsignaturen der Distanzen jedes Datenbankobjekts zu einer Menge von Referenzobjekten. Die Reihenfolge der Datenbankobjekte ist dabei in allen Signaturdateien gleich. Die kNN-Suche verläuft analog zu GeVAS, wobei der Ausschluss von Objekten jedoch anhand aggregierter Ähnlichkeitsgrenzen stattfindet. 6Die Beschreibungen lassen sich analog auf Ähnlichkeitsgrenzen anwenden.
Für die Auswahl geeigneter Referenzobjekte stehen
verschiedene Verfahren zur Verfügung, darunter die zufällige Auswahl oder
die inkrementelle Auswahl entfernter Objekte [
Bei der Indexerzeugung werden für einen repräsentativen
Ausschnitt der Datenbank die paarweisen Distanzen je Feature
bestimmt. Ein Equi-Height-Histogramm [
Nach einem in [
Um diesem Problem zu begegnen, werden bei steigender Featureanzahl, statt Distanzgrenzen für jedes einzelne Feature zu nutzen, nur noch für eine Teilmenge der verwendeten Features Distanzgrenzen abgeschätzt. Für alle anderen Features werden direkt die exakten Distanzen berechnet. Aus der exakten Berechnung von Teildistanzen ergibt sich ein Mehraufwand gegenüber der Nutzung von Distanzgrenzen. Dieser Mehraufwand kann jedoch ausgeglichen werden, wenn durch diese exakte Berechnung genügend zusätzliche Objekte ausgeschlossen werden können.
Dieses Prinzip lässt sich in der Filterphase anwenden um mehr Objekte auszuschließen. Analog zum sequentiellen Lesen der Signaturdateien müssen die Features in diesem Fall ebenfalls sequentiell gelesen werden, um die Sucheffizienz in der Filterphase zu garantieren.
Das gleiche Prinzip kann in der Verfeinerungsphase genutzt werden, um die Suche früher und mit weniger exakten Distanzberechnungen abbrechen zu können. Statt für ein Objekt in der Verfeinerungsphase direkt alle Teildistanzen auf einmal exakt zu berechnen und zu aggregieren, wird schrittweise vorgegangen. Jedes Mal, wenn ein Objekt in der Verfeinerungsphase am Anfang der Kandidatenliste steht, für das noch nicht alle Teildistanzen berechnet wurden, wird eine Teildistanz berechnet und das Objekt anhand der neuen (genaueren) aggregierten Ähnlichkeitsgrenze wieder in die Kandidatenliste einsortiert. Ein Vorteil ergibt sich dann, wenn der Ausschluss eines Objekts von nur wenigen Teildistanzen abhängt. Bei einer geeigneten Reihenfolge der berechneten Teildistanzen müssen dann nur diese diskriminierenden Distanzen exakt berechnet werden, die Berechnung aller weiteren Teildistanzen kann gespart werden.
Die Auswahl der Features, für die exakte Distanzen berechnet werden, erfolgt statisch (zur Indexierungszeit) oder dynamisch (zur Anfragezeit) nach unterschiedlichen Kriterien, wie der (intrinsischen) Dimensionalität der Features oder der Berechnungsdauer der zugehörigen Distanzfunktion. 6.6
Indexauswahl Die Sucheffizienz des beschriebenen Verfahrens hängt besonders von der Anzahl der verwendeten Features und der daraus resultierenden (intrinsischen) Dimensionalität ab. Hierarchische Verfahren können bei niedriger (intrinsischer) Dimensionalität, aufgrund der hohen Lokalität der Daten, größere Mengen von Objekten auf einmal ausschließen und dadurch effizienter als nicht-hierarchische Verfahren sein. Ein Vergleich des entworfenen Konzepts mit dem angepassten M2-Baum dient daher zur Bestimmung der Schnittpunkte bezüglich der Sucheffizienz beider Ansätze. Eine Selektion des effizienteren Index kann dann entweder bereits bei der Indexerzeugung oder erst zur Anfragezeit anhand der in der Anfrage genutzten Features und ihrer (intrinsischen) Dimensionalität stattfinden. Überschreitet die (intrinsische) Dimensionalität eine bestimmte Grenze, ist unter Umständen ein Rückfall auf den linearen Scan sinnvoll.
ZUSAMMENFASSUNG In dieser Arbeit wurde ein Konzept zur flexiblen Indexierung für Ähnlichkeitssuche mit logikbasierten Multi-Feature-Anfragen vorgestellt. Dazu wurden die spezifischen Anforderungen an geeignete Indexierungsverfahren definiert und der Stand der Technik im Bezug auf diese Anforderungen analysiert. Das entwickelte Konzept zur Indexierung basiert auf einer Übertragung und Anpassung des GeVAS-Ansatzes auf den metrischen Raum. Der Index ist dadurch unabhängig von der genutzten logischen Kombination, der Art und Struktur der verwendeten Features und unterstützt eine Vielzahl unterschiedlicher Features und Distanzfunktionen zur Berechnung der Unähnlichkeit.
Als zukünftige Arbeiten verbleiben Teile der Implementierung, die Bestimmung der optimalen Indexparameter und die Evaluation des Konzeptes anhand von synthetischen und realen Daten. Die Unterstützung von Multi-Objekt-Anfragen sowie von Distanzfunktionen die keine Metriken sind, stellen weitere Herausforderungen dar.
Literatur
Klemens Böhm u. a. “Fast Evaluation Techniques for Complex
Similarity Queries”. In: Proceedings of the 27th International Conference
on Very Large Data Bases. VLDB ’01. 2001, S. 211–220.
[
Recogn. Lett. 24 (14 2003), S. 2357–2366.
[
S. 137–146.
[
Surv. 33 (3 2001), S. 273–321.
[
Matthias Jarke u. a. 1997, S. 426–435.
[
Antonin Guttman. “R-trees: a dynamic index structure for spatial searching”. In: Proceedings of the 1984 ACM SIGMOD international conference on Management of data. SIGMOD ’84. 1984, S. 47– 57.
Yannis Ioannidis. “The history of histograms (abridged)”. In: Proceedings of the 29th international conference on Very large data bases - Volume 29. VLDB ’03. 2003, S. 19–30.
Yossi Rubner, Carlo Tomasi und Leonidas J. Guibas. “The Earth Mover’s Distance as a Metric for Image Retrieval”. In: Int. J. Comput.
Vision 40 (2 2000), S. 99–121.
Hanan Samet. Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and
Geometric Modeling). 2005.
[
trieval, Suchalgorithmen und Anfragebehandlung. 2005.
[
Journal 17 (1 2008), S. 39–56.
[
space”. In: Data Knowl. Eng. 56 (3 2006), S. 245–286.
[
Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces”. In: Proceedings of the 24rd International Conference on Very Large Data Bases. VLDB ’98. 1998, S. 194– 205.
Lofti A. Zadeh. “Fuzzy Logic”. In: Computer 21 (1988), S. 83–93.
David Zellhöfer und Ingo Schmitt. “A preference-based approach for interactive weight learning: learning weights within a logicbased query language”. In: Distributed and Parallel Databases 27 (1 2010), S. 31–51.
David Zellhöfer und Ingo Schmitt. “Approaching Multimedia Retrieval from a Polyrepresentative Perspective”. In: Adaptive Multimedia Retrieval. Context, Exploration, and Fusion. Hrsg. von Marcin Detyniecki u. a. Bd. 6817. Lecture Notes in Computer Science. 2011, S. 46–60.
Institute of Technical and Business Information Systems University of Magdeburg grebhahn@st.ovgu.de
Institute of Technical and Business Information Systems University of Magdeburg rschroet@st.ovgu.de
Institute of Technical and Business Information Systems University of Magdeburg dbronesk@st.ovgu.de
Center for Digital Engineering University of Magdeburg vkoeppen@ovgu.de
Institute of Technical and Business Information Systems University of Magdeburg schaeler@ovgu.de
Institute of Technical and Business Information Systems
University of Magdeburg saake@ovgu.de ABSTRACT In recent years, index structures for managing multi-dimensional data became increasingly important. Due to heterogeneous systems and specific use cases, it is a complex challenge to find an appropriate index structure for specific problems, such as finding similar fingerprints or micro traces in a database. One aspect that should be considered in general is the dimensionality and the related curse of dimensionality.
However, dimensionality of data is just one component that have to be considered. To address the challenges of finding the appropriate index, we motivate the necessity of a framework to evaluate indexes for specific use cases. Furthermore, we discuss core components of a framework that supports users in finding the most appropriate index structure for their use case.
Keywords index structures, evaluation, multi-dimensional data 1. INTRODUCTION
In the last years, data storage and management in computer-aided systems became more advanced, because of an increasing amount of unstructured data being stored. For example, in multimedia databases images or videos are stored and analyzed to find similar data items. A special use case is the Digi-Dak Database Project1, where multi-dimensional feature vectors of fingerprints and micro traces are stored in a database. To manage these data items, methods are required to handle unstructured data in an appropriate way. 1https://omen.cs.uni-magdeburg.de/digi-dak 24th GI-Workshop on Foundations of Databases (Grundlagen von Datenbanken), 29.05.2012 - 01.06.2012, Lübbenau, Germany.
Copyright is held by the author/owner(s).
It is possible to extract feature vectors from an item to manage the data in a compressed and meaningful way. For managing these feature vectors, multi-dimensional index structures can be used. In general, the question arises, which index structure supports managing data best. Throughout this paper, index structure performance describes suitability with respect to a specific use case. However, we analyze core aspects that have to be considered, if trying to answer this for a specific use case. In order to achieve a reconstructible and valid comparison, we present the idea of a framework that allows the comparison of different index structures in a homogeneous test environment.
This paper is organized as follows: In Section 2, we give a short overview of basic components that have to be considered for evaluating the performance of index structures. Within Section 3, we give an overview of additional challenges, which have to be handled by using index structures in a specific use case. Finally, in Section 4, we present core components that a framework needs for quantitatively evaluation of multi-dimensional index structures with respect to different use cases.
BASIC CHALLENGES
Querying multi-dimensional data in an efficient way is a complex challenge. Within the last decades, new index structures are proposed and existing once are improved to solve this challenge. Regarding a specific use case, it is not suitable to consider an index structure in isolation. Additionally data properties, used query types, and underlying distance metrics have to be taken into account. In this section, we give a short overview of these four basic challenges.
Characteristics of data cause main challenges of querying
data within a database system. For instance, data
dimensionality has to be considered, because existing index
structures are generally effected by the curse of dimensionality
[
Query Types
Based on the work of Bo¨hm et al. [
Definition: -similarity Query.
Two data points p1 and p2 are -similar if and only if
d(p1, p2) ≤ . The function d defines a similarity measure
for two points. In literature, similarity measures are
often replaced by distance metrics, which we review in
Section 2.3. For finding all points in the data base being
similar, an -similarity query is executed. A special case of
the -similarity is represented for = 0, because this implies
two identical points and an exact match is executed [
The data point p1 is NN-similar to p2 with respect to a data base of points DB if and only if ∀p ∈ DB, p 6= p1 : d(p2, p1) ≤ d(p2, p). For NN-similarity queries, all points in a database are retrieved that are NN-similar to the query point. An extension to the NN-similarity query is presented, when instead of a nearest neighbor, k nearest neighbors have to be retrieved. In this paper, we call the resulting query k-NN query.
Apart from the mentioned similarity range query, window
queries are common queries and often called range queries in
literature [
To execute similarity queries, we require a function computing the similarity of two data items. To this end, similarity for equal points is 1 whereas the maximum dissimilarity is expressed by 0. Equivalent information is delivered from distance metrics, whereupon two data items are more similar, the smaller their distance is.
The most common distance metrics are Minkowsky class metrics, also called Lp distance metrics. The distance of two data items x and y is computed by:
Lp(x, y) = d X (xi − yi)p 1/p.
i=1
By choosing different values for p, different representatives
of this class are produced. For p = 2, the Euclidean distance
metric is generated, which dominates common database
systems according to Bugatti et al. [
Beneath these distance metrics, there are many other
metrics, such as Canberra [
R6
R4
R12
R10
R2
R8 A R9 B
R7 C
Since we aim at providing a comprehensive set of indexes,
we want to consider different types of index structures. Thus,
we use the classification of Weber et al. [
Alternatively, Andoni and Indyk [
Giving an overview of existing index structures, we introduce promising exact index structures in this section. Furthermore, the difference between space partitioning and data partitioning methods is stated by presenting at least one index structure for each category.
R-Tree.
One of the most important multi-dimensional index
structures is the R-Tree [
However, the basic idea of these index structures is to administrate points hierarchically in a tree. The R-Tree partitions the data space using minimum bounding rectangles (MBR). A minimum bounding rectangle can be described by two points, being the end of the diagonal of the rectangle. Stepwise, the space is partitioned by MBRs, so that the superordinate MBR encloses all of its subordinate MBRs, as we visualize in Figure 1.
With increasing dimensionality, R-Trees face the challenge
of overlapping MBRs. A query rectangle, situated in a
region, where two or more MBRs overlap (like the MBR R2
and R3 in Figure 1), forces the R-Tree to follow up two or
more different routes in the tree. Thus, the query
performance decreases [
An example for an exact space partitioning index
structure is the Pyramid Technique, which was introduced by
Berchtold et al. [
Second, for managing the space enclosed by a pyramid, the pyramids are divided in pyramid slices. According to the query types supported by the index structure, the partition of pyramids can be done in different ways. In Figure 2, we present two different possible methods for partitioning a pyramid, for a two dimensional normalized space.
In particular, the partition of Figure 2 (a) is proposed
by Berchtold et al. [
In 1997, Weber and Blott [
A B
F I
H Z
X 00
C
E G Y 01
T
D W
V U 10
S
J Q
L R
M
K N
P O 11
Figure 3: Partitioning of the VA-File.
degeneration of most index structures to a sequential scan, if
the dimensionality of data points exceeds a certain limit [
The VA-File divides each dimension of the space into 2b equally filled cells, where b is an user defined amount of bits per dimension. Each cell is labeled with a unique bit string, being the concatenation of the corresponding bit strings for every dimension. For every point, the bit string of the cell is stored, which the point is inserted into. Thus, the VA-File uses two lists: an approximation file that stores the bit string of the cells for every point and a vector file with the vector data for each point. An exemplary space partitioning and the corresponding approximation file can be seen in Figure 3.
Generally, the query algorithm of the VA-File traverses the whole approximation file to collect suitable candidates for the query result at first. After that, exact comparisons between the vector data of the candidates and the query are performed.
The approximation technique of the VA-File helps to
reduce hard-disk accesses, because small bit strings can be
kept in main memory. Even if the whole approximation
file does not fit into the main memory, the sequential
examination of the approximations reduces disk access costs
compared to random accesses to many data items [
Typical representatives for an approximation-based index
structure are based on hash schemes. Apart from common
hashing algorithms, scattering inserted data points over the
amount of buckets is not applicable for similarity queries.
Consequently, there is a need for hash functions, causing
collisions when hashing locally near situated points. This
challenge is handled by Locality Sensitive Hashing (LSH).
The aim of LSH is to map the key to a one dimensional
hash value. Thus, all comparisons are made on the hash
value instead of a high dimensional key. Supporting nearest
neighbor queries, LSH uses (P 1, P 2, r, cr)-sensitive functions
h to compute the hash value. These functions h have to fulfill
the following constraints [
For every dataset in a d-dimensional space p, q ∈ Rd: 1. if ||p − q|| ≤ r, then P r[h(p) = h(q)] > P 1 2. if ||p − q|| ≥ cr, then P r[h(p) = h(q)] < P 2 The first constraint demands that the probability for two points to be hashed into the same bucket has to be larger than P 1 if their distance is smaller than r. Whereas, if their distance is bigger than cr, the probability should be smaller than P 2. In order to be an useful locality sensitive function, P 1 should be much bigger than P 2.
Improving the precision of the index structure, usually several hash tables with different hash functions are used. Consequently, the need for (P 1, P 2, r, cr)-sensitive functions is obvious. A promising family of hash functions is used in p-stable LSH. p-stable LSH.
The approach of p-stable LSH is based on p-stable distributions. A distribution D is p-stable for p ≥ 0 if for any n the real numbers v1, ..., vn and i.i.d. random variables X1, ..., Xn with distribution D, the following constraint is fulfilled: n X(viXi) ∼ i=1 n X(kvikp) i=1 1/p
X,
∼ means the operands have the same distribution and X is
a random variable from the distribution D [
Using d random variables from D to form a d-dimensional
Vector ~a, the scalar of vector ~a and the data point ~v result in
d 1/p
a random variable with distribution P (kvikp) X [
Instead of estimating a distance metric, the scalar product with vectors from p-stable distributions can be used to compute hash values of the data points, because the scalar product maps the vectors to a one dimensional space. Furthermore, the result of the scalar product has the same distribution as the Lp distance metric, which guarantees the (P 1, P 2, r, cr)-sensitiveness.
After giving a short introduction to general challenges of indexing multi-dimensional data, in this section we provide existing challenges of evaluating the performance of index structures for a specific use case. For giving an overview of possible challenges when evaluating index structures, we group the challenges into three groups. 3.1
Parameter of the Index Structures
Some index structures have specific parameters for tuning their performance. Thus, when evaluating the performance of index structures, these parameter have to be considered as well. For index structures given in Section 2.4, these parameter are: the minimum and the maximum number of points within a MBR for the R-Tree, the number of slices a pyramid is divided in, for the Pyramid Technique, and the length of the bit vector for the VA-File. The parameters of the approximation-based index structure p-stable LSH presented in Section 2.4 are number of hash functions and width of hash buckets.
Thus, we have to assume, that these parameters have an impact on the performance of index structures. Therefore, it is necessary to analyze suitable parameter values when trying to identify an appropriate index structure for a given use case. However, there are some problems considering an appropriate value of some parameters. For example, the vectors used for p-stable LSH are randomly chosen from pstable distributions. As a result of this random component it is possible that the performance and precision results of the same index structure created with different seeds of the random component can differ very much, within the same use case. This is problematic when trying to quantitatively evaluate the index structure. 3.2
Workload and used Queries
Although, two different applications can deal with the
same data, they can have a different workload. For that
reason, they can differ in requirements of index structures.
The workload of an application depends on the used query
types. Yet, it is obvious, not to use the Pyramid Technique
presented from Berchtold et al. [
For defining the workload of a database system we use
a definition inspired by Ahmad et al. [
In addition to use cases and workload, the test environment has an impact on the performance of each index structure. As already mentioned, the VA-File is optimized for database systems, storing data items on a disk and not in main memory. Evaluations of VA-File and sequential scan, result in different conclusions according to an evaluation with an in-memory database or a database storing items on the disk. Consequently, it is necessary to consider the underlying storage management of the database system as well.
Beside the storage management of a database, the amount of main memory and the CPU performance are other impact factors to the performance.
TOWARDS A FRAMEWORK
Since we aim at providing a comprehensive library of use cases and suitable indexes, we motivate a framework to give users the possibility to evaluate own use cases with different index structures. In this paper, we summarize key aspects of a framework that supports four groups. In Figure 4, we give an overview of these four groups.
First, the framework has to be extensible w.r.t. four key aspect, we present in Section 2. In other words, for an user, it has to be possible to implement, integrate, and evaluate own index structures. Furthermore, it has to be possible to extend the framework and existing index structures with additional distance metrics and also other query types. Finally, it has to be possible to integrate existing data in the framework and to create data with specific properties like a
USER
FRAMEWORK
workload
visualization
test environment
simulator
extensibility
specific data distribution. Thus, creating data distributions
is not trivial, an interface has to be created for importing
existing data sets and communicating with systems like R,
see for instance [
Adaptability to Different Workload
In real world applications, the workload differs quite much. On the one hand, there are use cases that use only read transactions. On the other hand, the workload can consist of read and write transactions. Thus, the performance results of workloads can differ very much. Hence, an interface is needed for importing workloads from existing systems. A further requirement, is to support standardized benchmarks, e.g. the TPC-H Benchmark2.
Beside the queries used, the desired precision of the query results have to be defined by the user. Thus, if approximate results are allowed, the user has to define the accuracy of the results. Nevertheless, the precision depends on the data properties, the given distance metric, the used queries and the parameters of the index structure as well. 4.3
Existing index structures are created with respect to different optimization criteria. As already mentioned, the VAFile is optimized for reducing disk accesses. Consequently, another criteria our framework has to consider is the environment the tests are located in. Thus, within the framework a parameter has to exist, for setting whether the test is for an in-memory database or if a disk access is needed for accessing the data. Due to an assumption, that the access time of data differs very much considering Hard-Disk-Drives and Solid-State-Disks, the framework should have a component for virtualizing the disk access. With this component it is possible to perform tests on one system while simulating an access delay of another system. In addition to this storage device simulator, a simulator for all hardware components is required to give an useful hint about the best performing index structure.
Additionally, within the framework a parameter has to exist for defining the values of some index structure parameters such as the maximum number of data items of leaves of the R-Tree. 4.4
Visualization
In case the index structure has to struggle with a specific data distribution or query type, it can be useful to visualize the space partitioning of the index structure. With this visualization, further hypothesis can be drawn on the benefits 2http://www.tpc.org/tpch/ or pit-falls of the chosen index structure. For instance, the user is able to follow the split of MBRs in the R-Tree and can easily identify overlapping regions while the tree is being constructed. Another aspect, being worth to visualize, is a statistic on query performance. These statistics help to analyze the performance of different index structures for a given workload or an index structure under different workloads. Apart form the query performance, other interesting values may be worth visualizing. The time spent on constructing the index structure is important for systems with many delete and update queries, because a reconstruction of the index is sometimes necessary when a certain threshold of changed data is reached. Furthermore, when using an approximate index structure, the precision of executed queries and the overall precision of the index structure is worth visualizing, because it has an impact on the suitability of an index structure for a special use case.
Working with the Framework
Finally, our framework shall help finding the most suitable index structures for a given use case. For this, the expected workload has to be known. These parameters include supported query types, exact or approximate results, data dimensionality and distribution, amount of data, the delay of the data access, and the environment. By finding suitable index structures for the given parameters, there are index structures that do not have to be taken into account, because they do not support certain query types or work approximately although the result is restricted to be exact. After excluding unsuitable index structures, the remaining index structures are evaluated under the given workload. By reviewing the performance results, the user can choose the suitable index structure for her use case.
RELATED WORK
In the last decades, many new index structures are
created [
For giving a comparison of the performance of
multi-dimensional index structures, there already exists some
frameworks, like the GiST 3 framework or the MESSIF [
CONCLUSION
In this paper, we provide an overview of existing challenges in finding an appropriate index for multi-dimensional data for a specific use case. First, we explain distance metrics and common query types that have to be considered. Second, the parameters of the index structures can have an impact on the performance of an index structure. Third, for users, it has to be possible to define own workload pattern and the environment, the application is located in.
For supporting these characteristics of real-world use cases we present requirements of a framework we intend to develope. Our framework has to support four key aspects. Namely, it has to be extensible, support different workload patterns, virtualize different use case environments, and contain a visualization component for improving user experiences.
ACKNOWLEDGMENTS
The work in this paper has been funded in part by the German Federal Ministry of Education and Science (BMBF) through the Research Programme under Contract No. FKZ:13N10817 and FKZ:13N10818. Additionally we want to thank Sandro Schulze for giving us useful comments.
dimensio informatics GmbH Brückenstraße 4 09111 Chemnitz alad@dimensio-informatics.de
dimensio informatics GmbH Brückenstraße 4 09111 Chemnitz lese@dimensio-informatics.de
Technische Universität
Chemnitz Straße der Nationen 62
09107 Chemnitz
benn@cs.tu-chemnitz.de
Keywords
Datenbankenerweiterung, Indizierung, Transparent
ZUSAMMENFASSUNG
Aktuelle Datenbanksysteme bieten dem Nutzer eine
enorme Funktionsvielfalt [
Allen gemein ist eine gewisse Abhängigkeit der Implementation vom Datenbankhersteller und einer damit verbundenen schlechten Portabilität der entwickelten Module. Besonders im Bereich der Indizierung um den es in diesem Papier gehen soll, stellen sich aber noch weitere Probleme dar.
Normalerweise kann ein Index auf einer beliebigen Tabelle und deren Spalten definiert werden. Die Anwendung bemerkt nur insoweit etwas von dieser Aktion, als dass Anfragen schneller beantwortet werden sollten.
Ein kleines Beispiel soll dies verdeutlichen. Die folgende Anfrage gibt alle Mitarbeiterinformationen zurück, die zu Mitarbeitern mit mehr als 1000 Euro Gehalt gehören: Listing 1: SQL-Anfrage mit Bedingung im WHERE-Teil SELECT ∗ FROM mitarb
WHERE mitarb.gehalt > 1000 Für die Anwendung, die diese Anfrage an die Datenbank stellt, ist es vollkommen unerheblich, ob sich auf der Gehaltsspalte der Mitarbeitertabelle ein Index befindet oder nicht. Die Anfrage würde, ob nun mit oder ohne Index, immer gleich aussehen.
Wir nehmen nun an, dass die Gehaltsspalte durch einen anderen Typ ersetzt werden soll, Gründe hierfür könnten eine ezffiientere Speicherung oder bessere Zugrisffmöglichkeiten sein. Wir nehmen weiter an, dass das Datenbanksystem für den neuen Typ den >-Operator nicht mehr anbietet. Es muss nun eine Vergleichsfunktion geschrieben werden, die die Aufgabe des >-Operators übernimmt. Diese tiefgreifende Umstrukturierung scheint nun bis in die Anfrage durch, ist also nicht mehr transparent: Listing 2: SQL-Anfrage mit Anfrage an eine nutzerdefinierte Funktion im WHERE-Teil
SELECT ∗ FROM mitarb
WHERE pruefe( mitarb.gehalt, 1000) = 1 Eine Anwendung, die der Nutzer nicht verändern kann, würde also von diesem neuen Typ ausschließlich dann profitieren, wenn der Hersteller diese Möglichkeit vorsieht oder standardmäßig einbaut. Für bestehende Umgebungen ist all dies also keine Option.
Im obigen Fall würde noch die Möglichkeit des
automatischen SQL-Umschreibens einen Ausweg bieten [
Im Folgenden werden wir eine Möglichkeit aufzeigen, wie es ohne einen Eingriff – weder bei der Anwendung noch bei der Datenbank – möglich ist, einen Index weitestgehend transparent in ein bestehendes System zu integrieren. Dazu wird zunächst untersucht, an welchen Stellen und wie in die Kommunikation von Anwendung und Datenbanksystem eingegrieffn werden kann. Anschließend wird auf die Herausforderungen eingegangen, die sich bei dem hier genutzten Ansatz zeigen und wie diese gelöst werden können. 2. INTEGRATIONSPUNKTE 2.1
Überblick Um mögliche Integrationspunkte zu finden, muss zunächst untersucht werden, wie eine Anwendung mit einem Datenbanksystem kommuniziert. Üblicherweise werden hierfür Datenbanktreiber eingesetzt. Das sind Programmbibliotheken, die die Anfragen in ein dem Datenbanksystem verständliches Protokoll überführen und dieses dann übermitteln. Der Datenbankserver dekodiert das Protokoll und arbeitet die darin enthaltenen Anweisungen ab. Abbildung 1: Schematische Darstellung des Zusammenspiels zwischen Anwendung und Datenbank. Die Anwendung verwendet ein API für einen Datenbanktreiber, welcher vom Datenbankhersteller zur Verfügung gestellt wird. Dieser Treiber ist dann für die Kommunikation mit dem Datenbanksystem über ein Netzwerk verantwortlich.
Das beschriebene Szenario – abgebildet in Abbildung 1 – offenbart drei Möglichkeiten, eine Integration vorzunehmen: • den Datenbanktreiber, • die Kommunikation über das Netzwerk und • das Datenbanksystem selbst.
Im Folgenden werden wir uns auf den Datenbanktreiber,
also die Anwendungsseite, konzentrieren. Die Vorgehensweise
bei der Integration in die Kommuniktion ist bereits in [
Datenbanktreiber
Der Datenbanktreiber ist die Schnittstelle für einen
Anwendungsprogrammierer, um mit dem Datenbanksystem zu
kommunizieren. Er stellt Funktionen bereit, um
Verbindungen zu verwalten und Datenbankanfragen abzuarbeiten (sei
es nun SQL oder irgendeine andere Art der Anfrage) [
Connection conn = DriverManager.getConnection( "jdbc:mysql://localhost/testdb", "username", "password"); Statement ps = conn.prepareStatement( "SELECT ∗ FROM mitarb
WHERE gehalt > ?"); ps. setInt (1, 1000); ResultSet rs = ps.executeQuery(); String name = rs.getString("name"); ps. close () ; conn.close () ;
Wie nun stellt sich hier eine Möglichkeit zur Integration dar? Es ist möglich, vor jede Funktion, die eine Anwendung vom originalen Datenbanktreiber aufruft, eine eigene Funktion zu setzen. Die Anwendung ruft nun die eigene Funktion, ohne dies zu bemerken, und die eigene Funktion ruft schließlich die originale. Da nun alle Daten, die von einer Anwendung zum Datenbanksystem gesendet werden, vorher analysiert und verändert werden können, stellt sich so dieser Integrationspunkt dar. Außerdem können eigene Funktionen auf der so abgefangenen Datenbankverbindung „huckepack“ aufgesetzt werden.
Ein erster Gedanke, dies zu realisieren, könnte in die
Richtung einer DLL-Injection [
Technisch ist zur Integration von Cardigo nichts weiter
nötig, als ein geänderter Verbindungsparameter für die
Anwendung. Dieser bewirkt, dass anstelle des originalen
JDBCTreibers nun Cardigo geladen wird. Der Aufbau dieser
veränderten Umgebung ist in Abbildung 2 verdeutlicht.
Abbildung 2: Anwendung, die Cardigo durch einen
veränderten Kommunikationsparameter nutzt. Der
Code, den ein Nutzer schreibt, umfasst
typischerweise nicht den gesamten API-Umfang von JDBC,
weshalb er hier nicht über die gesamte Breite
dargestellt ist. Exemplarisch sind die in Listing 3
verwendeten Methoden dargestellt.
3. INTEGRATION
Bevor wir die Integration des Index weiter betrachten,
wollen wir kurz darauf eingehen, wie ein in ein
Datenbanksystem integrierter Index arbeitet: Wird eine Anfrage an die
Datenbank gestellt und treffen einige der verwendeten
Attribute die im Index enthaltenen, so wird der Index
verwendet. Dabei wird die Anfrage vom Index bearbeitet und im
Ergebnis entsteht einen Liste von Ergebniskandidaten.
Diese können in Form von RowIDs [
Im Folgenden wird zunächst die logische Integration betrachtet, d. h., wie es überhaupt möglich ist, Ergebnisse eines Index an das Datenbanksystem zu übertragen. Es schließt sich eine Betrachtung an, die die programmtechnische Integration betrachtet, da sich hier noch einige weitere Probleme auftun. Die Grundidee der Integration ist es nun, die Anfrage, die eine Anwendung absetzt, so zu verändern, dass sie das Verhalten eines datenbankinternen Index nachahmt. Die Anfrage aus Listing 1 könnte nun, wie in Listing 4 aufgezeigt, um das Primärschlüsselattribut erweitert werden.
Listing 4: SQL-Anfrage, die um die Ergebnisse eines externen Index erweitert wurde
SELECT ∗ FROM mitarb WHERE gehalt > 2000
AND id IN (4, 18)
Dieses Vorgehen vertraut darauf, dass der Optimierer des Datenbanksystems erkennt, dass es sich bei den Werten in der IN-Klausel um Primärschlüssel handelt. Er muss diese möglichst am Anfang der Anfrageverarbeitung einbeziehen, um die Menge der zu untersuchenden Tupel zu minimieren.
Durch Tests haben wir herausgefunden, dass die Anzahl
der in IN-Listen enthaltenen Elemente eine Obergrenze hat.
Durch die Disjunktion mehrerer IN-Listen kann diese zu
einem gewissen Grad ausgeglichen werden. Somit ist es
möglich, sehr lange Anfragen zu erzeugen, Allerdings gibt es auch
eine Grenze für die maximale, vom Datenbanksystem
zugelassene, Anfragelänge. Bei IBM DB2 und Oracle ist diese
Maximallänge bspw. 64kB [
Ein weiterer Aspekt, der bei diesen langen Anfragen betrachtet werden muss, ist, dass diese vom Datenbanksystem auch geparst werden. Werden die Anfragen lang, so steigen auch deren Parsezeiten, selbst optimistisch betrachtet ist dieser Zusammenhang linear. Auch systematisch bedingt, ist, dass der Optimierer zu lange und viele IN-Listen nicht beachtet, selbst wenn es sich um Primärschlüssel handelt. Mit Hinweisen an den Optimierer kann hier gegengesteuert werden. Zusammenfassend lässt sich aber sagen, dass ab einer gewissen Anfragelänge, der Gewinn durch den Index sich im schlechtesten Falle sogar ins Gegenteil verkehren kann.
Um diese Beschränkungen zu umgehen, können die Ergebnisse des Index auch in eine Tabelle in der Datenbank eingefügt werden. Hier gibt es wieder mehrere Möglichkeiten: 1. Einfügen in eine Tabelle, die angelegt ist 2. Einfügen in eine temporäre Tabelle In beiden Fällen muss allerdings die Datenbank in der Weise modifiziert werden, dass die Anwendung, in die der Index integriert wurde, das Recht hat, auf diese Tabellen zu schreiben. Die Tabellen müssen prinzipiell eine Spalte für die Anfrage und eine Spalte für die Ergebnisse des Index besitzen.
Werden über eine Sitzung Anfragen nur sequenziell bearbeitet, haben temporäre Tabellen den Vorteil, dass zwischen verschiedenen Datenbanksitzungen nicht mittels der eben beschriebenen zusätzlichen AnfrageID-Spalte in dieser Tabelle unterschieden werden muss. Das ist darin begründet, dass temporäre Tabellen für jede Sitzung als leere neue Tabellen erscheinen. Die Aktionen einer Sitzung wirken sich nicht auf den Inhalt der temporären Tabelle in einer anderen Sitzung aus.
Ein bisher nicht zur Sprache gekommener Punkt ist das Aktualisieren des Index. Natürlich muss ein datenbankexterner Index über INSERT-, UPDATE- und DELETE-Operationen informiert werden. Der einfachste Weg ist, wenn alle Operationen, die auf der Datenbank laufen, über die gleiche abgefangene Schnittstelle gehen und so direkt gelesen werden können. In der Realität ist dies jedoch unpraktisch, da diese Voraussetzung nicht zu 100% gewährleistet werden kann. Trigger sind eine Variante, wie Veränderungen in der Datenbank nach außen gereicht werden können, diese müssen jedoch integriert werden dürfen. Hier ergeben sich damit auch Grenzen, über die hinaus unser Ansatz nicht angewendet werden kann. Eine andere Möglichkeit sind statische Datenhaltungen, die nur in definierten Zeitabschnitten aktualisiert werden, bspw. einmal pro Monat. Hier kann ein statischer Index genutzt werden, der über eine simple Zeitsteuerung aktualisiert wird. 3.2 Oft halten sich Anwendungsprogrammierer an die Beispiele der Autoren der jeweiligen Datenbankschnittstelle. Jedoch erlauben alle APIs auch eine freiere Nutzung, d. h., dass die Schrittfolge der Kommandos nicht festgelegt ist und es verschiedene Gründe geben kann, die so aufgezeigten Standardroutinen zu verwerfen. Listing 3 zeigt zunächst einen Standardweg auf. Für diesen wollen wir nun die Schritte, die ein datenbankexterner Index verfolgen kann, aufzeigen: • Statement vorbereiten (conn.prepareStatement(...)): if Anfrage relevant then
Anfrage speichern end if • Variablen binden (ps.setInt(...)): if Anfrage war relevant then
Bindung speichern end if
Beobachtungen an realen Programmen zeigen, dass das Binden von Variablen teils mehrfach auf die gleichen Variablen angewendet wird. Mit dem eben beschriebenen Verfahren ist dies kein Problem. Auch Operationen, die ein Statement näher beschreiben, sind nach wie vor ausführbar, da alle Bestandteile erhalten bleiben und nur Ergänzungen vorgenommen werden.
ERGEBNISSE UND AUSBLICK Das hier beschriebene System war bereits erfolgreich im Einsatz. Die Latenzen für das reine Abfangen der Datenbankaufrufe bewegen sich im einstelligen Mikrosekundenbereich, also dem, was für einen Funktionsaufruf erwartet werden kann. Hinzu kommt die Zeit für die Indexanfrage. Für einen realen Gewinn muss natürlich die Zeit für die Integration, die Indexanfrage und den Einbau der Ergebnisse in das Statement in Summe geringer sein, als die einer Anfrage ohne den externen Index.
Es zeigte sich auch, dass, wird eine Integration über Tabellen angestrebt, es verschiedene Arten gibt, die Ergebnisse aus der Ergebnistabelle zu entfernen. In 3.1 wurden die verschiedenen Arten von Tabellen hierfür beschrieben. Wenn keine Spalte für die AnfrageID verwendet werden muss, so können die Ergebnisse mit einem TRUNCATE entfernt werden. Dieses wird erheblich schneller ausgeführt, als ein DELETE FROM ... WHERE anfrage_id == <current_id>.
Unsere weitere Arbeit beschränkt sich nicht nur auf eine Integration in JDBC, die wir hier aufgezeigt haben, sondern geht auch darüberhinaus auf native Datenbanktreiber ein, die dann jedoch herstellerspezifisch sind. Hier müssen andere Mechanismen angewandt werden, eine Integration elegant zu vollziehen, die Prinzipien bleiben jedoch die gleichen. Auch der bereits vorgestellte Ansatz, einen Proxy zu integrieren, der das Protokoll, welches das Datenbanksystem im Netzwerk verwendet, versteht, wurde weitergeführt und zeigte sich bereits im Einsatz als wertvolle Hilfe. Das oben bereits erwähnte Cardigo dient uns dabei als Werkzeugkasten, der alle diese Möglichkeiten vereint.
LITERATUR
example and in detail, IBM Developer works DB2
library. Dec. 2003.
[
com/p/jdbcgrabber/.
[
Otto-von-Guericke University
Magdeburg bress@iti.cs.uni-magdeburg.de
Otto-von-Guericke University
Magdeburg siba.mohammad@st.ovgu.de
Otto-von-Guericke University
Magdeburg eike@iti.cs.uni-magdeburg.de A current research trend focuses on accelerating database operations with the help of GPUs (Graphics Processing Units). Since GPU algorithms are not necessarily faster than their CPU counterparts, it is important to use them only if they outperform their CPU counterparts. In this paper, we address this problem by constructing a decision model for a framework that is able to distribute database operations response time minimal on CPUs and GPUs. Furthermore, we discuss necessary quality measures for evaluating our model. 1. INTRODUCTION
In the context of database tuning, there are many
different approaches for performance optimization. A new
opportunity for optimization was introduced with General
Purpose Computation on Graphics Processing Units (GPGPU)
[
CPUs are optimized for a low response time, meaning
that they execute one task as fast as possible. The GPU
is optimized for high throughput, meaning they execute as
many tasks as possible in a fixed time. This is
accomplished by massively parallel execution of programs by using
multi threading. Furthermore, GPUs specialize on
computeintensive tasks, which is typical for graphics applications.
Additionally, tasks with much control flow decrease
performance on GPUs, but can be handled well by CPUs [
A new research trend focuses on speeding up database
operations by performing them on GPUs [
He et al. present the concept and implementation of
relational joins on GPUs [
We assume that an operation is executed through an algorithm which uses either CPU or GPU. For which operations and data is it efficient to execute database operations on a GPU? A GPU algorithm can be faster or slower as its CPU counterpart. Therefore, the GPU should be used in a meaningful way to achieve maximal performance. That means, only if it is to be expected that the GPU algorithm is faster it should be executed.
We do not know a priori which processing device (CPU or GPU) is faster for which datasets in a given hardware configuration. We have to take different requirements into account to determine the fastest processing device: • the operation to be executed, • the size of the dataset to process, • the processing power of CPU and GPU (number of processor cores, clock rate), and • the current load condition on CPU and GPU.
The following contributions are discussed in the following: 1. A response time minimal distribution of database operations on CPUs and GPUs can achieve shorter execution times for operations and speedup query executions. Hence, a basic idea how such a model can be constructed is depicted in this paper. 2. For the evaluation of our model, we define appropriate quality measures.
To the best of our knowledge, there is no self-tuning decision model that can distribute database operations response time minimal on CPUs and GPUs.
The remainder of the paper is structured as follows. In Section 2, we present our decision model. Then, we discuss model quality metrics needed for evaluation in Section 3. Section 4 provides background about related work. Finally, we present our conclusion and future work.
In this section, we present our decision model. At first, we discuss the basic model. Then, we explain details of the estimation and the decision components. 2.1
Basic Model
We construct a model that is able to choose the response time minimal algorithm from a set of algorithms for processing a dataset D. We store observations of past algorithm executions and use statistical methods to interpolate future execution times. We choose the algorithm with the smallest estimated execution time for processing a dataset.
Definitions: Let O be a database operation and let APO = {A1, .., Am} be an algorithm pool for operation O, i.e., a set of algorithms that is available for the execution of O. We assume that every algorithm has different performance characteristics. Hence, the execution times of different algorithms needed to process a dataset D are likely to vary. A data set D provides characteristic features of the input data. In this paper, we consider only the data size. Other characteristics, e.g., data distribution or data types will be considered in future work.
Let TA(D) be the execution time of an algorithm to process the dataset D. We do not consider hardware specific parameters like clock rate and number of processor cores to estimate execution times. Instead, we learn the execution behavior of every algorithm. For this purpose, we assign to every algorithm A a learning method LA and a corresponding approximation function FA(D). Let Test(A, D)=FA(D) be an estimated execution time of algorithm A for a dataset D. A measured execution time is referred to as Treal(A, D). Let a measurement pair (MP) be a tuple (D,Treal(A, D)). Let M P LA be a measurement pair list, containing all current measurement pairs of algorithm A.
Statistical Methods: We consider the following
statistical methods for the approximation of the execution
behavior of all algorithms. The first one is the least squares
method and the second is spline interpolation with cubic
splines [
Abstraction: The execution time of algorithms is highly dependent on specific parameters of the given processing hardware. In practice, it is problematic to manage all parameters, so maintenance would become even more costly. Hence, we do not consider hardware specific parameters and let the model learn the execution behavior of algorithms using statistical method LA and the corresponding approximation function FA(D).
Model Components: The model is composed of three components. The first is the algorithm pool APO which contains all available algorithm of an operation O. The second is the estimation component which computes execution time estimations for every algorithm of an operation. The third part is the decision component which chooses the algorithm that fits best for the specified optimization criteria. Depending on whether the chosen algorithm uses the CPU or the GPU, the corresponding operation is executed on the CPU or the GPU. In this paper, we only consider response time optimization. However, other optimization criteria like throughput can be added in future work. Figure 1 summarizes the model structure. 2.2
This section describes the functionality of the estimation component. First, we discuss when the approximation functions of the algorithms should be updated. Second, we examine how the model can adapt to load changes. 2.2.1
Updating the Approximation Functions
For an operation O that will be applied on a dataset D the estimation component computes for each available algorithm of O an estimated execution time. For this, we need an approximation function that can be used to compute estimations. Since we learn such functions with statistical methods, we need a number of observations for each algorithm to compute the corresponding approximation functions. After we computed an initial function for each algorithm, our model is used to make decisions. Hence, the model operation can be divided into two phases. The first is the initial training phase. The second is the operational phase.
Since the load condition can change over time, execution times of algorithms are likely to change as well. Hence, the model should provide a mechanism for an adoption to load changes. Therefore, the model continuously collects measurement pairs of all executed algorithms of an operation.
There are two problems to solve: 1. Re-computation Problem: find a strategy when to re-compute the approximation function for each algorithm, so that a good trade-off between accuracy and overhead is achieved. 2. Cleanup Problem: delete outdated measurements pairs from a measurement pair list because the consideration of measurement pairs from past load conditions is likely to be less beneficial for estimation accuracy. Furthermore, every measurement pair needs storage space and results in higher processing time for the statistical methods.
There are different heuristics that deal with the
re-computation of approximation functions. Zhang et al. present
possible approaches in [
A1,
A2,..., algorithm pool An CPU GPU dataset D optimization criterion Test(A1,D),
Test(A2,D),..., estimation component Test(An,D) MPLA1 ... MPLAi ... MPLAn
MP=(D,Treal(Ai)) decision component
Ai
As Zhang et al. point out, the most aggressive method is unlikely to achieve good results because the expected overhead for re-computing the approximation function counteracts possible performance gains. Hence, we have to choose between approach 2 and 3. There is no guarantee that one approach causes less overhead than the other.
On one hand, periodic re-computation causes a predictable overhead, but it may re-compute approximation functions when it is not necessary, e.g., the relative estimation error is still beneath an error threshold. On the other hand, an event based approach re-computes the approximation functions only if it is necessary, but has the disadvantage, that the quality of estimations has to decrease until the approximation functions are re-computed. We choose the periodic approach, because of it’s predictable overhead. We will consider the event based approach in future work.
Parameters: Now we discuss necessary parameters of the model. Let RCR be the re-computation rate of an algorithm. That means that after RCR measurement pairs were added to the measurement pair list of an algorithm A, the approximation function FA(D) of A is re-computed.1 Hence, the used time measure is the number of added measurement pairs. Let ITL be the initial training length, which is the number of measurement pairs that have to be collected for each algorithm, before the model switches into its operational phase.
Now we address the Cleanup Problem. We have to limit the number of measurement pairs in the measurement pair list to keep space and computation requirements low. Furthermore, we want to delete old measurement pairs from the list that do not contribute to our current estimation problem sufficiently. These requirements are fulfilled by a ring buffer data structure. Let RBS be the ring buffer size in number of measurement pairs. If a new measurement pair is added to a full ring buffer, it overrides the oldest measurement pair. Hence, the usage of a ring buffer solves the Cleanup Problem. RCR and RBS are related because if RCR is greater than RBS there would be measurement pairs that are never considered for computing the approximation functions. Hence, RCR should be smaller than RBS .
Statistical Methods: The used statistical methods have
to be computationally efficient when computing
approximation functions and estimation values. Additionally, they
should provide good estimations (relative estimation error
<10%). Since the times needed to compute estimations
sums up over time, we consider a method computationally
efficient if it can compute one estimation value in less than
50μs. Our experiments with the ALGLIB [
Self Tuning Cycle: The model performs the following self tuning cycle during the operational phase: 1. Use approximation functions to compute execution time estimations for all algorithms in the algorithm pool of operation O for the dataset D. 2. Select the algorithm with the minimal estimated response time. 3. Execute the selected algorithm and measure its execution time. Add the new measurement pair to the measurement pair list M P LA of the executed algorithm A. 4. If the new measurement pair is the RCR new pair in the list, then the approximation function of the corresponding algorithm will be re-computed using the assigned statistical method.
Adaption to Load Changes
This section focuses on the adaption to load changes of the model. We start with necessary assumptions, then proceed with the discussion how the model can adapt to new load conditions.
Let ACP U be a CPU algorithm and AGP U a GPU algorithm for the same operation O.
The basic assumptions are: 1. Every algorithm is executed on a regular basis, even in overload conditions. That ensures a continuing supply of new measurement pairs. If this assumption holds then a gradual adaption of the approximation functions to a changed load condition is possible. 2. A change in the load condition has to last a certain amount of time, otherwise the model cannot adapt and delivers more vague execution time estimations. If this assumption does not hold, it is not possible to continuously deliver good estimations. 3. The load condition of CPU and GPU are not related.
As long as the assumptions are fulfilled, the estimated execution time curves2 approach the real execution time curves if the load changes. Increase and decrease of the load condition on the side of the CPU is symmetric compared to an equivalent change on the side of the GPU. For simplicity, but without the loss of generality, we discuss the load adaption mechanism for the CPU side. 2An execution time curve is the graphical representation of all execution times an algorithm needs to process all datasets in a workload.
Treal(AGPU,D) Treal(ACPU,D) Test (ACPU,D) e m i t n o i t u c e x e
Treal(AGPU,D) Treal(ACPU,D) Test (ACPU,D) data size data size
Increasing Load Condition: If the load condition increases on the side of the CPU then the execution times of CPU algorithms increase and the real execution time curves are shifted upwards. In contrast, the estimated execution time curves stay as they are. We illustrate this situation in Figure 2. The model is adapted to the new load condition by collecting new measurement pairs and recomputing the approximation function. This will shift the estimated execution time curve in the direction of the measured execution time curve. Hence, the estimations become more precise. After at maximum RCR newly added measurement pairs for one algorithm the estimated execution time curve approaches the real execution time curve. This implies the assumption that a re-computation of approximation functions never has a negative impact on the estimation accuracy.
Decreasing Load Condition: The case of a decreasing load is mostly symmetric to the case of increased load. A decreased load on CPU side causes shorter execution time of CPU algorithms. The consequence is that real execution time curves are shifted downwards, whereas the estimated execution time curves stay as they are.
Limits of the Adaption: There is the possibility that the described load adaption scheme can break, if the load on CPU side increases or decreases too much. We consider the case, where the load increases too much, the other case is symmetric. In Figure 3, we illustrate the former case. Hence, the real execution time curve of ACP U lies above the real execution time curve of AGP U .
If this state continues to reside a certain amount of time, the estimated execution time curves will approach the real execution time curves. If the load condition normalizes again, then only algorithm AGP U is executed, regardless of datasets that can be faster processed by algorithm ACP U . The model is now stuck in an erroneous state since it cannot make response time minimal decisions for operation O anymore.
However, this cannot happen due to the assumption that every algorithm is executed on a regular basis, even in overload conditions. Hence, a continuing supply of new measurement pairs is ensured which allows the adaption of the model to the current load condition. 2.3
In this section, we describe the decision component of our model. Due to limited space, we introduce only one optimization criterion, namely response time, but other criteria like throughput are possible. 2.3.1
If we optimize the operation execution for response time, we want to select the algorithm with the minimal execution time for the dataset D. In choosing the algorithm with the minimal execution time, we distribute the operation response time minimal to CPU and GPU. There is always one decision per operation that considers the size of the dataset that has to be processed.
Definition: Let a workload W be a tuple W = (DS, O), where DS = D1, D2, · · · , Dn is a set of datasets Di that are to be processed and O the operation to be executed.3
Goal: The goal is to choose the fastest algorithm Aj ∈ APO for every dataset Di ∈ DS for the execution of operation O.
min =
X Treal(Ak, Di) with Ak ∈ APO
Di∈DS
Usage: The algorithm with the minimal estimated execution time for the dataset D is chosen for execution. The function choose Algorithm (choose Alg) chooses an algorithm according to the optimization criterion.
choose Alg(D, O) = Aj with
Test(Aj, D) = min({Test(Ak, D)|∀Ak ∈ APO})
It is expected that the accuracy of the estimated execution times has a large impact on the decisions and the model quality.
Practical Use: The execution of the fastest algorithm reduces the response time of the system and results in better performance of a DBS. These response time optimization is necessary to accelerate time critical tasks4. Furthermore, it 3For simplicity, we only consider one operation per workload. However, a set of operations is more realistic and can be added in future work. 4A task is an operation in execution. is possible to automatically fine-tune algorithm selection on a specific hardware configuration.
MODEL QUALITY CRITERIA
In this section, we present four model quality measures, namely average percentage estimation error, hit rate, model quality, and percentage speed increase.
The idea of the average percentage estimation error is to
compute the estimation error for each executed algorithm
and the corresponding estimation value. Then, the
absolute percentage estimation error is computed. Finally, the
average of all computed percentage estimation errors is
computed. This measure is also called relative error and is used,
e.g., in [
The idea of this measure is to compute the ratio of the number of correct decisions and the total number of decisions. A decision is correct, if and only if the model decided for the fastest algorithm. In the ideal case all decisions are correct, so the hit rate is 100%. In the worst case all decisions are wrong. Hence, the hit rate is 0%. The benefit of the hit rate is that it can provide statistical information about how many decisions are wrong. If the hit rate is X then every 1/(1-X) decision is incorrect. However, we cannot quantify the impact of an incorrect decision. This is addressed by the model quality. Note, that algorithms with very similar execution time curves can lead to a bad hit rate, although the overall performance is acceptable.
The idea of the model quality is to compute the ratio of the resulting execution times that a system using an ideal model and a real model needs to process a workload W . In the ideal case, the real model would be as good as the ideal model. Hence, the model quality is 100%. The worst case model would always select the slowest algorithm and provides a lower bound for the model quality.
Let TDM (W ) be the time a system using a decision model (DM ) needs to process a workload W . It is computed out of the sum of all algorithm execution times resulting from the algorithm selection of the decision model for the workload added with the overhead caused by DM . Let TOh(DM, W ) be the overhead the decision model DM causes. If a decision model introduces to much overhead, it can eliminate their gain. Hence the overhead has to be considered, which is the sum of the total time needed for computing estimation values and the total time needed to re-compute approximation functions. The time needed for all estimation value computation (EVC) for a workload W is TEVC(W ). The time needed to re-compute the approximation functions of all algorithms is TRC (W ). Both measures are highly dependent on DM . Hence, we get the following formulas:
TOh(DM, W ) = TEVC(W ) + TRC (W )
X Treal(choose AlgDM (D, O), D) (4) + TOh(DM, W )
Let DMideal be the ideal decision model and let DMreal be the real decision model. Then, the model quality MQ is defined as:
M Q(W, DMreal) = TDMideal (W )
TDMreal (W )
This measure describes to which degree the optimization goal described in formula 1 is achieved. Note, that the ideal model is not introducing overhead (TOh(DMideal, W ) = 0). 3.4
The idea of the percentage speed increase (PSI) is to quantify the performance gain, if a decision model DMi is replaced with a decision model DMj.
P SI(DMi → DMj, W ) =
TDMi (W ) − TDMj (W )
TDMi (W ) If P SI(DMi → DMj, W ) is greater than zero, DMj had a better performance than DMi and vice versa.
RELATED WORK
In this section, we present the related work. We consider analytical models for estimating execution times of GPU algorithms. Furthermore, we discuss learning based approaches to estimate execution times. Finally, we present existing decision models and provide a comparison to our approach.
Analytical Models Hong et al. present an analytical
model which estimates execution times of massively parallel
programs [
Zhang et al. develop a model that should help optimizing
GPU programs by arranging qualitative performance
analyses [
Learning based Execution Time Estimation Akdere
et al. investigate modeling techniques for analytical
workloads [
Matsunaga et al. present a short overview over machine
learning algorithms and their fields of application [
Zhang et al. present a model for predicting the costs of
complex XML queries [
Decision Models Kerr et al. present a model that
predicts the performance of similar application classes for
different processors [
Iverson et al. develop an approach that estimates
execution times of tasks in the context of distributed systems [
CONCLUSION
In this paper, we addressed a current research problem, namely the optimal distribution of database operations on hybrid CPU/GPU platforms. Furthermore, we develop a self-tuning decision model that is able to distribute database operations on CPUs and GPUs in a response time minimal manner. We discuss the basic structure of the model and provide a qualitative argumentation of how the model works. Additionally, we present suitable model quality measures, which are required to evaluate our model. Our experiments show that our model is almost as good as the ideal model if the model parameters are set appropriately. We omit the evaluation due to limited space. We conclude that distributing database operations on CPUs and GPUs has a large optimization potential. We believe our model is a further step to address this issue.
In ongoing research, we use the defined quality measures to evaluate our model on suitable use cases. A further possible extension is using the model in a more general context, where response-time optimal decisions have to be made, e.g., an optimal index usage. Furthermore, an extension of the model from operations to queries is necessary for better applicability of our model. This leads to the problem of hybrid query plan optimization.
REFERENCES