Big mobility data analytics: algorithms and techniques for efficient trajectory clustering

Abstract

The unprecedented rate of trajectory data generation that has been observed during the recent years, caused by the proliferation of GPS-enabled devices, poses new challenges in terms of storage, querying, analytics and knowledge extraction from mobility data. One of these challenges is cluster analysis, which aims at identifying clusters of moving objects according to the similarity degree of their movement. Discovering clusters of moving objects is an important operation when trying to extract knowledge out of mobility data, since by doing so, the underlying hidden patterns of collective behavior can be unveiled. What is even more challenging is treating knowledge discovery techniques, such as cluster analysis, as an integral part of a real DMBS, which can turn out to be practical and useful in real-world application scenarios, where issues like the ease of use (e.g., via a simple SQL interface) are taken into consideration. Furthermore, the support of incremental and progressive cluster analysis in the context of dynamic applications is of great interest, where (i) new trajectories arrive at frequent rates, and (ii) the analysis is performed over different portions of the dataset, and this might be repeated several times per analysis task. However, performing such “expensive” operations over immense volumes of data in a centralized way is far from straightforward, which in turn calls for parallel and distributed algorithms to address the scalability requirements posed by the Big Data era. The bottleneck of performing “expensive” operations, such as cluster analysis, is the underlying join query. Joining trajectory datasets is not only the cornerstone of various trajectory cluster analysis methods, but it is also a significant operation in mobility data analytics with a wide range of applications, such as carpooling, suspicious movement discovery, etc. In this thesis, we aim to address the above challenges. Towards this direction, we propose a novel in-DBMS Sampling-based Sub Trajectory Clustering algorithm, namely S2T-Clustering, which is incorporated in a real MOD engine over an extensible DBMS (PostgreSQL in effectively than state-of-the-art techniques. Moreover, we introduce the temporally-constrained subtrajectory cluster analysis problem. To address it, we propose ReTraTree, an indexing scheme which organizes trajectories by using an effective spatio-temporal partitioning technique. Partitions in ReTraTree correspond to groupings of subtrajectories, which are incrementally maintained and represented via a hierarchical organization of a small (thus, light-weight in-memory) set of ‘representative’ subtrajectories. Given this, the problem in hand can be efficiently solved as a query operator on ReTraTree, coined QuT-Clustering. Our approach further contributes to the mobility data management and mining domain for the additional reason that it has been designed and implemented in a MOD engine. Such functionality enables the application users to perform progressive cluster analysis via simple SQL in a real extensible DBMS. Furthermore, we propose an efficient in-DBMS architecture for progressive time-aware subtrajectory cluster analysis, by utilizing the aforementioned in-DBMS solutions along with a Visual Analytics (VA) tool to facilitate real world analysis. Towards addressing the challenges posed by the Big Data era, we introduce the Distributed Subtrajectory Join query, an important operation in the spatiotemporal data management domain, where very large datasets of moving object trajectories are processed for analytic purposes. To address this problem in a scalable manner, we follow the MapReduce programming model. Finally, we address the problem of Distributed Subtrajectory Clustering by building upon the Distributed Subtrajectory Join query, in order to tackle the problem in an efficient manner. We propose two alternative trajectory segmentation algorithms and a distributed clustering algorithm where the clusters are identified in a parallel manner.

Ο πρωτοφανής ρυθμός παραγωγής δεδομένων τροχιάς που παρατηρείται τα τελευταία χρόνια και προκλήθηκε από τον πολλαπλασιασμό των συσκευών με δυνατότητα 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. Τέλος, αντιμετωπίζουμε το πρόβλημα της Κατανεμημένης Συσταδοποίησης Υποτροχιών με βάση το ερώτημα της Κατανεμημένης Σύνδεσης Υποτροχιών, προκειμένου να αντιμετωπίσουμε αποτελεσματικά το πρόβλημα. Στη συνέχεια, προτείναμε δύο εναλλακτικούς αλγορίθμους τμηματοποίησης τροχιάς και έναν κατανεμημένο αλγόριθμο ομαδοποίησης, όπου οι συστάδες ταυτοποιούνται με έναν παράλληλο τρόπο.