Επεξεργασια Ερωτηματων Διαρκειας Σε Ρευματα Κινουμενων Αντικειμενων

Abstract

Πυρήνας της εργασίας είναι η μελέτη και υλοποίηση αλγορίθμων που επιτρέπουν απαντήσεις σε πραγματικό χρόνο για πολλαπλά ερωτήματα διαρκείας σχετικά με την τρέχουσα θέση μεγάλου αριθμού κινούμενων αντικειμένων. Ως βασική υπόθεση εργασίας θεωρείται ότι ένα ρεύμα δεδομένων δημιουργείται παρακολουθώντας την κίνηση πολλών σημειακών αντικειμένων, τα οποία ανανεώνουν συχνά το στίγμα τους και το αποστέλλουν τακτικά σε έναν κεντρικό επεξεργαστή. Για την επίτευξη γρήγορων ενημερώσεων, οι θέσεις των αντικειμένων δεικτοδοτούνται σε πλέγμα με βάση την τεχνική του κατακερματισμού. Σε ό,τι αφορά την επεξεργασία, αναπτύχθηκαν αλγόριθμοι με τη μορφή τελεστών στο ρεύμα, οι οποίοι αποτιμούν πολλαπλά κινούμενα ερωτήματα περιοχής και ερωτήματα k-εγγύτερων γειτόνων. Ένα ερώτημα περιοχής εντοπίζει διαρκώς τα αντικείμενα που κινούνται σε μια δοσμένη περιοχή, που για λόγους απλοποίησης θεωρείται ορθογώνια. Η αποτίμησή τους γίνεται με την τεχνική της από κοινού επεξεργασίας, βάσει της οποίας τα ερωτήματα που τέμνουν ένα κελί του πλέγματος συνδέονται χωρικά με τα αντικείμενα που βρίσκονται σε αυτό. Ένα ερώτημα εγγύτερων γειτόνων εντοπίζει τα k αντικείμενα πλησίον ενός δοσμένου σημειακού αντικειμένου. Η αποτίμηση τέτοιων ερωτημάτων έγινε με την μέθοδο της σπειροειδούς διαμέρισης (Conceptual Partitioning Monitoring), διαμερίζοντας τον χώρο γύρω από το ερώτημα σε επάλληλες λωρίδες κελιών σε σπειροειδή σχηματισμό. Η τεχνική αυτή εκμεταλλεύεται την ιδιότητα της ελάχιστης απόστασης μεταξύ ενός σημείου και ενός πολυγώνου: αν η ελάχιστη απόσταση του ερωτήματος από ένα κελί ή μια λωρίδα είναι μεγαλύτερη από την απόσταση του k-στού εγγύτερου γείτονα, τότε εντός του κελιού ή της λωρίδας αποκλείεται να υπάρχει άλλο σημείο πλησιέστερα από τον ήδη υπολογισμένο k-στό γείτονα. Η μέθοδος εξετάζει το βέλτιστο σύνολο κελιών και με τη διαμέριση επιταχύνει την αναζήτησή τους. Οι δύο αλγόριθμοι αποτιμούν αποδοτικά κυμαινόμενο πλήθος ενεργών ερωτημάτων σε κλιμακούμενο πλήθος αντικειμένων. Οι επιδόσεις τους μετρήθηκαν πειραματικά και ανέδειξαν την επάρκειά τους ως προς τον χειρισμό πολλαπλών ερωτημάτων διαρκείας. Οι δύο χωροχρονικοί τελεστές είναι δυνατόν να ολοκληρωθούν σε ένα ευρύτερο ενιαίο μηχανισμό επεξεργασίας, αφού χρησιμοποιούν αποτελεσματικά το ίδιο πλέγμα κατάτμησης του χώρου.