Parallel query processing on big spatial data
Authors: Βελέντζας Πολυχρόνης 
Published: December 2022

Σήμερα αποθηκεύουμε πολύ μεγάλο όγκο χωρικών δεδομένων. Η συνεχώς αυξανόμενη ανάγκη για επεξεργασία τέτοιων μεγάλων δεδομένων μας οδήγησε να δημιουργήσουμε κατανεμημένα ή παράλληλα συστήματα, για να αντιμετωπίσουμε τα αυξανόμενα υπολογιστικά κόστη. Τέτοια δεδομένα (συχνά ονομάζονται γεωχωρικά δεδομένα), χρησιμοποιούνται σε πολλές γεωγραφικές εφαρμογές. Για την εκμετάλλευση αυτών των δεδομένων, η αποτελεσματική επεξεργασία χωρικών ερωτημάτων είναι μεγάλης σημασίας λόγω της ευρείας γκάμας εφαρμογών όπου μπορούν να χρησιμοποιήσουν αυτά τα ερωτήματα. Τα πιο συνηθισμένα χωρικά ερωτήματα στα οποία εμπλέκονται χωρικά σημεία είναι τα ερωτήματα θέσης σημείου, παραθύρου, απόστασης εμβέλειας και k πλησιέστερου γείτονα (k-NNQs). Σε υψηλότερο επίπεδο, τέτοια ερωτήματα έχουν χρησιμοποιηθεί ως βάση πολλών πολύπλοκων λειτουργιών σε προηγμένες εφαρμογές, για παράδειγμα, συστήματα γεωγραφικών πληροφοριών (GIS), συστήματα που βασίζονται σε τοποθεσία (LBS), γεωγραφικές βάσεις δεδομένων, CAD κ.λπ. Η απόδοση της επεξεργασίας των χωρικών ερωτημάτων συνήθως επηρεάζεται από δύο βασικούς παράγοντες. Ο υπολογιστικός παράγοντας και ο παράγοντας αποθήκευσης. Το πρώτο μπορεί να αντιμετωπιστεί από πολλές αρχιτεκτονικές, για παράδειγμα, μονού πύρηνα (διαδοχική-σειριακή εκτέλεση), πολλαπλών πυρήνων (παράλληλη εκτέλεση), πολλαπλών κόμβων ή ακόμη και μοντέλα επεξεργασίας GPU. Ο δεύτερος παράγοντας έχει επίσης μεγάλη σημασία και επηρεάζει την ανάκτηση ή αποθήκευση πληροφοριών. Η έλευση της non-volative μνήμης (NVM) επέτρεψε μια ολοκαίνουργια κατηγορία συσκευών αποθήκευσης με συναρπαστικά χαρακτηριστικά που θα επικρατήσουν στην αγορά αποθήκευσης στο εγγύς μέλλον. Οι υψηλές ταχύτητες ανάγνωσης και εγγραφής, το μικρό μέγεθος, η χαμηλή κατανάλωση ενέργειας και η αντοχή τους σε κραδασμούς είναι μερικοί από τους λόγους που τα έκαναν δημοφιλή ως μέσο αποθήκευσης. Το NAND flash είναι αναμφίβολα το πιο δημοφιλές NVM σήμερα. Οι συσκευές αποθήκευσης που βασίζονται στο NAND Flash βρίσκονται τόσο σε καταναλωτικές συσκευές όσο και σε εταιρικά κέντρα δεδομένων. Οι αυξανόμενες ανάγκες για αποτελεσματική αποθήκευση οδήγησαν στην εμφάνιση μονάδων δίσκου στερεάς κατάστασης (SSD).Εκτός από το σχεδιασμό και την ανάπτυξη των παραπάνω χωρικών ερωτημάτων, δοκιμάσαμε επιπλέον την αποτελεσματικότητά τους σε Edge Computers. Το Edge computing είναιμια κατανεμημένη υπολογιστική αρχιτεκτονική, όπου ο υπολογισμός και η αποθήκευση δεδομένων είναι όσο το δυνατόν πιο κοντά στην πηγή των δεδομένων. Σχεδιάσαμε επίσης μια κατανεμημένη αρχιτεκτονική υπολογιστών Edge και IoT, όπου περιγράψαμε διεξοδικά τον τρόπο με τον οποίο μπορούμε να εκμεταλλευτούμε τη δυναμική των τεχνικών μας.Σε αυτή τη διατριβή εστιάζουμε στον σχεδιασμό και την υλοποίηση χωρικών ερωτημάτων που εκμεταλλεύονται επεξεργαστές πολλαπλών πυρήνων, GPU και SSD για αποθήκευση. Χρησιμοποιούμε τεχνικές για ταχύτερους και λιγότερους υπολογισμούς, μειώσεις υπολογισμών καθώς και μειώσεις επεξεργασίας δεδομένων, χρησιμοποιώντας χωρική εγγύτητα, διανομή δεδομένων, σε συνθετικά και σε πραγματικά δεδομένα. Με βάση αυτές τις τεχνικές αναπτύσσουμε αποτελεσματικούς αλγόριθμους χωρικών ερωτημάτων χρησιμοποιώντας CPU πολλαπλών πυρήνων, αναπτύσσουμε αποτελεσματικούς αλγόριθμους χωρικών ερωτημάτων χρησιμοποιώντας GPU, εκμεταλλευόμαστε τα τεράστια πλεονεκτήματα I/O των SSD, εφαρμόζουμε αυτά τα ερωτήματα στους Edge Computers, διενεργούμε εκτενείς πειραματικές δοκιμές για να συγκρίνουμε τους αλγόριθμούς μας με άλλους υπάρχοντες χρησιμοποιώντας συνθετικά και πραγματικά χωρικά δεδομένα.