| dc.description.abstract | Η εργασία που ακολουθεί έχει ως αντικείμενο τη μελέτη μεθόδων δεικτοποίησης των Δεδομένων Χωρικού Τύπου. Επέιδή έχουν αναπτυχθεί πάρα πολλές τέτοιες μέθοδοι η μελέτη περιορίστηκε σε δυο: το xBR-δένδρο και το R* δένδρο, τα οποία επιλέχθηκαν διότι το πρώτο είναι ένα μέλος της οικογένειας των τετραδικών δένδρων με χαρακτηριστικά πο το κάνουν ιδανικό να κατοικεί στη δευτερεύουσα μνήμη και ως εκ τούτου να διαχειρίχεται χωρικά δεδομένα πολύ μεγάλου όγκου, ενώ το δεύτερο είναι ίσως η πιο δημοφιλής βελτιωμένη ρκδοχής της οικογένειας των R-δένδρων, τα οποία βασίζονται στην αποσύνθεση του χώρου Ελάχιστα Περιγεγραμμένα Ορθογώνια και στη συνέχεια στην οργάνωση αυτών σε ομάδες μεγαλυτέρων που τα περιβάλλουν κ.ο.κ. Και αυτό το δένδρο είναι απ'αρχής σχεδιασμένο να εδρεύει στη δευτερεύουσα μνήμη.Το R* δένδρο έχει καταπληκτικές επιδόσεις σε ερωτήσεις Χωρικού Τύπου όπως είναι τα ερωτήματα περιοχής ή τα ερωτήματα πλησιέστερου γείτονα με ή χωρίς περιορισμό απόστασης.Αναπτύσσονται οι βασικοί αλγόριθμοι αποτίμησης ερωτημάτων επί των Χωρικών Βάσεων Δεδομένων. Οι αλγόριθμοι για το R* δένδρο είναι ήδη πολυσυζητημένοι και έχουν τύχει μεγάλης έρευνας από πάρα πολλούς ερευνητές. Από το στάδιο αυτό (της θεωρητικής περιγραφής) διαφαίνονται ομοιότητες ως προς ττον τρόπο διαχείρισης των δεδομένων. Διαφορές οι οποίες αποτελούν συγκριτικά πλεονεκτήματα του xBR δένδρου διαπιστώνονται, αλλά και μειονεκτήματα κάνουν την εμφάνισή τους. Ας πούμε το xBR δένδρο χαρτογραφεί το χώρο με σαφή προτίμηση στο μεγαλύτερο δυνατό μέγεθος των τμημάτων στα οποία τον διαιρεί ενώ το R* δένδρο σε όσο το δυνατόν μικρότερα ορθογώνια τα οποία περιγράφουν ποσότητες δεδομένων. Αυτό μας κάνει να ανμένουμε απο το xBR-δένδρο να είναι ταχύτερο στη διαδικάσια κατασκευής της βάσης αποτίμησης ερωτημάτων αναζήτησης θέσης, αλλά το R* δένδρο να είναι αποτελεσματικότερο στην αποτίμηση ερωτημάτων περιοχής ή γειτνίασης. Κάθε δομή υποβλήθηκε σε ένα πλήθος ερωτημάτων και μετρήθηκε η απόδοση της σε αριθμό σελίδων (κόμβων) που χρειαζόταν να ανασύρει απο τη δευτερύουσα μνήμη αλλά και σε πραγματικό χρόνο που δαπανούσε μέχρι να φτάσει στην απάντηση. Το πρόγραμμα των ερωτημάτων είχε μια οργάνωση τέτοια ώστε να προσπαθήσει να ανιχνεύσει τις επιδόσεις σε οποιδήποτε σημείο ή οποιαδήποτε γειτονιά του χώρου που κάλυπταν τα δεδομένα της καθεμιάς απο τις 25 βάσεις δεδομένων που κατασκευάσαμε.Επίσης προσπαθήσαμε να εντοπίσουμε κάτω απο ποιές συνθήκες είναι αποτελεσματικότερη η κάθε δομή. Τα αποτελέσματα έδειξαν ότι στη διαδικασία δημιουργίαε της βάσης και στον αριθμό των προσπελάσεων στα ερωτήματα αναζήτησης θέσης το xBR δένδρο υπερτερεί. Ενώ στις προσπελάσεις της δευτερεύουσαν μνήμης για τα ερωτήματα περιοχής και γειτνίασης υπερτερει το R* δένδρο. Στην ταχύτητα απόκρισης στα ίδια ερωτήματα το xBR δένδρο είναι στις περισσότερες περιπτώσεις καλύτερο και γενικά δειχνει να αυξάνει την αποτελεσματικότητα του όσο οι Χωρικές Βάσεις γίνονται μεγαλύτερες. Τέλος περιγράφουμε τη σχεδίαση και υλοποίηση΄ενός διαδικτιακού εργαστηρίου που μπορεί να αποτελέσει ένα γραφικό περιβάλλον για την υποβολή μεμονομένων ερωτημάτων προς τις δομές xBR δένδρο και R* δένδρο, αλλά και οργανωμένων προγραμμάτων ερωτημάτων. Από την εργασία αυτή προέκυψαν οι δημοσιεύσεις: Η πρώτη με τίτλο "Nearest Neighbor Algorithms Using xBR-trees", έγινε δεκτή για πλήρη παρουσίαση και δημοσίευση στα πρακτικά του 15th Panhellenic Conference on Informatics (PCI 2011). Σ'αυτή παρουσιάζονται οι αλγόριθμοι, πρώτα κατλα βάθος (DF) και πρώτα το καλύτερο (BF), των ερωτημάτων γειτνίασης για το xBR δένδρο (Κ -πλησιέστεροι γείτονες με ή χωρίς περιορισμό απόστασης) καθώς και αποτελέσματα που προέκυψαν από την εκτέλεση μιας ολοκληρωμένης σειράς πειραμάτων στα παραπάνω ερωτήματα. Η δεύτερη με τίτλο "Performance Comparison of xBR-treew for single Dataset Spatial Quaries" έγινε δεκτή για πλήρη παρουσίαση και δημοσίευση στα πρακτικά του Fifteeth East-European Conference on Advances in Databases and Information Systems (ADBIS2011). Παρουσιάζεται το πειραματικό μέρος αυτής της εργασίας και συγκρίνονται οι αποδόσεις των δυο δομών βάσει των αποτελεσμάτων των πειραμάτων που εκτελέστηκαν σε όλους τους τύπους των ερωτημάτων. | el_GR |
| dc.description.translatedabstract | In this work we study indexing methods for spatial data. We compare the eXternal Balanced Regular (xBR) tree and the R*-tree, based on the fact that the first spatial access method is a member of the quadtrees family, having features allowing it to live in the secondary memory and therefore to manage very large spatial databases, while the second is the most popular variation of R-trees which organize the space in Minimum Bounding Rectangles (MBR), which are then organized in buckets of MBRs and so on. R*-trees are designed to live in the secondary memory, too, while they have excellent performance in spatial queries, like range queries or nearest neighbor queries with, or without distance constraints.
In the present work, we present the basic algorithms for the evaluation of queries on Spatial Data Bases (SDB). The algorithms for the R*-tree have already been extensively discussed in the literature and extensive research has been presented by many researchers. However, the algorithms for the xBR-tree are presented for the first time in the literature. The similarities in data management between the two methods can be clearly seen, even in these preliminary steps, whereas differences and constructive comparisons are also being discussed. The xBR-tree tends to map the area with a strong preference to the largest possible size of the dividing areas, while the R*-tree uses the smallest possible rectangles that describe the data.
We also present the results of extensive experimentation for comparing the performance of the two structures. During our experiments, each structure is tested under a large number of queries and performance is measured in the aspects of number of pages (nodes) that need to be retrieved from secondary memory and the time spent to reach the answer. The organization of queries aimed at detecting the performance at any point, or any neighborhood in the area covering the data of each of the 25 databases that we built for experimentation. The general conclusions are that the xBR-tree is faster, regarding the construction process and the execution of Point Location Queries, while, regarding the number of read accesses to the secondary memory, the R*-tree excels (on Range Queries and Nearest Neighbor Queries). Regarding the speed of response to the same queries, the xBR-tree is, in many cases, the winner and is highly competitive. Generally the xBR-tree improves its performance as the size of data increases.
Additionally, we describe the design and implementation of an online workshop that serves as a web graphical interface to executing single queries using individual structures, xBR-tree or R*-tree, as well as, to executing projects (groups) of queries.
From this thesis two papers have been raised.
The first paper “Nearest Neighbor Algorithms Using xBR-trees” has been accepted for publication and presentation at 15th Panhellenic Conference on Informatics (PCI 2011). We present the algorithms, Depth First search (DF) and Best First search (BF), for the Nearest Neighbor Queries (NNQ) with or without distance constraints. In the same paper we analyze the results of one large experiment’s project that has been executed.The second one with title ‘Performance Comparison of xBR-trees and R*-trees for Single Dataset Spatial Queries’ has been accepted as a full research paper from Fifteenth East-European Conference on Advances in Databases and Information Systems (ADBIS2011). We present the experimental part of this thesis and compare the efficiencies of two structures xBR-tree and R*-tree based on the results of these experiments. | el_GR |
