Scalable indexing and exploration of big time series data
Κλιμακώσιμη δεικτοδότηση και εξερεύνηση μεγάλων δεδομένων χρονοσειρών
Διδακτορική διατριβή
Συγγραφέας
Χατζηγεωργακίδης, Γεώργιος
Ημερομηνία
2020-04-01Επιβλέπων
Σκιαδόπουλος, ΣπύροςΠερίληψη
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.
Περίληψη
Στις μέρες μας, σε πολλές βιομηχανικές και ερευνητικές εφαρμογές (π.χ., διαδίκτυο
των πραγμάτων, αστρονομία, οικονομικά, βιολογία), δημιουργείται και αποθηκεύεται με-
γάλος όγκος δεδομένων χρονοσειρών. Ένα σημαντικό ποσοστό αυτών αποτελούν οι
γεωχωρικές χρονοσειρές, δηλαδή εκείνες οι οποίες σχετίζονται με συγκεκριμένες τοπο-
θεσίες. Τα τελευταία χρόνια, πληθώρα επιστημονικών άρθρων μελετά μεθόδους αναζήτη-
σης ομοιότητας σε δεδομένα χρονοσειρών αψηφώντας τη γεωχωρική τους υπόσταση, η
οποία θα επέτρεπε υβριδικά ερωτήματα, βασισμένα –εκτός από την ομοιότητα στο πεδίο
του χρόνου– στη χωρική εγγύτητα των χρονοσειρών. Παράλληλα, ενδιαφέρον παρουσιά-
ζει το πρόβλημα εντοπισμού ζευγαριών και ομάδων τοπικά όμοιων, συν-εξελισσόμενων
χρονοσειρών. Συγκεκριμένα, οι ομάδες αυτές αποτελόυνται από χρονοσειρές των οποί-
ων οι τιμές σε οποιαδήποτε υποακολουθία τους δεν διαφέρουν περισσότερο από ένα
δωθέν κατώφλι. Ο εντοπισμός τέτοιων ομάδων μπορεί να φανερώσει χρήσιμα κοινά τοπι-
κά μοτίβα και τάσεις σε δεδομένα χρονοσειρών. Επίσης, πληθώρα επιστημονικών άρθρων
επικεντρώνεται στην οπτικοποίηση και οπτική ανάλυση δεδομένων χρονοσειρών. Η απο-
δοτική οπτική εξερεύνηση γεωχωρικών χρονοσειρών, όμως, δεν έχει μελετηθεί επαρκώς.
Τέλος, η αποδοτική πρόβλεψη δεδομένων χρονοσειρών μεγάλης κλίματας είναι ένα ακό-
μη πεδίο έρευνας το οποίο έχει κεντρίσει το ενδιαφέρον της επιστημονικής κοινότητας,
λόγω των διαφόρων ιδιαιτεροτήτων του συγκεκριμένουν τύπου δεδομένων.
Στη διατριβή αυτή, παρουσιάζουμε ένα υβριδικό ευρετήριο με το όνομα BTSR-tree,
το οποίο μπορεί αποδοτικά να απαντήσει υβριδικά ερωτήματα αναζήτησης ομοιότητας.
Επιπροσθέτως, επικεντρωνόμαστε στο πρόβλημα των υβριδικών συνδέσεων ομοιότητας
σε δεδομένα γεωχωρικών χρονοσειρών. Για την επίλυσή του, προτείνουμε κεντρικούς
και κατανεμημένους αλγορίθμους βασισμένους στη μέθοδο MapReduce, με τη χρήση
υβριδικών και μη ευρετηρίων. Στη συνέχεια, σχετικά με το πρόβλημα εντοπισμού ζευ-
γαριών και ομάδων τοπικά όμοιων συν-εξελισσόμενων χρονοσειρών, προτείνουμε μια
μέθοδο φιλτραρίσματος-επαλήθευσης, η οποία επικεντρώνεται σε συγκεκριμένα σημεία
ελέγχου στο πεδίο του χρόνου, επιταγχύνοντας τη διαδικασία. Παράλληλα, προτείνουμε
μεθόδους απάντησης υβριδικών ερωτημάτων τοπικής ομοιότητας σε δεδομένα γεωχωρι-
κών χρονοσειρών μεγάλου όγκου. Για την υποστήριξη τέτοιων ερωτημάτων, εισάγουμε
μια επέκταση του ευρετηρίου BTSR-tree, με το όνομα SBTSR-tree, το οποίο βελτιστοποιεί την βασισμένη σε τοπική ομοιότητα αναζήτηση. Στη συνέχεια, παρουσιάζουμε δυο
προσεγγίσεις βασισμένες σε υβριδικά ευρετήρια, οι οποίες επιτρέπουν την αποδοτική
εξερεύνηση δεδομένων γεωχωρικών χρονοσειρών μεγάλου όγκου με τη χρήση οπτικο-
ποιήσεων σε χάρτη. Για την πρώτη, χρησιμοποιούμε το προαναφερθέν υβριδικό ευρετήριο
BTSR-tree. Η δεύτερη προσέγγιση βασίζεται σε μια επέκταση του υπάρχοντος ευρετη-
ρίου χρονοσειρών iSAX, με το όνομα geo-iSAX. Συγκεκριμένα, παρουσιάζουμε τη δομή
του νέου ευρετηρίου και μεθόδους αποδοτικής οπτικοποίησης τέτοιων δεδομένων. Τέλος,
στο πλαίσιο της πρόβλεψης δεδομένων χρονοσειρών μεγάλης κλίματας, παρουσιάζου-
με ένα παράλληλο και κατανεμημένο πλαίσιο επεξεργασίας με το όνομα FML-kNN, το
οποίο εκτελεί αποδοτικά κατηγοριοποίηση και παλινδρόμηση. Ο κεντρικός αλγόριθμός
του πλαισίου είναι βασισμένος στη μέθοδο συνδέσεων k-πλησιέστερων γειτόνων και
μπορεί να εκτελεστεί σε μια παράλληλη συνεδρία –σε αντίθεση με παρόμοιες μεθόδους–,
επιτρέποντας, έτσι, την εκτέλεση σε δεδομένα μεγάλου όγκου, διαφόρων βαθμών λε-
πτομέρειας και διαστατικότητας.
Όλοι οι αλγόριθμοι και μέθοδοι που παρουσιαζονται στην διατριβή αυτή αξιολο-
γούνται πειραματικά και εμπειρικά, με τη χρήση συνθετικών ή δεδομένων παργματικού
κόσμου. Παράλληλα, συγκρίνονται με βασικές, ή υπάρχουσες μεθόδους αιχμής (stateof-
the-art), αποδεικνύοντας την υπεροχή τους και επιβεβαιώνοντας την αποδοτικότητά
τους.