Studienarbeit STUD-2264

Bibliograph.
Daten
Schembera, Björn: Implementierung und Evaluation mehrdimensionaler Bereichsanfragen mittels raumfüllender Kurven.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Studienarbeit Nr. 2264 (2010).
84 Seiten, deutsch.
CR-Klassif.C.2.4 (Distributed Systems)
E.1 (Data Structures)
H.2.4 (Database Management Systems)
H.3 (Information Storage and Retrieval)
Kurzfassung

Abstract Die vorliegende Arbeit beschäftigt sich mit der Realisierung von mehrdimensionalen Bereichsanfragen in strukturierten Peer-to-Peer-Netzen. Bei diesen Systemen handelt es sich um Netzwerke, deren Teile sich gleichberechtigt gegenüberstehen – das System organisiert sich insofern selbst, dass es keinen zentralen Koordinator gibt. Diese Netzwerke dienen zum Bereitstellen von Ressourcen wie Speicherplatz, CPU-Zeit usw., welche entsprechend verwaltet werden müssen. Zum Zugriff auf Ressourcen muss eine Zuordnung von Merkmalen eines Datenelements (ein „Attribut“) zum Aufenthaltsort des Datenelements bekannt sein. Viele Peer-to-Peer-Systeme, wie beispielsweise Chord, unterstützen nativ nur Punktanfragen über einem Attribut. In der Praxis sollen Daten mit mehreren Attributen versehen werden dürfen, um einen Datenbestand hinreichend zu modellieren. Um dieser Problemstellung beizukommen, werden raumfüllende Kurven genutzt, deren mathematische Eigenschaften es erlauben, mehrere Attribute auf eines abzubilden und dabei die Nachbarschaftsbeziehungen zu erhalten. Dadurch werden Bereichsanfragen möglich, indem einfach ein kontingentes Kurvenstück einem gesuchten, zusammenhängenden Bereich im Attributraum entspricht. Im Rahmen der Studienarbeit wurden die Hilbert-, die Peano-und die Z-Kurve implementiert und evaluiert. Grundsätzlich bietet die Hilbert-Kurve die besten Eigenschaften im Bezug auf Erhaltung der Datenlokalität – jedoch ist ihr Berechnungsaufwand hoch, der sich vor allem bei Bereichsanfragen akkumuliert. Daher wird eine Optimierung für einen bereits bestehenden Algorithmus für Bereichsanfragen mit der Hilbert-Kurve durchgeführt sowie eine API vorgeschlagen, die die Benutzung von raumfüllenden Kurven zur Datenindizierung vereinfachen soll. Die Studienarbeit hat zum Ergebnis, dass die Hilbert-Kurve auch wegen der niedrigen Berechnungszeit vor allem in der optimierten Variante den anderen vorzuziehen ist.

Volltext und
andere Links
PDF (1612070 Bytes)
Zugriff auf studentische Arbeiten aufgrund vorherrschender Datenschutzbestimmungen nur innerhalb der Fakultät möglich
Abteilung(en)Universität Stuttgart, Institut für Parallele und Verteilte Systeme, Verteilte Systeme
BetreuerMemon, Faraz
Eingabedatum18. November 2010
   Publ. Abteilung   Publ. Institut   Publ. Informatik