Abstract.tex

% !TEX encoding = UTF-8 Unicode
% !TEX root = ThesisGchatzi.tex

\chapter{Abstract} \label{chap:abstract}

\textit{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 \textit{geolocated} time series, i.e., those generated at, or otherwise associated with specific locations. Although several works have focused on efficient time series \textit{similarity search}, there has been limited attention to the inherent challenge that geolocated time series introduce for \textit{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 \textit{locally} similar \textit{pairs} and groups, called \textit{bundles}, over \textit{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, thus indicating common local patterns and trends. Time series \textit{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 \textit{geolocated} time series. Finally, \textit{large-scale} time series \textit{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 \textit{hybrid index} that we propose, called \textit{\btsr}. Furthermore, we address the problem of \textit{hybrid similarity joins} over such geolocated time series. We introduce both \textit{centralized} and \textit{MapReduce}-based algorithms for performing such join operations using \textit{spatial-only}, \textit{time series-only}, and \textit{hybrid} indices. Then, we tackle the problem of \textit{pair} and \textit{bundle} discovery over co-evolving time series, via a filter-verification technique that only examines candidate matches at judiciously chosen \textit{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 \textit{\sbtsr} index, an extension of \btsr that further optimizes local similarity search. Additionally, we present two approaches that rely on hybrid indices, allowing efficient map-based \textit{visual exploration} and \textit{summarization} of geolocated time series data. In particular, we use the \btsr index and we introduce a new variant of the standard \textit{\isax} index, called \textit{\hisax}. 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 \textit{FML-$k$NN}, a novel distributed processing framework for big data that performs probabilistic classification and regression. The framework's core is consisted of a \textit{$k$-nearest neighbor joins} algorithm which, contrary to similar approaches, is executed in a \textit{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.

\chapter{Περίληψη}

\selectlanguage{greek}

Στις μέρες μας, σε πολλές βιομηχανικές και ερευνητικές εφαρμογές (π.χ., διαδίκτυο των πραγμάτων, αστρονομία, οικονομικά, βιολογία), δημιουργείται και αποθηκεύεται μεγάλος όγκος δεδομένων \textit{χρονοσειρών}. Ένα σημαντικό ποσοστό αυτών αποτελούν οι \textit{γεωχωρικές} χρονοσειρές, δηλαδή εκείνες οι οποίες σχετίζονται με συγκεκριμένες τοποθεσίες. Τα τελευταία χρόνια, πληθώρα επιστημονικών άρθρων μελετά μεθόδους \textit{αναζήτησης ομοιότητας} σε δεδομένα χρονοσειρών αψηφώντας τη γεωχωρική τους υπόσταση, η οποία θα επέτρεπε \textit{υβριδικά ερωτήματα}, βασισμένα --εκτός από την ομοιότητα στο πεδίο του χρόνου-- στη χωρική εγγύτητα των χρονοσειρών. Παράλληλα, ενδιαφέρον παρουσιάζει το πρόβλημα εντοπισμού \textit{ζευγαριών} ή \textit{ομάδων τοπικά όμοιων, συν-εξελισσόμενων} χρονοσειρών. Συγκεκριμένα, τα ζευγάρια (ή ομάδες) αυτά αποτελόυνται από χρονοσειρές των οποίων οι τιμές σε οποιαδήποτε υποακολουθία τους δεν διαφέρουν περισσότερο από ένα δωθέν κατώφλι. Ο εντοπισμός τέτοιων ζευγαριών (ή ομάδων) μπορεί να φανερώσει χρήσιμα κοινά τοπικά μοτίβα και τάσεις σε δεδομένα χρονοσειρών. Επίσης, πληθώρα επιστημονικών άρθρων επικεντρώνεται στην \textit{οπτικοποίηση} και οπτική ανάλυση δεδομένων χρονοσειρών. Η αποδοτική οπτική εξερέυνηση \textit{γεωχωρικών} χρονοσειρών, όμως, δεν έχει μελετηθεί επαρκώς. Τέλος, η αποδοτική \textit{πρόβλεψη} δεδομένων χρονοσειρών \textit{μεγάλης κλίματας} είναι ένα ακόμη πεδίο έρευνας το οποίο έχει κεντρίσει το ενδιαφέρον της επιστημονικής κοινότητας, λόγω των διαφόρων ιδιαιτεροτήτων του συγκεκριμένουν τύπου δεδομένων.

Στη διατριβή αυτή, παρουσιάζουμε ένα \textit{υβριδικό} ευρετήριο με το όνομα \textit{\btsr}, το οποίο μπορεί αποδοτικά να απαντήσει υβριδικά ερωτήματα αναζήτησης ομοιότητας. Επιπροσθέτως, επικεντρωνόμαστε στο πρόβλημα των \textit{υβριδικών ενώσεων ομοιότητας} σε δεδομένα γεωχωρικών χρονοσειρών. Για την επίλυσή του, προτείνουμε \textit{κεντρικούς} και \textit{κατανεμημένους} αλγορίθμους βασισμένους στη μέθοδο \textit{MapReduce}, με τη χρήση υβριδικών και μη ευρετηρίων. Στη συνέχεια, σχετικά με το πρόβλημα εντοπισμού ζευγαριών η ομάδων τοπικά όμοιων συν-εξελισσόμενων χρονοσειρών, προτείνουμε μια μέθοδο φιλτραρίσματος-επαλήθευσης, η οποία επικεντρώνεται σε συγκεκριμένα σημεία ελέγχου στο πεδίο του χρόνου, επιταγχύνοντας τη διαδικασία. Παράλληλα, προτείνουμε μεθόδους απάντησης υβριδικών ερωτημάτων τοπικής ομοιότητας σε δεδομένα γεωχωρικών χρονοσειρών μεγάλου όγκου. Για την υποστήριξη τέτοιων ερωτημάτων, εισάγουμε μια επέκταση του ευρετηρίου \btsr, με το όνομα \textit{\sbtsr}, το οποίο βελτιστοποιεί την βασισμένη σε τοπική ομοιότητα αναζήτηση. Στη συνέχεια, παρουσιάζουμε δυο προσεγγίσεις βασισμένες σε υβριδικά ευρετήρια, οι οποίες επιτρέπουν την αποδοτική εξερεύνηση δεδομένων γεωχωρικών χρονοσειρών μεγάλου όγκου με τη χρήση \textit{οπτικοποιήσεων} σε χάρτη. Για την πρώτη, χρησιμοποιούμε το προαναφερθέν υβριδικό ευρετήριο \btsr. Η δεύτερη προσέγγιση βασίζεται σε μια επέκταση του υπάρχοντος ευρετηρίου χρονοσειρών \textit{\isax}, με το όνομα \textit{\hisax}. Συγκεκριμένα, παρουσιάζουμε τη δομή του νέου ευρετηρίου και μεθόδους αποδοτικής οπτικοποίησης τέτοιων δεδομένων. Τέλος, στο πλαίσιο της πρόβλεψης δεδομένων χρονοσειρών μεγάλης κλίματας, παρουσιάζουμε ένα παράλληλο και κατανεμημένο πλαίσιο επεξεργασίας με το όνομα \textit{FML-$k$NN}, το οποίο εκτελεί αποδοτικά κατηγοριοποίηση και παλινδρόμηση. Ο κεντρικός αλγόριθμός του πλαισίου είναι βασισμένος στη μέθοδο ενώσεων \textit{$k$-πλησιέστερων γειτόνων} και μπορεί να εκτελεστεί σε μια παράλληλη συνεδρία --σε αντίθεση με παρόμοιες μεθόδους--, επιτρέποντας, έτσι, την εκτέλεση σε δεδομένα μεγάλου όγκου, διαφόρων βαθμών λεπτομέρειας και διαστατικότητας.

Όλοι οι αλγόριθμοι και μέθοδοι που παρουσιαζονται στην διατριβή αυτή αξιολογούνται πειραματικά και εμπειρικά, με τη χρήση συνθετικών ή δεδομένων παργματικού κόσμου. Συγκεκριμένα, συγκρίνονται με βασικές, ή υπάρχουσες μεθόδους αιχμής (state-of-the-art), αποδεικνύοντας την υπεροχή τους και επιβεβαιώνοντας την αποδοτικότητά τους.