Προσεγγιστική καταμέτρηση περιοχής
| dc.contributor.advisor | Πλατής, Νίκος | |
| dc.contributor.author | Τσίρμπα, Κωνσταντίνα Σ. | |
| dc.date.accessioned | 2013-11-19T09:30:34Z | |
| dc.date.available | 2013-11-19T09:30:34Z | |
| dc.date.issued | 2013-04 | |
| dc.identifier.uri | http://amitos.library.uop.gr/xmlui/handle/123456789/979 | |
| dc.description | Μ.Δ.Ε. 32 | el |
| dc.description.abstract | Η παρούσα εργασία πραγματεύεται την προσεγγιστική καταμέτρηση και αναζήτηση περιοχής (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 ερωτήματα σε οποιαδήποτε σταθερή διάσταση. Επιπλέον, παρουσιάζουμε μια μέθοδο που μειώνει τόσο τον χώρο όσο και τον χρόνο στα ερωτήματα πλησιέστερου γείτονα. Τέλος, ερευνούμε τα ερωτήματα αναζήτησης ε-ΝΝ με περιορισμένο βάρος και παρουσιάζουμε ένα βασικό θεώρημα. | el |
| dc.format.extent | 72 σελ. | el |
| dc.language.iso | el | el |
| dc.publisher | Πανεπιστήμιο Πελοποννήσου | el |
| dc.rights | Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/gr/ | * |
| dc.subject | Γεωμετρία -- Πληροφορική | el |
| dc.title | Προσεγγιστική καταμέτρηση περιοχής | el |
| dc.type | Μεταπτυχιακή διπλωματική εργασία | el |
| dc.contributor.department | Τμήμα Επιστήμης και Τεχνολογίας Υπολογιστών | el |
| dc.contributor.faculty | Σχολή Θετικών Επιστημών και Τεχνολογίας | el |
| dc.contributor.master | Επιστήμη και Τεχνολογία Υπολογιστών | el |
| dc.subject.keyword | Υπολογιστική γεωμετρία | el |
| dc.subject.keyword | Αναζήτηση περιοχής | el |
| dc.subject.keyword | Range trees | el |
| dc.subject.keyword | k-d Trees | el |
| dc.subject.keyword | Προσεγγιστική αναζήτηση περιοχής | el |
| dc.subject.keyword | Πλησιέστεροι γείτονες | el |
| dc.description.abstracttranslated | 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. | el |
Αρχεία σε αυτό το τεκμήριο
Αυτό το τεκμήριο εμφανίζεται στις ακόλουθες συλλογές
Εκτός από όπου επισημαίνεται κάτι διαφορετικό, το τεκμήριο διανέμεται με την ακόλουθη άδεια:
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα