Scalable indexing and exploration of big time series data

Abstract

Time series are generated and stored at a vastly increasing rate in many industrial and research applications, including the Web and the Internet of Things, public utilities, finance, astronomy, biology, and many more. A significant portion concerns geolocated time series, i.e., those generated at, or otherwise associated with specific locations. Although several works have focused on efficient time series similarity search, there has been limited attention to the inherent challenge that geolocated time series introduce for hybrid queries, i.e., queries that involve both spatial proximity and time series similarity. Apart from traditional similarity search, we also consider the problem of detecting locally similar pairs and groups, called bundles, over co-evolving time series. These are pairs or groups of subsequences whose values do not differ by more than a predefined threshold for a number of consecutive timestamps. They could represent potentially valuable, concurrent common local patterns and trends among the time series. Time series visualization and visual analytics in general, is another field that has drawn the attention of the scientific community. However, there is a lack of efficient techniques for visual exploration and analysis of geolocated time series. Finally, large-scale time series forecasting has attracted a significant amount of interest, due to the highly complex nature of such data. In this thesis, we efficiently process hybrid queries through a hybrid index that we propose, called BTSR-tree. Furthermore, we address the problem of hybrid similarity joins over such geolocated time series. We introduce both centralized and MapReduce-based algorithms for performing such join operations using spatial-only, time series-only, and hybrid indices. Then, we tackle the problem of pair and bundle discovery over co-evolving time series, via a filter-verification technique that only examines candidate matches at judiciously chosen checkpoints across time. In the same line of work, we consider hybrid queries for retrieving geolocated time series based on filters that combine spatial distance and time series local similarity. To efficiently support such queries, we introduce the SBTSR-tree index, an extension of BTSR-tree that further optimizes local similarity search. Additionally, we present two approaches that rely on hybrid indices, allowing efficient map-based visual exploration and summarization of geolocated time series data. In particular, we use the BTSR-tree index and we introduce a new variant of the standard iSAX index, called geo-iSAX. We define the structure of the new index and show how both hybrid indices can be directly exploited to produce map-based visualizations of geolocated time series at different levels of granularity. Finally, towards large-scale time series forecasting, we introduce FML-kNN, a novel distributed processing framework for big data that performs probabilistic classification and regression. The framework’s core is consisted of a k-nearest neighbor joins algorithm which, contrary to similar approaches, is executed in a single distributed session and scales on very large volumes of data of variable granularity and dimensionality. Throughout this thesis, we experimentally and empirically evaluate our work using synthetic and real-world datasets from diverse domains, against baseline and state-of-the-art existing methods, demonstrating the efficiency and superiority of our approaches.

