Big Mobility Data Analytics: algorithms and techniques for efficient trajectory clustering

Abstract

Ο πρωτοφανής ρυθμός παραγωγής δεδομένων τροχιάς που παρατηρείται τα τελευταία χρόνια και προκλήθηκε από τον πολλαπλασιασμό των συσκευών με δυνατότητα GPS, δημιουργεί νέες προκλήσεις όσον αφορά την αποθήκευση, την αναζήτηση, την ανάλυση και την εξαγωγή γνώσης από δεδομένα κίνησης. Μια από αυτές τις προκλήσεις είναι η ανάλυση συστάδων, η οποία στοχεύει στον εντοπισμό συστάδων κινούμενων αντικειμένων σύμφωνα με τον βαθμό ομοιότητας της κίνησης τους. Η ανακάλυψη συστάδων κινούμενων αντικειμένων είναι μια σημαντική λειτουργία κατά την προσπάθεια εξαγωγής γνώσης από δεδομένα κίνησης, διότι με τον τρόπο αυτό μπορούν να αποκαλυφθούν τα υποκείμενα κρυμμένα πρότυπα συλλογικής συμπεριφοράς. Αυτό που είναι ακόμη πιο δύσκολο είναι η αντιμετώπιση των τεχνικών ανακάλυψης γνώσης, όπως η ανάλυση συστάδων, ως ενα αναπόσπαστο κομμάτι ενός πραγματικού DMBS, το οποίο μπορεί να αποδειχθεί πρακτικό και χρήσιμο σε σενάρια εφαρμογών πραγματικού κόσμου, όπου λαμβάνονται υπόψη θέματα όπως η ευκολία χρήσης (π.χ. μέσω μιας απλής διεπαφής SQL). Επιπλέον, η υποστήριξη της σταδιακής και προοδευτικής ανάλυσης συστάδων στο πλαίσιο των δυναμικών εφαρμογών παρουσιάζει μεγάλο ενδιαφέρον, όπου (i) οι νέες τροχιές φθάνουν με συχνό ρυθμό και (ii) η ανάλυση πραγματοποιείται σε διαφορετικά τμήματα του συνόλου δεδομένων και αυτό μπορεί να επαναληφθεί πολλές φορές ανά εργασία ανάλυσης. Ωστόσο, η εκτέλεση τέτοιων ``δαπανηρών'' λειτουργιών σε τεράστιους όγκους δεδομένων με κεντρικοποιημένο τρόπο δεν είναι καθόλου εύκολη, πράγμα που με τη σειρά του απαιτεί παράλληλους και κατανεμημένους αλγόριθμους για την αντιμετώπιση των απαιτήσεων που θέτει η εποχή των Μεγάλων Δεδομένων. Το σημείο συμφόρησης της εκτέλεσης τέτοιων ``δαπανηρών'' λειτουργιών, όπως η ανάλυση συστάδων, είναι το υποκείμενο ερώτημα ``σύνδεσης''. Η ``σύνδεση'' συνόλων δεδομένων τροχιάς δεν αποτελεί μόνο τον ακρογωνιαίο λίθο των διαφόρων μεθόδων ανάλυσης συστάδων τροχιών, αλλά είναι επίσης μια σημαντική λειτουργία σε αναλύσεις δεδομένων κίνησης με ένα ευρύ φάσμα εφαρμογών, όπως ο συνεπιβατισμός, η ανακάλυψη ύποπτων κινήσεων κλπ. Σε αυτή τη διατριβή, στοχεύουμε να αντιμετωπίσουμε τις παραπάνω προκλήσεις.

Προς αυτή την κατεύθυνση, προτείνουμε έναν νέο in-DBMS αλγόριθμο συσταδοποίησης υποτροχιών βασιζόμενο στη δειγματολειψία, ο οποίος ονομάζεται S2T-Clustering και είναι ενσωματωμένος σε ένα πραγματικό MOD μέσω ενός επεκτάσιμου DBMS (της PostgreSQL στην πρωτότυπη υλοποίησή μας), που επιλύει το πρόβλημα πιο αποτελεσματικά από την τελευταία λέξη της τεχνολογίας. Επιπλέον, εισάγουμε το πρόβλημα της χρονικά περιορισμένη ανάλυση συστάδων υποτροχιών. Προκειμένου να το αντιμετωπίσουμε, προτείνουμε το ReTraTree, ένα σχήμα ευρετηρίου που οργανώνει τροχιές χρησιμοποιώντας μια αποτελεσματική τεχνική χωροχρονικής διαμέρισης. Οι διαμερίσεις στο ReTraTree, αντιστοιχούν σε ομάδες υποτροχιών, οι οποίες διατηρούνται σταδιακά και αντιπροσωπεύονται μέσω μιας ιεραρχικής οργάνωσης μίας μικρής (κατά συνέπεια ``ελαφριάς'' όσον αφορά τη μνήμη) ομάδας «αντιπροσωπευτικών» υποτροχιών. Δεδομένου αυτού, το υπό μελέτη πρόβλημα μπορεί να λυθεί αποτελεσματικά ως ένα ερώτημα στο ReTraTree, το οποίο το ονομάζουμε QuT-Clustering. Η προσέγγισή μας συμβάλλει περαιτέρω στον τομέα διαχείρισης και εξόρυξης γνώσης δεδομένων κίνησης για τον πρόσθετο λόγο ότι έχει σχεδιαστεί και εφαρμοστεί σε ένα MOD. Αυτή η λειτουργικότητα επιτρέπει στους χρήστες της εφαρμογής να εκτελούν προοδευτική ανάλυση συστάδων μέσω απλής SQL σε πραγματικά επεκτάσιμα DBMS. Επιπλέον, προτείνουμε μια αποτελεσματική αρχιτεκτονική in-DBMS για την προοδευτική ανάλυση συστάδων υποτροχιών, χρησιμοποιώντας τις προαναφερθείσες in-DBMS λύσεις, σε συνδυασμό με ενα εργαλείο Οπτικής Ανάλυσης (VA) για τη διευκόλυνση της ανάλυσης στον πραγματικό κόσμο.

Προς αντιμετώπιση των προκλήσεων που θέτει η εποχή των Μεγάλων Δεδομένων, παρουσιάζουμε το ερώτημα της Κατανεμημένης Σύνδεσης Υποτροχιών, μια σημαντική λειτουργία στον τομέα των χωροχρονικών δεδομένων, όπου πολύ μεγάλα σύνολα δεδομένων τροχιών κινούμενων αντικειμένων επεξεργάζονται για αναλυτικούς σκοπούς. Για να αντιμετωπίσουμε αυτό το πρόβλημα με αποτελεσματικό τρόπο, χρησιμοποιήσαμε το μοντέλο προγραμματισμού MapReduce. Τέλος, αντιμετωπίζουμε το πρόβλημα της Κατανεμημένης Συσταδοποίησης Υποτροχιών με βάση το ερώτημα της Κατανεμημένης Σύνδεσης Υποτροχιών, προκειμένου να αντιμετωπίσουμε αποτελεσματικά το πρόβλημα. Στη συνέχεια, προτείναμε δύο εναλλακτικούς αλγορίθμους τμηματοποίησης τροχιάς και έναν κατανεμημένο αλγόριθμο ομαδοποίησης, όπου οι συστάδες ταυτοποιούνται με έναν παράλληλο τρόπο.