Υλοποίηση παραλλαγών διαμέρισης k-D δένδρων για δομές δεικτοδότησης πολυδιάστατων δεδομένων

Abstract

Στον τομέα της πληροφορικής, οι αλγόριθμοι και δομές δεδομένων αποτελούν ιδιαιτέρα χρήσιμα εργαλεία για την αντιμετώπιση πολυδιάστατων και δυσκολονόητων προβλημάτων. Γενικότερα, μπορούμε να ορίσουμε τις δομές δεδομένων ως διαδικασίες εισαγωγής και απομάκρυνσης στοιχείων με τρόπο ώστε όλη η δομή να μην αλλοιώνεται. Στα πλαίσια της παρούσας πτυχιακής αναλύσαμε διεξοδικά την δομή δεδομένων Κ-D tree, η οποία ορίζεται ως μια δομή που οργανώνει την πρόσβαση σε ένα πλήθος σημείων του ν-διάστατου χώρου έτσι ώστε αυτή να γίνεται σε logN χρόνο όπου Ν το πλήθος των σημείων. Το δέντρο Κ-D είναι μια πολύ χρήσιμη δομή δεδομένων για διάφορες εφαρμογές, όπως έρευνες που αφορούν την αναζήτηση εύρους και την αλγοριθμική αναζήτηση του πλησιέστερου γείτονα. Τέλος, οι εφαρμογές, στις οποίες χρησιμοποιείται το δέντρο Κ-D είναι πάρα πολλές με σημαντικότερες την επεξεργασία εικόνας, την αναγνώριση μοτίβου, την ανάκτηση δεδομένων και τους προσομοιωτές πτήσης.

In the field of information technology, algorithms and data structures are particularly useful tools for dealing with multidimensional and difficult problems. More generally, we can define data structures as import procedures and removing data in a way that the entire structure is not altered. In the context of this thesis we analyzed in detail the data structure K -D tree, which is defined as a structure that organizes access to a number of points of n - dimensional space so that it becomes in time logN where N is the number of points. The K -D tree is a very useful data structure for various applications, such as investigations concerning the range search and algorithmic search for the nearest neighbor. Finally, applications which use the K -D tree is too many with important image processing, pattern recognition, data recovery and flight simulators.