Geo - spatial knowledge in user - generated data: mining, modeling and applications

Abstract

With the proliferation of the Internet as the primary medium for data publishing and information exchange, we have seen an explosion in the amount of online content available on the Web. Thus, in addition to professionally-produced material being offered free on the Internet, the public has also been allowed, indeed encouraged, making its content available online to everyone. The volumes of such User-Generated Content (UGC) are already staggering and constantly growing. Our goal has to be to take advantage of this data explosion, which applied to the spatial domain translates to massively collecting and sharing knowledge to ultimately digitize the world. User-Generated geospatial content is also commonly referred to as Volunteered Geographic Information (VGI). There are several forms of VGI. In the current thesis, we will work on VGI from textual and GPS data.Subsumed under VGI, non-expert users have been providing a wealth of quantitative geospatial data online. With spatial reasoning being a basic form of human cognition, narratives expressing geospatial experiences, e.g., travel blogs, would provide an even bigger source of geospatial data. Textual narratives typically contain qualitative data in the form of objects and spatial relationships. One of the main scopes of this thesis is (i) to extract these relationships from user-generated texts, (ii) to quantify them and (iii) to reason about object locations based only on this qualitative data.Moreover, with the extracted and modeled spatial relations and by employing Bayesian inference, we obtain probabilistic measures of spatial connectedness of PoIs according to the crowd. Applying this measure to the corresponding road network, we obtain an altered cost function which does not exclusively rely on distance, and enriches an actual road networks taking crowdsourced spatial relations into account. With this we aim at obtaining paths that do not only minimize distance but also lead through more popular areas using knowledge generated by users. The last objective of this thesis, is to introduce the problem of continuous and non-continuous monitoring of nearest trajectories based on GPS data. In contrast to other similar approaches, we are interested in monitoring moving objects taking into account at each timestamp not only their current positions but their recent trajectory in a defined time window. We rst describe generic baseline algorithms for this problem, which applies for any aggregate function used to compute trajectory distances between objects, and without any restrictions on the movement of the objects. Using this as a framework, we continue to derive optimized algorithm for the cases where the distance between two moving objects in a time window is determined by their maximum or minimum distance in all contained timestamps. Furthermore, we propose additional optimizations for the case that an upper bound on the velocities of the objects exists.

Με την εξάπλωση του Διαδικτύου ως το κύριο μέσο για τη δημοσίευση στοιχείων και την ανταλλαγή πληροφοριών, έχουμε δει μια έκρηξη στον όγκο του περιεχομένου που είναι διαθέσιμο στο διαδίκτυο. ́Ετσι, εκτός από επαγγελματικό περιεχόμενο που είναι διαθέσιμο στο διαδίκτυο, το κοινό έχει επίσης τη δυνατότητα, να καθιστά το περιεχόμενό του διαθέσιμο σε όλους. Οι όγκοι της εν λόγω πληροφορίας από τους χρήστες είναι συνεχώς αυξανόμενοι. Στόχος μας πρέπει να είναι να επωφεληθούμε από αυτή την έκρηξη των δεδομένων, η οποία εφαρμοζόμενη στο γεοχωρικό πεδίο μεταφράζεται στη μαζική τη συλλογή και την ανταλλαγή γνώσης για την ψηφιοποίηση του κόσμου. Το περιεχόμενο που δημιουργείται από χρήστες στο γεωχωρικό πεδίο επίσης, αναφέρεται και ως εθελοντική γεωγραφική πληροφορία. Η εθελοντική γεωχωρική πληροφορία μπορεί να εμπεριέχεται σε πολλoύς τύπους δεδομένων. Στην παρούσα διατριβή, θα ασχοληθούμε με γεωχωρική πληροφορία από δεδομένα κειμένουκαι από δεδομένα πλοήγησης.Υπό τον όρο εθελοντική γεωγραφική πληροφορία, μη εξειδικευμένοι χρήστες παρέχουν έναν πλούτο ποσοτικών γεωχωρικών δεδομένων στο διαδίκτυο. Με τη χωρική συλλογιστική να είναι μια βασική μορφή της ανθρώπινης νόησης, αφηγήσεις που εκφράζουν γεωχωρικών εμπειρίες, π.χ., ταξιδιωτικά ιστολόγια, παρέχουν μια ακόμη μεγαλύτερη πηγή γεωχωρικών δεδομένων. Οι κειμενικές αφηγήσεις συνήθως περιέχουν ποιοτικά δεδομένα με τη μορφή χωρικών αντικειμένων και χωρικών σχέσεων. ́Ενας από τους βασικούς στόχους της παρούσας διατριβής είναι (1) για να εξαγάγουμε τις σχέσεις αυτές από κείμενα που δημιουργούνται από χρήστες, (2) να τις ποσοτικοποιήσουμε και (3) και να βγάλουμε συμπεράσματα για τις θέσεις αντικειμένων στο χώρο βασιζόμενοι μόνο σε αυτά τα ποιοτικά δεδομένα. ́Ενας επιπλέον στόχος της παρούσας διατριβής, είναι η χρησιμοποίηση των εξαγόμενων και ποσοτικά μοντελοποιημένων χωρικων σχέσεων σε συνδυασμό με πιθανοτική θεωρία, και την εφαρμογή τους για την επίλυση του προβλήματος του δημοφιλούς μονοπατιού. Συγκεκριμένα, χρησιμοποιούμε την χωρική πληροφορία που παράγεται από χρήστες και με αυτό στοχεύουμε στην απόκτηση μονοπατιών που δεν ελαχιστοποιούν μόνο την απόσταση, αλλά επίσης οδηγούν σε πιο δημοφιλείς περιοχές χρησιμοποιώντας γνώσης που παράγεται από τους ίδιους τους χρήστες.Ο τελευταίος στόχος της παρούσας διπλωματικής εργασίας, είναι να εισάγει το πρόβλημα της παρακολούθησης πλησιέστερων τροχιών με βάση δεδομένα πλοήγησης. Μελετούμε το πρόβλημα αυτό στη συνεχή και στη μή συνεχή περίπτωση. Παρουσιάζουμε αρχικά γενικούς και βασικούς αλγόριθμους για το πρόβλημα αυτό, και στην συνέχεια προτείνουμε επιπλέον βελτιστοποιήσεις με ακριβής και προσεγγιστικούς αλγορίθμους χρησιμοποιώντας πολλών τύπων χαρακτηριστικά