Algorithms and indexing structures for spatial big data

Abstract

Ζούμε στην εποχή των μεγάλων δεδομένων, όπου παράγονται ετερογενή δεδομένα τα οποία αποθηκεύονται με εκθετικό ρυθμό. Τα παραδοσιακά συστήματα διαχείρισης δεδομένων δεν είναι ικανά να συλλέγουν, να διαχειρίζονται και να επεξεργάζονται τα μεγάλα δεδομένα μέσα σε ανεκτά χρονικά πλαίσια. Σημαντικό μέρος των μεγάλων δεδομένων είναι τα χωρικά μεγάλα δεδομένα (Spatial Big Data - SBD), τα οποία αντιπροσωπεύουν γεωγραφικές δομές δεδομένων που υπερβαίνουν και πάλι την ικανότητα των παραδοσιακών χωρικών υπολογιστικών συστημάτων λόγω του όγκου, της ποικιλίας και της ταχύτητας των δεδομένων. Τα SBD φέρνουν πολλές νέες προκλήσεις για νέες αρχιτεκτονικές διαχείρισης SBD. Συγκεκριμένα, οι πιο πρόσφατες δουλειές χρησιμοποιούν κατανεμημένα περιβάλλοντα για την υλοποίηση χωρικών τελεστών όπως, kNN, συνένωσης, αθροίσματος και επιλογής πάνω από τις αρχιτεκτονικές μεγάλων δεδομένων. Επιπρόσθετα, αρκετές από τις προηγούμενες λύσεις χρησιμοποιούν τεχνικές κατανεμημένης ευρετηρίασης για την ενίσχυση της διαδικασίας αποθήκευσης και της εκτέλεσης των χωρικών τελεστών. Δυστυχώς, οι προτεινόμενες αρχιτεκτονικές είναι αγνωστικές ως προς τις δυνατότητες επεξεργασίας και αποθήκευσης του συστήματος και δεν καταφέρνουν να διατηρήσουν τη βελτιστοποιημένη απόδοση αποθήκευσης και να ικανοποιήσουν τις απαιτήσεις για αναλυτικά και επιχειρησιακά ερωτήματα σε πραγματικό χρόνο. Σε αυτή τη διδακτορική διατριβή παρουσιάζουμε αλγόριθμους και δομές δεδομένων που επιλύουν σημαντικές προκλήσεις των SBD, ειδικότερα σε ότι αφορά τον χρόνο απόκρισης σε επερωτήσεις και την αποδοτικότητα αποθήκευσης δεδομένων. Οι ερευνητικές συνεισφορές της διατριβής πλαισιώνονται μέσα σε μια νέα αρχιτεκτονική η οποία βασίζεται στην απόδοση, με ονομασία SPATE+, όπου η αποθήκευση, η ευρετηρίαση, η επεξεργασία επερωτήσεων και τα συστατικά της εφαρμογής μπορούν να επιτύχουν καλύτερη απόδοση από τις εξελίξεις αιχμής. Η αρχιτεκτονική SPATE+ χρησιμοποιεί συμπιεσμένα δεδομένα χωρίς απώλεια της αρχικής πληροφορίας για να αποθηκεύσει τα πρόσφατα ρεύματα SBD με τον πιο συμπαγή τρόπο, διατηρώντας τη δυνατότητα για πλήρη ανάλυση των δεδομένων. Το SPATE+ εξασφαλίζει την προοδευτική απώλεια της λεπτομέρειας των δεδομένων, που ονομάζεται φθορά δεδομένων, καθώς τα δεδομένα γερνούν με το χρόνο. Συγκεκριμένα, παρουσιάζουμε ένα νέο καινοτόμο τελεστή φθοράς για Μεγάλα Τηλεπικοινωνιακά Δεδομένα (TBD), με ονομασία TBD-DP (Επίρρηση Δεδομένων). Ο τελεστής TBD-DP βασίζεται σε γνωστούς αλγόριθμους μηχανικής μάθησης για να γενικεύσει τα TBD σε συμπαγή μοντέλα τα οποία μπορούν να αποθηκευτούν και να επερωτηθούν όταν είναι απαραίτητο. Η αρχιτεκτονική SPATE+ είναι εννοιολογικά χωρισμένη σε τρία επίπεδα: (i) αποθήκευση και ευρετηρίαση, όπου επιτυγχάνεται υψηλή απόδοση αποθήκευσης χρησιμοποιώντας τα συστατικά στοιχεία συμπίεσης και αποσύνθεσης. Αυτή η κατηγορία περιλαμβάνει επίσης ένα χωροχρονικό ευρετήριο με τέσσερα επίπεδα χρονικών αναλύσεων που ελαχιστοποιούν το χρόνο απόκρισης για ερωτήματα αναζήτησης δεδομένων. (ii) τελεστές, όπου ένας τελεστής ερωτημάτων AkNN υψηλής απόδοσης υπερβαίνει τις τελευταίες τεχνικές από την άποψη της αποτελεσματικής κατανομής, αντιγραφής και διύλισης δεδομένων. (iii) εφαρμογές, όπου ένα αποτελεσματικό πλαίσιο εξερεύνησης ερωτημάτων, με ονομασία SPATE, παρέχει νέες λειτουργίες εξερεύνησης δεδομένων στο χρήστη. Επιπλέον, μια ανώνυμη εφαρμογή ανταλλαγής μηνυμάτων, με ονομασία Rayzit, χρησιμοποιεί SBD για να συνδέσει άμεσα τους χρήστες με τους πλησιέστερους γείτονες (kNN) καθώς κινούνται στον χώρο για να εκθέσει τις συνεισφορές των συστατικών που είναι μέρος της αρχιτεκτονικής SPATE+.