Στις μέρες μας, σε πολλές βιομηχανικές και ερευνητικές εφαρμογές (π.χ., διαδίκτυο των πραγμάτων, αστρονομία, οικονομικά, βιολογία), δημιουργείται και αποθηκεύεται μεγάλος όγκος δεδομένων χρονοσειρών. Ένα σημαντικό ποσοστό αυτών αποτελούν οι γεωχωρικές χρονοσειρές, δηλαδή εκείνες οι οποίες σχετίζονται με συγκεκριμένες τοποθεσίες. Τα τελευταία χρόνια, πληθώρα επιστημονικών άρθρων μελετά μεθόδους αναζήτησης ομοιότητας σε δεδομένα χρονοσειρών αψηφώντας τη γεωχωρική τους υπόσταση, η οποία θα επέτρεπε υβριδικά ερωτήματα, βασισμένα –εκτός από την ομοιότητα στο πεδίο του χρόνου– στη χωρική εγγύτητα των χρονοσειρών. Παράλληλα, ενδιαφέρον παρουσιάζει το πρόβλημα εντοπισμού ζευγαριών και ομάδων τοπικά όμοιων, συνεξελισσόμενων χρονοσειρών. Συγκεκριμένα, οι ομάδες αυτές αποτελούνται από χρονοσειρές των οποίων οι τιμές σε οποιαδήποτε υπακολουθία τους δεν διαφέρουν περισσότερο από ένα δoθέν κατώφλι. Ο εντοπισμός τέτοιων ομάδων μπορεί να φανερώσει χρήσιμα κοινά τοπικά μοτίβα και τάσεις σε δεδομένα χρονοσειρών. Επίσης, πληθώρα επιστημονικών άρθρων επικεντρώνεται στην οπτικοποίηση και οπτική ανάλυση δεδομένων χρονοσειρών. Η αποδοτική οπτική εξερεύνηση γεωχωρικών χρονοσειρών, όμως, δεν έχει μελετηθεί επαρκώς. Τέλος, η αποδοτική πρόβλεψη δεδομένων χρονοσειρών μεγάλης κλίμαkας είναι ένα ακόμη πεδίο έρευνας το οποίο έχει κεντρίσει το ενδιαφέρον της επιστημονικής κοινότητας, λόγω των διαφόρων ιδιαιτεροτήτων του συγκεκριμένου τύπου δεδομένων. Στη διατριβή αυτή, παρουσιάζουμε ένα υβριδικό ευρετήριο με το όνομα BTSR-tree, το οποίο μπορεί αποδοτικά να απαντήσει υβριδικά ερωτήματα αναζήτησης ομοιότητας. Επιπροσθέτως, επικεντρωνόμαστε στο πρόβλημα των υβριδικών συνδέσεων ομοιότητας σε δεδομένα γεωχωρικών χρονοσειρών. Για την επίλυσή του, προτείνουμε κεντρικούς και κατανεμημένους αλγορίθμους βασισμένους στη μέθοδο MapReduce, με τη χρήση υβριδικών και μη ευρετηρίων. Στη συνέχεια, σχετικά με το πρόβλημα εντοπισμού ζευγαριών και ομάδων τοπικά όμοιων συνεξελισσόμενων χρονοσειρών, προτείνουμε μια μέθοδο φιλτραρίσματος-επαλήθευσης, η οποία επικεντρώνεται σε συγκεκριμένα σημεία ελέγχου στο πεδίο του χρόνου, επιταχύνοντας τη διαδικασία. Παράλληλα, προτείνουμε μεθόδους απάντησης υβριδικών ερωτημάτων τοπικής ομοιότητας σε δεδομένα γεωχωρικών χρονοσειρών μεγάλου όγκου. Για την υποστήριξη τέτοιων ερωτημάτων, εισάγουμε μια επέκταση του ευρετηρίου BTSR-tree, με το όνομα SBTSR-tree, το οποίο βελτιστοποιεί την βασισμένη σε τοπική ομοιότητα αναζήτηση. Στη συνέχεια, παρουσιάζουμε δυο προσεγγίσεις βασισμένες σε υβριδικά ευρετήρια, οι οποίες επιτρέπουν την αποδοτική εξερεύνηση δεδομένων γεωχωρικών χρονοσειρών μεγάλου όγκου με τη χρήση οπτικοποιήσεων σε χάρτη. Για την πρώτη, χρησιμοποιούμε το προαναφερθέν υβριδικό ευρετήριο BTSR-tree. Η δεύτερη προσέγγιση βασίζεται σε μια επέκταση του υπάρχοντος ευρετηρίου χρονοσειρών iSAX, με το όνομα geo-iSAX. Συγκεκριμένα, παρουσιάζουμε τη δομή του νέου ευρετηρίου και μεθόδους αποδοτικής οπτικοποίησης τέτοιων δεδομένων. Τέλος, στο πλαίσιο της πρόβλεψης δεδομένων χρονοσειρών μεγάλης κλίμακας, παρουσιάζουμε ένα παράλληλο και κατανεμημένο πλαίσιο επεξεργασίας με το όνομα FML-kNN, το οποίο εκτελεί αποδοτικά κατηγοριοποίηση και παλινδρόμηση. Ο κεντρικός αλγόριθμός του πλαισίου είναι βασισμένος στη μέθοδο συνδέσεων k-πλησιέστερων γειτόνων και μπορεί να εκτελεστεί σε μια παράλληλη συνεδρία –σε αντίθεση με παρόμοιες μεθόδους–, επιτρέποντας, έτσι, την εκτέλεση σε δεδομένα μεγάλου όγκου, διαφόρων βαθμών λεπτομέρειας και διαστατικότητας. Όλοι οι αλγόριθμοι και μέθοδοι που παρουσιάζονται στην διατριβή αυτή αξιολογούνται πειραματικά και εμπειρικά, με τη χρήση συνθετικών ή δεδομένων πραγματικού κόσμου. Παράλληλα, συγκρίνονται με βασικές, ή υπάρχουσες μεθόδους αιχμής (state- of-the-art), αποδεικνύοντας την υπεροχή τους και επιβεβαιώνοντας την αποδοτικότητά τους.