Not logged in.

Quick Search - Contribution

Contribution Details

Type Bachelor's Thesis
Scope Discipline-based scholarship
Title Implementing a disk-resident spatial index structure (Quadtree)
Organization Unit
Authors
  • Freddy Panakkal
Supervisors
  • Michael Hanspeter Böhlen
  • Georgios Garmpis
Language
  • English
Institution University of Zurich
Faculty Faculty of Business, Economics and Informatics
Date 2016
Abstract Text In the last decades more and more systems are dealing with multi-dimensional data. An example for such a system are the geographic information systems (GIS), like Google Maps or PostGIS, that store, manipulate and analyze geographic data. It is the task of the underlying database to deal with such huge amount of geographic information. One way to deal with multi-dimensional data is by using a tree data structure like the quadtree. A quadtree works similar to a binary tree but it is designed for two-dimensional data. This thesis discusses the implementation of a disk-resident quadtree and analyzes the efficiency of a quadtree. For this purpose, a buffer manager has been implemented and a quadtree on top of it. By performing different experiments, good and bad scenarios of using a quadtree and a buffer manager are demonstrated.
Zusammenfassung In den letzten Jahrzehnten entstanden immer mehr Systeme, welche mit mehrdimensionalen Daten arbeiten. Geoinformationssysteme (GIS), wie Google Maps oder PostGIS, sind Beispiele für solche Systeme, mit welchen geographische Daten erfasst, bearbeitet und analysiert werden. Eine Anforderung an solche Systeme ist die effiziente Handhabung riesiger Mengen mehrdimensionaler Daten. Eine Möglichkeit mehrdimensionaler Daten strukturiert abzulegen ist mittels einer Baumstruktur, wie einem Quadtree. Quadtrees funktionieren ähnlich wie Binärbäume, jedoch mit zweidimensionalen Schlüsseln. Diese Arbeit befasst sich mit der plattenresidenten Implementierung eines Quadtrees und der Analyse der Performance. Zu diesem Zweck wurde zuerst ein Buffer Manager implementiert und aufbauend auf diesem der Quadtree. Durch verschiedene Experimente werden sowohl gute als auch schlechte Szenarien dieser Implementierung aufgezeigt.
PDF File Download
Export BibTeX