Τα τετραδικά δένδρα δευτερεύουσας μνήμης ως μηχανισμοί δεικτοδότησης σε γεωγραφικά συστήματα πληροφοριών και συστήματα χωρικών βάσεων δεδομένων

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). Παρουσιάζεται το πειραματικό μέρος αυτής της εργασίας και συγκρίνονται οι αποδόσεις των δυο δομών βάσει των αποτελεσμάτων των πειραμάτων που εκτελέστηκαν σε όλους τους τύπους των ερωτημάτων.