Student Thesis STUD-2264

BibliographySchembera, Björn: Implementierung und Evaluation mehrdimensionaler Bereichsanfragen mittels raumfüllender Kurven.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Student Thesis No. 2264 (2010).
84 pages, german.
CR-SchemaC.2.4 (Distributed Systems)
E.1 (Data Structures)
H.2.4 (Database Management Systems)
H.3 (Information Storage and Retrieval)
Abstract

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.

Full text and
other links
PDF (1612070 Bytes)
Access to students' publications restricted to the faculty due to current privacy regulations
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Superviser(s)Memon, Faraz
Entry dateNovember 18, 2010
   Publ. Computer Science