Τεχνικές παράλληλης επεξεργασίας στον αλγόριθμο k-d tree

Abstract

Ο k-d tree είναι μια δενδρική δομή που οργανώνει την πρόσβαση σε ένα πλήθος σημείων του ν-διάστατου χώρου έτσι ώστε αυτή να γίνεται σε logN χρόνο όπου Ν το πλήθος των σημείων. Μπορεί να αποτελέσει μια πολυδιάστατη εκδοχή δυαδικού δένδρου. Η κατασκευή του k-d tree ξεκινά, βρίσκοντας πρώτα ποιά από τις διαστάσεις (ποιός άξονας) έχει το μεγαλύτερο εύρος (δηλαδή τη μεγαλύτερη διαφορά μεταξύ του μέγιστου και του ελάχιστου) και ορίζεται ως άξονας αποκοπής. Έτσι για να βρούμε μια καλή κατεύθυνση για το διαχωρισμό (split), υπολογίζουμε τη διακύμανση των σημείων δεδομένων κατά μήκος κάθε άξονα χωριστά, επιλέγουμε τον άξονα με τη μεγαλύτερη διακύμανση, και δημιουργούμε ένα υπερεπίπεδο προς διάσπαση κάθετο σ' αυτό. Για να βρούμε ένα καλό σημείο διαχωρισμού για το υπερεπίπεδο, εντοπίζουμε την διάμεσο (median) κατά μήκος του εν λόγω άξονα και επιλέγουμε το αντίστοιχο σημείο. Αυτό παράγει ένα καλά ισορροπημένο δέντρο. Για την εύρεση της διαμέσου γίνεται ταξινόμηση κατά μήκος αυτού του άξονα στα σημεία ή εκτελείται ένας γρήγορος αλγόριθμος QuickSelect. Ακολουθεί ο διαχωρισμός των δεδομένων σε δύο υποσύνολα. Όταν ο αριθμός των σημείων δεδομένων που περιέχονται σε κάθε κόμβο είναι μικρότερος ή ίσος αυτών που αρχικά καθορίσαμε, η διαδικασία σταματά. Συνήθως ο αριθμός αυτός είναι ένα σημείο σε κάθε φύλλο. Σκοπός της διπλωματικής αυτής είναι η υλοποίηση του αλγορίθμου αυτού και η εύρεση του κοντινότερου γείτονα με την τεχνική του παράλληλου προγραμματισμού χρησιμοποιώντας το λογισμικό Matlab. Όπως, επίσης και η μελέτη της απόδοσης της παράλληλης και σειριακής εκδοχής του εναλλάσσοντας των αριθμό των πυρήνων και των διαστάσεων σε γνωστά σύνολα δεδομένων.

K-d tree is a tree structure that organizes access to a number of points of n-dimensional space so that it is done in logN time where N is the number of points. It can be a multidimensional version of a binary tree. The construction of the k-d tree begins, finding first which of the dimensions (which axis) has the widest range (i.e., the greatest difference between the maximum and the minimum) and is defined as the cut-off axis. So in order to find a good direction for splitting, we calculate the fluctuation of the data points along each axis individually, select the axis with the greatest variance, and we create a super-level to split vertically into it. To find a good separation point for the hyperplane, we locate the median along that axis and select the corresponding point. This produces a well-balanced tree. To find the middle one sorts along this axis in points or runs a quick QuickSelect algorithm. The following is the separation of the data into two subsets. When the number of data points contained in each node is less than or equal to those originally set, the process stops. Usually this number is a point on each sheet. The aim of this diploma is to implement this algorithm and to find the closest neighbor with the parallel programming technique using the Matlab software. As well as studying the performance of the parallel and serial version of alternating the number of cores and dimensions in known datasets.