Parallel query processing on big spatial data

Abstract

Nowadays we are storing overwhelming volumes of Spatial data. The continuously growing need for processing such big data has led us create distributed or parallel frameworks, to address the emerging computational overhead. Such data (often termed as geospatial data), are used in many geographically enabled applications. To exploit these data, efficient processing of spatial queries is of great importance due to the wide area of applications that may address such queries. The most common spatial queries where points are involved are point-location, window, distance-range and k nearest-neighbor queries (k-NNQs). At a higher level, such queries have been used as the basis of many complex operations in advanced applications, for example, geographical information systems (GIS), location-based systems (LBS), geometric databases, CAD, etc.The spatial queries processing performance is usually affected by two major factors. The computational and the storage factor. The first one can be addressed by many architectures,for example single core (sequential execution), multi-core (parallel execution), multi-node or even GPU processing models. The second factor is also of great importance and affects the retrieval or storage of information. The advent of non-volatile memories (NVM) has enabled a brand-new class of storage devices with exciting features that will prevail in the storage market in the near future. Their high read and write speeds, small size, low power consumption and shock resistance are some of the reasons that made them storage medium of choice.NAND flash is undoubtedly the most popular NVM today. Storage devices based on NAND Flash are found both in consumer devices and enterprise data-centers.The increasing needs for efficient storage drove the emergence of Solid-State Drives (SSDs). Aside from the design and development of the above spatial queries, we furthermore tested their efficiency in Edge Computers. Edge computing is a distributed computing architecture where computation and data storage is as close to the source of data as possible. We also designed an Edge computing and IoT distributed architecture, where we described thoroughly the way we can exploit the dynamics of our techniques.In this thesis we focus on the design and implementation of spatial queries that take advantage of multi-core CPU, GPU and SSD for storage. We employ techniques for faster and fewer computations, computation reductions as well as data processing reductions, using spatial locality and data distribution, on either synthetic or real data. Based on these techniques we develop efficient spatial query algorithms using multi-core CPU, we develop efficient spatial query algorithms using GPU, we exploit the massive I/O advantages of SSDs, we apply these queries to Edge Computers, we perform extensive experimental tests to compare our algorithms to other existing ones using synthetic and real spatial data.

Σήμερα αποθηκεύουμε πολύ μεγάλο όγκο χωρικών δεδομένων. Η συνεχώς αυξανόμενη ανάγκη για επεξεργασία τέτοιων μεγάλων δεδομένων μας οδήγησε να δημιουργήσουμε κατανεμημένα ή παράλληλα συστήματα, για να αντιμετωπίσουμε τα αυξανόμενα υπολογιστικά κόστη. Τέτοια δεδομένα (συχνά ονομάζονται γεωχωρικά δεδομένα), χρησιμοποιούνται σε πολλές γεωγραφικές εφαρμογές. Για την εκμετάλλευση αυτών των δεδομένων, η αποτελεσματική επεξεργασία χωρικών ερωτημάτων είναι μεγάλης σημασίας λόγω της ευρείας γκάμας εφαρμογών όπου μπορούν να χρησιμοποιήσουν αυτά τα ερωτήματα. Τα πιο συνηθισμένα χωρικά ερωτήματα στα οποία εμπλέκονται χωρικά σημεία είναι τα ερωτήματα θέσης σημείου, παραθύρου, απόστασης εμβέλειας και 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, διενεργούμε εκτενείς πειραματικές δοκιμές για να συγκρίνουμε τους αλγόριθμούς μας με άλλους υπάρχοντες χρησιμοποιώντας συνθετικά και πραγματικά χωρικά δεδομένα.