Αλγόριθμοι ερωτημάτων εγγύτητας τροχιών σε σημεία ενδιαφέροντος πάνω σε χωρικά δίκτυα
Creators: name: Πλιάκης, Νικόλαος Ιωάννη
Publisher: name: Aristotle University of Thessaloniki
Year: 2017
Subjects: Χωρικά δίκτυα
Τροχιές
Σημεία ενδιαφέροντος
Spatial Networks
Trajectories
Points of Interest

description: Τα τελευταία χρόνια έχει παρατηρηθεί μία μεγάλη αύξηση της ανάγκης για αναζήτηση μονοπατιών και τροχιών σε πολλών ειδών δίκτυα (πόλεις, δίκτυα υπολογιστών, κτλ) με αποδοτικό τρόπο και σε εύλογο χρονικό διάστημα, ειδικά εάν σκεφτεί κανείς το γεγονός ότι ολοένα και περισσότεροι άνθρωποι ταξιδεύουν σε άλλες χώρες και πόλεις αναζητώντας εργασία ή κάνοντας διακοπές. Το πρόβλημα, οπότε, ανάγεται σε ένα κλασικό πρόβλημα αναζήτηης, με τις γνωσστές ανάγκες δεικτοδότησης και αποδοτικής αποθήκευσης των δεδομένων, ώστε να μπορούν να επιστραφούν στο χρήστη σε εύλογο χρονικό διάστημα. Σε αυτή την εργασία, μελετούμε τις εμπορικές και επιστημονικές ανάγκες και εφαρμογές της αναζήτησης και δεικτοδότησης τροχιών ανά την ιστορία στο εισαγωγικό κεφάλαιο. Εξετάζουμε τις ευρείες έννοιες του δικτύου, της τροχιάς, καθώς και των κινούμενων αντικειμένων. Στο δεύτερο κεφάλαιο, προσφέρουμε παραδείγματα σχετικής εργασίας η οποία έχει ήδη πραγματωθεί πάνω στο θέμα της αναζήτησης και δεικτοδότησης τροχιών. Αναφέρουμε τα αποτελέσματα αυτών των ερευνών, καθώς και τα ανοιχτά θέματα που προέκυψαν από αυτές. Στο τρίτο κεφάλαιο, παραθέτουμε τον ορισμό του προβλήματος που καλούμαστε να λύσουμε, δίνοντας ακριβείς ορισμούς για τα γραφήματα που μοντελοποιούν το δίκτυό μας, τις τροχιές που δημιουργούνται πάνω σε αυτό και τα κινούμενα αντικείμενα που τις χρησιμοποιούν για να κινηθούν πάνω στο δίκτυο. Στο επόμενο κεφάλαιο, βασισμένοι στη σχετική έρευνα που έχει πραγματοποιηθεί, εστιάζουμε πάνω σε τρεις αλγόριθμους που αποπειρώνται να δώσουν λύση στο συγκεκριμένο θέμα μας, τους FNR-Tree και MON-Tree, οι οποίοι βασίζονται σε επεκτάσεις του γνωστού R-Tree, και την εκτεταμένη με συστάδες τροχιών λίστα γειτνίασης, η οποία επεκτείνει τη δομή της λίστας γειτνίασης και παρέχει δύο νέες μετρικές οι οποίες χρησιμοποιούνται για τη σύγκριση μεταξύ των τροχιών. Δίνουμε εκτενείς ορισμούς και περιγραφές για κάθε μία από τις μεθόδους. Το αμέσως επόμενο κεφάλαιο ασχολείται με την υλοποίησή μας. Δείχνουμε τις προγραμματιστικές μεθοδολογίες που ακολουθήσαμε καθώς και τις βιβλιοθήκες που χρησιμοποιήθηκαν και αναφέρουμε το περιβάλλον στο οποίο εκτελέστηκαν τα πειράματα. Ακολούθως, πραγματοποιούμε την πειραματική αξιολόγηση για κάθε αλγόριθμο που περιγράψαμε παραπάνω επιδεικνύοντας τις δυνάμεις και τις αδυναμίες τους, τόσο για τον καθένα ξεχωριστά όσο και συγκριτικά μεταξύ τους. Τέλος, παραθέτουμε τα συμπεράσματά μας καθώς και εξηγήσεις σχετικά με την παρατηρηθείσα συμπεριφορά, και αναφέρουμε μία σειρά από ανοιχτά θέματα τα οποία θα μπορούσαν εν δυνάμει να αποτελέσουν τη βάση για κάποια μελλοντική εργασία
description: In recent years there has been an observable increase for seeking and retrieving paths and trajectories in all manners of networks (cities, computer networks, etc.) in an efficient and timely manner, especially when considering the fact that more and more people travel to other countries and cities seeking employment or recreation. This problem is, therefore, reduced into a classic search problem, with a need for indexing and efficiently storing the data so they can be returned to the user in a reasonable amount of time. In this paper, we briefly explore the commercial and scientific needs and applications of trajectory indexing throughout history in the introductory chapter. Here we examine what a network, a trajectory and the associated moving objects are, in broad terms. In the second chapter, we show examples of related research that has already been performed on the subject. We show the results of this research and identify the issues and open topics derived from it. In the third chapter, we formulate the problem we attempt to solve, by providing formal definitions for the graphs that model our networks, for the trajectories traced on these graphs, and for the moving objects/visitors that traverse the graphs by way of the trajectories. On the next chapter, based on the related research we studied, we identify three distinct algorithms that try to address the problem, FNR-Tree and MON-Tree, which are based on extending the known R-Tree structure (with one being an optimization of the other), and a cluster-extended Adjacency List, which is based on extending the already known adjacency list structure and providing two new specific metrics for comparison, with the metrics being defined in such a way as to take into account both the spatial and temporal distance between points on a network. We provide extensive descriptions of the algorithms and their underlying principles. The next chapter describes the implementation in great detail. We show the programming methodologies and libraries used for the algorithms’ evaluation, and we provide information on the actual environment the experiments took place. We then perform the experimental evaluation of each of the three algorithms we described above, and show the strengths and weaknesses of each algorithm on its own, as well as compared to each other. Following the experimental evaluation, we provide our own conclusions and explanations as to the observed behavior, and identify a number of open topics which could potentially provide a basis for future work on enhancing these algorithms or creating new ones