Monitoring and mining distributed data streams

Abstract

Πολλές σύγχρονες εφαρμογές ρευμάτων δεδομένων, όπως ανάλυση οικονομικών, δικτυακών, αισθητήρων και άλλων τύπων δεδομένων είναι κατανεμημένης φύσεως. Εξαιτίας της κατανεμημένης φύσης παραγωγής των δεδομένων στα προαναφερθέντα σενάρια, η μεγαλύτερη πρόκληση που αντιμετωπίζουν οι αλγόριθμοι που καλούνται να τα διαχειριστούν είναι η μείωση του κόστους επικοινωνίας. Αυτό συμβαίνει λόγω του ότι η κεντρική συλλογή των δεδομένων σε εφαρμογές μεγάλης κλίμακας, οδηγεί σε αυξημένη κατανάλωση του εύρους ζώνης των συνδέσμων επικοινωνίας οι οποίοι καθίστανται μη λειτουργικοί. Ένας σημαντικός τύπος επερωτήσεων που έχει ιδιαίτερο νόημα σε τέτοιες εφαρμογές αφορά το συνεχή έλεγχο της τοποθέτησης της τιμής μιας δοθείσας (οσοδήποτε πολύπλοκης) συνάρτησης f σε σχέση με κάποιο τεθέν κατώφλι Τ. Αυτή η απαίτηση παρακολούθησης ενδέχεται να τίθεται ρητά στον πυρήνα της αποστολής κάποιας εφαρμογής, ή να αποτελεί λειτουργικό της συστατικό. Μια προσέγγιση για να επιτύχει κανείς την επιθυμητή μείωση στην επικοινωνία κατά την παρακολούθηση της f, είναι η αποσύνθεση του προβλήματος της παρακολούθησης των ρευμάτων δεδομένων, σε τοπικούς περιορισμούς που μπορούν να δοθούν στις, γεωγραφικά κατανεμημένες, πηγές δεδομένων. Κάθε πηγή δεδομένων συμβουλεύεται αυτούς τους περιορισμούς σε κάθε αλλαγή του ρεύματος δεδομένων που καταφθάνει τοπικά. Η κεντρική συλλογή των δεδομένων χρειάζεται μόνο όταν παραβιάζεται ο περιορισμός που έχει τεθεί τοπικά σε κάποια πηγή. Ωστόσο, η αποσύνθεση του προβλήματος της παρακολούθησης σε σύνολο τοπικών περιορισμών δεν είναι πάντα αποτελεσματική. Μπορεί να περιπλέξει τη διαδικασία παρακολούθησης και να θυσιάζει την ακρίβεια της όταν λειτουργεί σε λιγότερο απλές δικτυακές υποδομές όπου απώλειες μηνυμάτων και αναδιοργάνωση των κόμβων του δικτύου μπορεί να λάβουν χώρα.Μια δεύτερη προσέγγιση είναι να επιτραπεί η συνεχείς επικοινωνία μεταξύ των απαραίτητων δικτυακών μερών αλλά να γίνει προσπάθεια μείωσης της κατανάλωσης του αντίστοιχου εύρους ζώνης με εφαρμογή τεχνικών μείωσης των δεδομένων που πρόκειται να μεταδοθούν, θυσιάζοντας μέρος της ακρίβειας με ελεγχόμενο τρόπο. Σε ότι αφορά την πρώτη από τις παραπάνω προσεγγίσεις, επικεντρωνόμαστε στην παρακολούθηση πολύπλοκων συναρτήσεων επί κατανεμημένων ρευμάτων δεδομένων. Πιο συγκεκριμένα, στην εργασία μας [42], γενικεύουμε την προσέγγιση της γεωμετρικής παρακολούθησης που αρχικά παρουσιάστηκε στο [103], προτείνοντας την υιοθέτηση τοπικών μοντέλων πρόβλεψης [22] κατάλληλων να χρησιμοποιηθούν κατα την κατανεμημένη παρακολούθηση. Αναφορικά με τη δεύτερη από τις προαναφερθείσες προσεγγίσεις προτείνουμε ένα πλαίσιο προσδιορισμού ακραίων τιμών, με όνομα TACO [44, 45], το οποίο είναι ικανό να συναλλάσει ευθέως την κατανάλωση εύρους ζώνης με την ακρίβεια στον προσδιορισμό των ακραίων τιμών και μπορεί να ενσωματώσει πληθώρα μέτρων ομοιότητας (παρακολούθηση συναρτήσεων που μας ενδιαφέρουν).Εν κατακλείδι, αναφερόμαστε σε επεκτάσεις των προηγούμενων λογικών. Επικεντρωνόμενοι σε ρεύματα δεδομένων τροχιών κινούμενων αντικειμένων, πραγματοποιούμε κατανεμημένη παρακολούθηση Αντιπροσωπευτικών Τροχιών επί ενός αριθμού παρακολουθούμενων, κινούμενων αντικειμένων χρησιμοποιώντας έννοιες των μοντέλων πρόβλεψης [42]. Επιπλέον, εκμεταλλευόμαστε τις ιδιότητες των μέτρων ομοιότητας που χρησιμοποιήθηκαν στα [44, 45], για τον εντοπισμό αλλαγών στο μοτίβο κινούμενων αντικειμένων, μέσω των αντίστοιχων ρευμάτων δεδομένων του τρόπου κίνησής τους [116]