1. Home page
  2. Search

Structuring point data and processing spatial queries

This item is provided by the institution :
National Documentation Centre (EKT)   

Repository :
National Archive of PhD Theses  | ΕΚΤ NA.Ph.D.   

see the original item page
in the repository's web site and access all digital files if the item*



Δόμηση σημειακών δεδομένων και επεξεργασία χωρικών ερωτημάτων
Structuring point data and processing spatial queries
Roumelis, George
Ρούμελης, Γεώργιος
PhD Thesis
2017
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 αναδείχθηκε ως αποδοτικότερος.
Φυσικές Επιστήμες ➨ Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
Αξιολόγηση χωρικών ερωτημάτων
Χωρικές βάσεις δεδομένων
Spatial query processing
Spatial query performance evaluation
Επεξεργασία χωρικών ερωτημάτων
Spatial databases
Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
Natural Sciences
Computer and Information Sciences
Spatial access methods
Φυσικές Επιστήμες
Μέθοδοι προσπέλασης χωρικών δεδομένων
Greek
Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης (ΑΠΘ)
Aristotle University Of Thessaloniki (AUTH)
Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης (ΑΠΘ). Σχολή Θετικών Επιστημών. Τμήμα Πληροφορικής
National Documentation Centre (EKT)
National Archive of PhD Theses
Συλλογή ΕΑΔΔ



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)