Analysis of spatiotemporal data

Abstract

In this thesis, we address major challenges in spatiotemporal data mining. Spatiotemporal data are data that relate to both space and time. Spatiotemporal data mining is the process of discovering patterns and extracting knowledge from spatiotemporal data. Examples of spatiotemporal data are trajectories of moving vehicles (i.e., GPS equipped buses or taxis) that move around the city reporting their GPS location along with the timestamp of each measurement, or animals’ trajectories that are particularly important for zoologists in order to analyze the ecological behavior. The ubiquitous mobile devices generate massive datasets of GPS trajectories that are particularly difficult to interpret or analyse. Examples of spatiotemporal data mining include the extraction of moving patterns among a collection of moving objects. Another example of trajectory data mining, focusing in urban environments, is the traffic modelling. This refers to the analysis of the real-time traffic reports in order to extract the current traffic condition across the road network and the forecasting of the future traffic condition. Detecting and forecasting the traffic condition is particularly important in order to perform travel time estimation of a given path. Also, traditionalcentralized systems are unable to cope with the current massive-scale of spatiotemporal data, mainly because a single host is not able to receive and process all incoming data in real-time. Due to this reason, there is a shift in using Distributed Stream Processing Systems (DSPS). The contributions in this thesis focus on three main topic areas: (i) discovering corridors from GPS trajectories, (ii) hybrid travel time estimation and (iii) distributed complex event processing. Bellow we provide a short description of each of these topics: Discovering corridors from GPS trajectoriesWe aim at detecting paths that are frequently followed by the moving objects in the spatiotemporal database. Our main hypothesis is that even if the moving objects have different origins and destinations they are following common paths. The detections of such common paths is particularly demanding due to the complex nature of the spatiotemporal data. In this thesis we proposed a pipelined algorithm that discovers such frequent paths. The proposed technique first discovers areas that are frequently followed together by the moving objects and then discovers frequent paths following a greedy algorithm. Hybrid travel time estimation. This thesis also, focuses on the analysis of traffic condition across the road network and more specifically with the travel time estimation problem from one location of the road network to another given the path that will be followed and the time of departure. This problem is particularly challenging since the travel time depends on multiple factors that are difficult to be modeled. In this thesis we proposed a hybrid travel time estimation technique, named HTTE. Our technique performs travel time estimation for a given path (map-matched in the road network), using data provided by the other moving vehicles. Firstly, we are estimating road segments embeddings considering the available traffic information for each road segment. We also developed a hybrid mechanism that considers appropriately the recent traffic reports, the historical traffic reports (focusing on the periodicity of traffic condition) and the correlations among different road segments. Scalable and dynamic traffic management systemThe last part of this thesis focuses on complex event processing systems and provides techniques that efficiently allow the distributed processing of the incoming tuples. Such techniques are particularly important for the real-time analysis of spatiotemporal datasets, since the large volume of the incoming data and the complex processing of the incoming data may not be able to be processed in a single machine. Here we propose techniques that allow the system to adjust in changes of the incoming input rate and to automatically select the number of machines that willbe used.

Στην παρούσα διδακτορική διατριβή μελετάται το πρόβλημα της ανάλυσης χωροχρονικών δεδομένων. Τα χωροχρονικά δεδομένα είναι τα δεδομένα τα οποία σχετίζονται τόσο μετο χώρο όσο και με το χρόνο. Η ανάλυση χωροχρονικών δεδομένων είναι η διαδικασία εύρεσης προτύπων και η εξαγωγή γνώσης από τα χωροχρονικά δεδομένα. Παραδείγματα χρονικών δεδομένων αποτελούν οι τροχιές οχημάτων (π.χ. λεωφορείων ή ταξί) τα οποία κινούνται στην πόλη καταγράφοντας την τοποθεσία (στίγμα GPS) τους και τη χρονική στιγμή της κάθε μέτρησης ή οι τροχιές ζώων οι οποίες είναι ιδιαίτερα σημαντικές για ζωολόγους προκειμένου να κατανοήσουν τη συμπεριφορά του οικοσυστήματος. Οι πανταχού παρόντες κινητές συσκευές δημιουργούν τεράστιους όγκους δεδομένων από τροχιές κινούμενων αντικειμένων οι οποίες είναι ιδιαίτερα δύσκολο να κατανοηθούν και να αναλυθούν στην αρχική τους (μη επεξεργασμένη) μορφή. Ένα παράδειγμα ανάλυσης χωροχρονικών δεδομένων αποτελεί η εξαγωγή προτύπων κίνησης χρησιμοποιώντας ιστορικά δεδομένα τα οποία περιέχουν ακολουθείες των τοποθεσιών που κάθε κινούμενο αντικείμενο έχει επισκεφθεί. Ένα άλλο παράδειγμα ανάλυσης χωροχρονικών δεδομένων, το οποίο επικεντρώνεται σε αστικά περιβάλλοντα, είναι η μοντελοποίηση της κυκλοφοριακης κατάστασης του οδικού δικτύου. Ο στόχος σε αυτή την περίπτωση είναι η ανάλυση σε πραγματικό χρόνο των χωροχρονικών δεδομένων τα οποία παράγονται από ένα σύνολο κινούμενων οχημάτων και η κατανόηση της τρέχουσας κυκλοφοριακής κατάστασης στο οδικό δίκτυο καθώς και η πρόβλεψη της εξέλιξης της κυκλοφοριακής κατάστασης στο άμεσο μέλλον. Επιπλέον, τα παραδοσιακά κεντρικά συστήματα με έναν υπολογιστικό κόμβο δεν είναι σε θέση να αντιμετωπίσουν την τρέχουσα μαζική κλίμακα των χωροχρονικών δεδομένων, κυρίως επειδή μόνο ένας κεντρικός υπολογιστής δεν είναι σε θέση να λαμβάνει και να επεξεργάζεται σε πραγματικό χρόνο όλα τα εισερχόμενα δεδομένα. Λόγω της συγκεκριμένης αδυναμίας, υπάρχει μετατόπιση στην χρήση κατανεμημένων συστημάτων επεξεργασίας ροών χωροχρονικών δεδομένων. Οι συνεισφορές της διδακτορικής διατριβής επικεντρώνονται στις παρακάτω θεματικές περιοχές: (i) εντοπισμός συχνών διαδρομών από τροχιές κινούμενων αντικειμένων, (ii) υβριδική εκτίμηση του χρόνου μετάβασης και (iii) κατανεμημένη επεξεργασία σύνθετων γεγονότων.