We live in the big data era where heterogeneous data is produced and stored at an exponential rate. Recently, many solutions have emerged to handle big data for which traditional data management systems are not capable to capture, manage, and process the data within a tolerable elapsed time. A significant portion of big data is Spatial Big Data (SBD), which represents massive geographic objects that again exceed the capability of traditional spatial computing systems due to volume, variety and velocity characteristics. SBD brings many new challenges for novel SBD management architectures. Particularly, recent works are utilizing distributed environments to implement spatial operators like kNN, Joins, Aggregations and Selections on top of big data architectures. Additionally, several of the previous solutions are using distributed indexing techniques to enhance the storing process and the spatial operators. Unfortunately, the proposed architectures are agnostic of underline processing and storage capabilities failing to maintain optimized storage efficiency and satisfy the requirements for online analytical and operational queries. In this PhD thesis we present algorithms and indexing structures that tackle critical challenges brought forward by SBD, namely query response time and storage efficiency. We frame our research contributions in the context of a novel performance-driven architecture, named SPATE+, where the storage, indexing, query processing and application components of the architecture can achieve better utilization and efficiency than the state-of-the-art. SPATE+ uses lossless data compression to ingest recent streams of SBD in the most compact manner retaining full resolution for data exploration tasks. More importantly, it takes care of the progressive loss of detail in information, called v decaying, as data ages with time. Particularly, we present a novel decaying operator for Telco Big Data (TBD), coined TBD-DP (Data Postdiction). TBD-DP relies on existing machine learning algorithms to abstract TBD into compact models that can be stored and queried when necessary. SPATE+ is conceptually divided into three layers: (i) storage and indexing, where high storage efficiency is achieved using the compression and decay components. This category also includes a spatio-temporal index with four levels of temporal resolutions minimizing the query response time for data exploration queries; (ii) operators, where a high performance AkNN query operator outperforms state-of-the-art techniques in terms of efficient partitioning, replication and refinement; and (iii) applications, where an efficient query exploration framework, called SPATE, provides novel data exploration functionalities to the user. We also present an anonymous crowd messaging application, called Rayzit, which utilizes SBD to connect the users instantly to their k Nearest Neighbors (kNN) as they move in space, to expose the contributions of the components that are part of SPATE+.