Βάσεις δεδομένων για την αποθήκευση και την επεξεργασία κινούμενων σημείων

Abstract

The current thesis, studies thoroughly the Moving Objects Databases and suggests new ordinary tree structures. More precisely, it presents queries for moving objects databases (nearest neighbor query, incremental nearest neighbor query, window query and timestamp query.). These queries are necessary in order to access the new tree structures. The main contributions of this thesis are presented in detail, in the following: • A first contribution constitutes an algorithm, that is being presented to calculate the nearest neighbor query, for moving objects databases. This algorithm is being compared to an already existent method, which is based on constant repetition. From the experiments, we can conclued that, the new algorithm has a lot better performance than the old one. • A next contribution is a method, that is able to answer to incremental nearest neighbor queries for moving objects databases. This incremental query has not been proposed for moving objects databases. For this reason, we present it and we compare it to the query, that already exists in static objects databases. Once again, the new algorithm outperforms the new one. • In the sequel, we extend an already existent tree structure, based on the quadtree, for the moving objects databases, as well. This method is being compared to an other one also based on the quadtree. The comparison is being made for window queries, in which the new structure outperforms by far the new one. • Next, the structure of the previous work is being compared to an other structure, that is not based on the quadtree and the movement of the objects belongs to the past.. The queries, which are implemented are both window and timestamp. For all the experiments being executed, the new method is better than the one, that is not based on the quadtree. • In conclusion, one final contribution constitutes the comparison of the structure of the previous work to an other structure, that is not based on the quadtree and the movement of the objects belongs to the past and to the future. Once again, the new structure has better performance than the old one. As it is already mentioned, the basic target of the current thesis is the management of moving objects databases. In the near future we expect, that a huge variety of applications will emerge, which will be based on the geographic position of the moving objects. All these applications are collectively called location-based services. The above mentioned applications are expected to crate a great range, to which the moving objects databases can be applied.

Η διατριβή αυτή μελετά διεξοδικά τις χωροχρονικές βάσεις δεδομένων και προτείνει νέες πρωτότυπες δομές καταλόγων. Πιο συγκεκριμένα, στα πλαίσια της διατριβής αυτής μελετώ- νται και χωροχρονικά ερωτήματα (ερωτήματα πλησιέστερου γείτονα, απλού και αυξητικού, ερωτήματα παραθύρου και χρονικής στιγμής), τα οποία είναι απαραίτητα για την προσπέλα- ση των καινούριων δομών καταλόγων. Οι κυριότερες συνεισφορές της διατριβής αυτής παρουσιάζονται εκτενώς παρακάτω: • Μία πρώτη συνεισφορά αποτελεί ένας αλγόριθμος, ο οποίος προτάθηκε για τον υπολο- γισμό του ερωτήματος πλησιέστερου γείτονα σε βάσεις δεδομένων κινούμενων αντικει- μένων. Ο αλγόριθμος αυτός, συγκρίθηκε με μία ήδη υπάρχουσα μέθοδο, που βασίζεται όμως σε συνεχή επανάληψη. Από τα πειράματα προέκυψε ότι, ο καινούριος αλγόριθμος παρουσιάζει πολύ καλύτερη απόδοση σε σχέση με τον ήδη υπάρχοντα. • Μία επόμενη συνεισφορά είναι μία μέθοδος, που είναι ικανή να απαντάει σε αυξητικά ερωτήματα πλησιέστερου γείτονα σε βάσεις δεδομένων κινούμενων αντικειμένων. Το αυξητικό αυτό ερώτημα δεν έχει αντιμετωπιστεί, στις χωροχρονικές βάσεις δεδομένων. Για το λόγο αυτό, το υλοποιούμε για πρώτη φορά και το συγκρίνουμε με αυτό, που υ- πάρχει ήδη στις χωρικές βάσεις δεδομένων. Για άλλη μία φορά ο καινούριος αλγόριθμος ξεπερνάει τον παλιό. • Στη συνέχεια, επεκτείνεται μία ήδη υπάρχουσα δομή καταλόγου βασισμένη στο τετραδι- κό δέντρο και για τη χωροχρονική κίνηση των αντικειμένων. Η μέθοδος αυτή συγκρίνε- ται με μία άλλη, που είναι βασισμένη και αυτή στο τετραδικό δέντρο. Η σύγκριση πραγ- ματοποιείται για ερωτήματα παραθύρου, στα οποία η καινούρια δομή ξεπερνάει κατά πολύ την παλιά. • Έπειτα, η δομή της προηγούμενης εργασίας συγκρίνεται με μία; δομή, που δε βασίζεται στο τετραδικό δέντρο και η κίνηση των αντικειμένων είναι παρελθοντική. Τα ερωτήματα τα οποία υλοποιούνται είναι και χρονικής στιγμής και παραθύρου. Για όλα τα πειράματα, τα οποία πραγματοποιούνται η καινούρια μέθοδος ξεπερνάει αυτήν, που δε βασίζεται στο τετραδικό δέντρο. • Ολοκληρώνοντας, μία τελευταία συνεισφορά αποτελεί η σύγκριση της δομής της προη- γούμενης εργασίας με μία άλλη δομή, που δε βασίζεται στο τετραδικό δέντρο. Επιπλέον, η κίνηση των αντικειμένων είναι και παρελθοντική και μελλοντική, ενώ τα ερωτήματα είναι τόσο παραθύρου όσο και χρονικής στιγμής. Για άλλη μία φορά η καινούρια δομή ξεπερνάει την παλιά και ήδη υπάρχουσα. Όπως έχει ήδη αναφερθεί, το βασικό αντικείμενο της παρούσας διατριβής είναι η επε- ξεργασία και η διαχείριση των χωροχρονικών βάσεων δεδομένων. Στο κοντινό μέλλον, αναμένεται να υπάρξει μία πληθώρα εφαρμογών, οι οποίες θα βασί- ζονται στη γεωγραφική θέση των αντικειμένων. Όλες αυτές οι εφαρμογές ονομάζονται συλ- λογικά υπηρεσίες βασισμένες στην θέση (location-based services). Οι παραπάνω εφαρμογές αναμένεται να αποτελέσουν ένα ευρύτατο φάσμα, στο οποίο μπορούν να βρουν εφαρμογή οι βάσεις δεδομένων κινούμενων αντικειμένων.