Προσεγγιστική καταμέτρηση περιοχής
Θεματική επικεφαλίδα
Γεωμετρία -- ΠληροφορικήΛέξεις κλειδιά
Υπολογιστική γεωμετρία ; Αναζήτηση περιοχής ; Range trees ; k-d Trees ; Προσεγγιστική αναζήτηση περιοχής ; Πλησιέστεροι γείτονεςΠερίληψη
Η παρούσα εργασία πραγματεύεται την προσεγγιστική καταμέτρηση και αναζήτηση περιοχής (approximate range counting - searching) η οποία συγκαταλέγεται στα κυριότερα προβλήματα της υπολογιστικής γεωμετρίας.
Στο 1ο κεφάλαιο γίνεται μια εισαγωγή στις έννοιες της υπολογιστικής γεωμετρίας για την καλύτερη κατανόηση του επιστημονικού χώρου. Δίδονται παραδείγματα εφαρμογής της στο σύγχρονο κόσμο και εξηγούνται οι βασικές έννοιες των δομών για ερωτήσεις περιοχής (range searching).
Στο 2ο κεφάλαιο παρουσιάζεται το πρόβλημα αναζήτησης περιοχής. Για την καλύτερη κατανόηση του προβλήματος παρουσιάζουμε συγκεκριμένες δεντρικές δομές δεδομένων, Range Trees και k-d Trees.
Στο 3ο κεφάλαιο αναλύεται το Balanced Box-Decomposition δέντρο (BBD-Tree) και η σημασία του για την επίλυση του παραπάνω προβλήματος. Επιπλέον, αναλύεται η δυναμική δομή δεδομένων «quadtreap», η οποία χρησιμοποιείται για την αποθήκευση πολυδιάστατων συνόλων από σημεία. Παρατίθεται, τέλος, και ο αλγόριθμος για την απάντηση ερωτημάτων προσεγγιστικής καταμέτρησης περιοχής χρησιμοποιώντας τη δομή quadtreap.
Στο 4o κεφάλαιο ερευνούμε τα ε-ΝΝ ερωτήματα πλησιέστερου γείτονα (nearest neighbor queries) στο πεδίο των παράλληλων τμημάτων. Παρουσιάζουμε μια δομή δεδομένων που απαντά σε χρονικά-εξαρτώμενα ε-NN ερωτήματα σε οποιαδήποτε σταθερή διάσταση. Επιπλέον, παρουσιάζουμε μια μέθοδο που μειώνει τόσο τον χώρο όσο και τον χρόνο στα ερωτήματα πλησιέστερου γείτονα. Τέλος, ερευνούμε τα ερωτήματα αναζήτησης ε-ΝΝ με περιορισμένο βάρος και παρουσιάζουμε ένα βασικό θεώρημα.
Περίληψη
The present thesis deals with approximate range counting and searching, which constitutes one of the main problems of computational geometry.
The first chapter introduces the concepts of computational geometry aiming at a better understanding of the relevant scientific sector. It provides examples of its application in the modern world, as well as further insights into the basic concepts of the structures of range searching queries.
The second chapter goes on to present the range searching problem. We present specific tree data structures (Range Trees and k-d Trees) to better understand the problem.
The third chapter analyzes the Balanced Box-Decomposition Tree (BBD-Tree) and its contribution to solving the above problem. Moreover, we analyze the dynamic “quadtreap” data structure, which is used to store multi-dimensional sets of points. This chapter ends with the presentation of an algorithm for answering approximate range counting queries using the quadtreap structure.
The fourth chapter investigates the nearest neighbor queries in the field of parallel sections. It presents a data structure that responds to time-dependent e-NN queries in any fixed dimension. A method is also introduced that reduces both the time and space of the nearest neighbor queries. Finally, the chapter explores the e-NN search queries with limited weight and ends up with a basic theorem.
Αριθμός σελίδων
72 σελ.Σχολή
Σχολή Θετικών Επιστημών και ΤεχνολογίαςΑκαδημαϊκό Τμήμα
Τμήμα Επιστήμης και Τεχνολογίας ΥπολογιστώνΤίτλος Προγράμματος Μεταπτυχιακών Σπουδών
Επιστήμη και Τεχνολογία ΥπολογιστώνΓλώσσα
ΕλληνικάΠεριγραφή
Μ.Δ.Ε. 32Οι παρακάτω άδειες σχετίζονται με αυτό το τεκμήριο:
Εκτός από όπου επισημαίνεται κάτι διαφορετικό, το τεκμήριο διανέμεται με την ακόλουθη άδεια:
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα