Scalable indexing and exploration of big time series data
Authors: Χατζηγεωργακίδης Γεώργιος 
Published: September 2021

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