Δόμηση σημειακών δεδομένων και επεξεργασία χωρικών ερωτημάτων

Abstract

The aim of the present thesis was to develop and study an improved version of the structure xBR-tree named xBR+-tree in the section of spatial data structuring. This index would have to be capable of organizing, querying and storing small and big spatial data. Construction methods (one-by-one insertion and bulk loading) and a deletion algorithm were developed. The xBR+-tree was compared experimentally with xBR-tree and popular R-trees in both types of spatial queries with one or two input data sets. We proposed two enhancements on algorithms using classic plain sweep for join queries (kCPQ, εDJQ) with two input spatial data sets stored in main memory. One new algorithm (Reverse Run Plain Sweep - RRPS) was developed in order to improve the query processing of that type of queries executed on data stored in main memory beforehand or partial loading. The experimental results showed that the algorithm RRPS always reduces the distance calculations, therefore accelerates the execution time. In the field of spatial query processing, on data stored in main memory, existing methods were studied and new ones were proposed in order to solve the k Group Nearest Neighbor problem. Finally, new algorithms were proposed using a combination of the plane sweep technique and space partitioning for kCPQ and εDJQ without utilizing any spatial indexing method over data sets stored in the secondary memory and studied. The new algorithms proved efficient. The best of the new algorithms proved more efficient in comparison to the best algorithm using the spatial structure R-tree.

Σκοπός της διατριβής στον τομέα των μεθόδων δόμησης σημειακών δεδομένων πολύ μεγάλου όγκου ήταν η βελτίωση της δομής του δενδρικού χωρικού ευρετηρίου xBR-tree με μία νέα δομή (xBR+-tree). Αναπτύχθηκαν μέθοδοι κατασκευής του νέου ευρετηρίου με εισαγωγή μεμονωμένων και μαζική εισαγωγή δεδομένων και μέθοδος διαγραφής δεδομένων από τα xBR-tree. Μελετήθηκαν τα αποτελέσματα πειραμάτων σύγκρισης του xBR+-tree με το xBR-tree και με R-trees στη λειτουργία δόμησης και στην επεξεργασία χωρικών ερωτημάτων επί ενός ή δύο συνόλων δεδομένων. Προτάθηκαν επεκτάσεις των αλγορίθμων κλασικής τεχνικής σάρωσης επιπέδου για ερωτήματα σύζευξης δύο χωρικών συνόλων αποθηκευμένων στην κύρια μνήμη kCPQ και εDJQ με δύο προτάσεις βελτίωσης. Παρουσιάστηκε ένας νέος αλγόριθμος (Αντίρροπης Κίνησης Αλγόριθμος Σάρωσης – RRPS) για τη βελτίωση της επεξεργασίας των ερωτημάτων αυτών τόσο με δεδομένα εξολοκλήρου στην κύρια μνήμη ή επί τμημάτων των συνόλων δεδομένων που ανεβαίνουν επιλεκτικά στην κύρια μνήμη. Τα αποτελέσματα των πειραμάτων οδήγησαν στο συμπέρασμα ότι ο αλγόριθμος RRPS πάντοτε περιορίζει τους υπολογισμούς απόστασης άρα επιταχύνει χρονικά την εκτέλεση. Στο πεδίο των ερωτημάτων χωρικής σύζευξης με δεδομένα στην κύρια μνήμη μελετήθηκαν υπάρχοντες και προτάθηκαν νέοι αλγόριθμοι επίλυσης των k ομαδικών εγγύτερων γειτόνων. Τέλος, παρουσιάστηκαν και μελετήθηκαν νέοι αλγόριθμοι που χρησιμοποιούν ένα συνδυασμό τεχνικής σάρωσης και διαμέρισης του χώρου για τη σύζευξη των δεδομένων για ερωτήματα kCPQ και εDJQ, χωρίς τη χρήση κάποιου ευρετηρίου, με δεδομένα αποθηκευμένα στον δίσκο. Απεδείχθη ότι οι αλγόριθμοι RRPS είναι αποδοτικότεροι στα ανωτέρω ερωτήματα από τους κλασικής τεχνικής σάρωσης. Ο καλύτερος από τους νέους αλγόριθμους συγκρινόμενος πειραματικά με τον καλύτερο αλγόριθμο που χρησιμοποιεί τη χωρική δομή δεικτοδότησης R-tree αναδείχθηκε ως αποδοτικότερος.