Monitoring and mining distributed data streams

Abstract

Many modern streaming applications, such as online analysis of financial, network, sensor and other forms of data are inherently distributed in nature. Due to the distributed nature of data production in the aforementioned scenarios, the major challenge confronted by algorithms dealing with their manipulation is to reduce communication.This happens because the central collection of data is not feasible in large-scale applications.An important query type that is of the essence in such applications involves a continuous check on the position of a given (arbitrarily complex) function f with respect to a posed threshold T. This monitoring demand may be explicitly placed at the core of applications mission or implicitly stand as an operational component. One approach to achieve the desired communication reduction is to decompose the monitoring problem into local constraints that can be disseminated to the geographically dispersed sites. According to that approach, each site in the network will then have to consult these constraints upon the local dataset is altered. Collecting the data centrally is only required when the local constraint of at least one site is violated [103].However, the decomposition of the central monitoring problem into a set of local constraints is not always effective. In fact, it may complicate the monitoring processes and uncontrollably sacrifice accuracy when functioning over generic network infrastructures where message losses, death or reorganization of nodes affects the network formation.A second approach of performing the monitoring is to allow continuous communication between the necessary network parties but attempt to reduce the bandwidth consumption by applying reduction techniques on the data under transmission. In that, we allow efficient derivation of answers by controllably compromising accuracy. Regarding the first approach, we focus on monitoring (non-linear) complex functions over distributed data streams. More precisely, in our work [42], we generalize the geometric monitoring approach initially presented in [103] by proposing the adoption of local predictors [22] to be used during the distributed tracking. As regards the second of the previously discussed approaches and propose an outlier detection framework,namely TACO [44, 45], that trades bandwidth for accuracy in a straightforward manner and supports various similarity metrics (monitored functions of interest).Eventually, we further elaborate on extensions of the rationales utilized in the previously mentioned approaches. We concentrate on trajectory data streams and perform distributed Representative Trajectory monitoring over a number of monitored objects utilizing the concept of predictors [42]. Additionally, we exploit the properties of the monitored similarity measures used in [44, 45], in the context of detecting movement pattern alterations over streaming movement data [116].

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