Επεξεργασία Χωρικών Ρευμάτων Δεδομένων Με Διαγράμματα Voronoi

Abstract

Αντικείμενο της διπλωματικής εργασίας είναι η διερεύνηση της εφαρμογής των διαγραμμάτων Voronoi για την διαχείριση χωρικών ρευμάτων δεδομένων (spatial data streams) τα οποία προκύπτουν λ.χ. από τις καταγραφές αισθητήρων ή δεκτών GPS. Τα χωρικά ρεύματα δεδομένων δημιουργούνται από την καταγραφή των σημειακών θέσεων πολλών κινούμενων αντικειμένων τα οποία ανανεώνουν συχνά το στίγμα τους. Τα δεδομένα λοιπόν καταφθάνουν με μεγάλο και δυναμικά μεταβλητό ρυθμό σε πραγματικό χρόνο ,οπότε για την επεξεργασία τους απαιτείται η χρήση μόνο της κύριας μνήμης. Ενδεχόμενη αποθήκευσή τους θα επέφερε ανεπιθύμητες καθυστερήσεις, γι' αυτό και δεν ενδείκνυται η χρήση συμβατικών χωρικών βάσεων δεδομένων. Ειδικότερα, μελετάται το ζήτημα της ταχείας επεξεργασίας ερωτημάτων εγγύτερου γείτονα (nearest neighbor queries) για στατικές εστίες, καθώς και ο online υπολογισμός μεμονωμένων κελιών Voronoi για δυναμικά κινούμενες εστίες. Η μελέτη των διαγραμμάτων Voronoi στατικών αντικειμένων, αποτέλεσε χρήσιμο υπόβαθρο στην κατανόηση της εφαρμογής γεωμετρικών αλγορίθμων στο πεδίο των βάσεων δεδομένων. Ο αλγόριθμος του Fortune αξιοποιήθηκε για την κατασκευή του διαγράμματος Voronoi ενός συνόλου στατικών αντικειμένων και την απάντηση ερωτημάτων εγγύτερου γείτονα για ένα ρεύμα κινούμενων αντικειμένων επί αυτού. Για την περίπτωση των μεμονωμένων κελιών προτείνεται πρωτότυπος αλγόριθμος, που υπολογίζει και ανανεώνει ένα προσεγγιστικό κελί Voronoi k-τάξεως, χρησιμοποιώντας ένα ρεύμα κινούμενων σημείων ως είσοδο. Ο αλγόριθμος που προτείνεται επιλέχθηκε να είναι προσεγγιστικός και παρέχει μια κομψή και εύκολα υλοποιήσιμη λύση στο πρόβλημα αναζήτησης εγγύτερου γείτονα για τις περιπτώσεις ταυτόχρονης και ασύγχρονης ανανέωσης των θέσεων των αντικειμένων. Ο υπολογισμός των προσεγγιστικών κελιών τον καθιστά κατάλληλο για προβλήματα πραγματικού χρόνου, όπου η ακρίβεια στην απάντηση μπορεί να θυσιαστεί για χάρη της γρήγορης απόκρισης.