Clustering streaming data in distributed environments based on belief propagation techniques

Abstract

Σκοπός της παρούσας εργασίας είναι να εξετάσει ένα σύγχρονο πρόβλημα στον τομέα της ανάκτησης πληροφορίας, την ομαδοποίηση ροών δεδομένων σε κατανεμημένο σύστημα. Αυτό το πρόβλημα ανήκει στη κατηγορία προβλημάτων μεγάλων δεδομένων, το οποίο σημαίνει ότι σε αυτά τα δεδομένα δεν μπορούν να εφαρμοστούν παραδοσιακές τεχνικές, λογισμικό ή βάσεις δεδομένων για να πιαστούν, να επεξεργαστούν και να αναλυθούν χωρίς μεγάλη καθυστέρηση και για αυτό τον λόγο πρέπει να χρησιμοποιηθεί παράλληλη επεξεργασία. Επιπλέον όταν αυτά τα δεδομένα είναι με την μορφή ροών δεδομένων υπάρχουν ακόμα περισσότερες προκλήσεις που πρέπει να αντιμετωπιστούν. Από την άλλη μεριά αν λυθούν αυτά τα προβλήματα, η ανάλυση των ροών δεδομένων δίνει πολλά πλεονεκτήματα, όπως το να υπάρχει εικόνα για τα δεδομένα σε πραγματικό χρόνο το οποίο μπορεί να βοηθήσει στην αντιμετώπιση διαφόρων καταστάσεων σε πραγματικό χρόνο. Η συνεχής και κατανεμημένη μορφή που παράγονται τα δεδομένα από πλήθος συσκευών μαζί με το μεγάλο μέγεθός τους και περιορισμούς όπως ο χώρος αποθήκευσης και ο φόρτος δικτύου καθιστούν ένα πολύ δύσκολο πρόβλημα την ομαδοποίηση ροών δεδομένων. Στην παρούσα εργασία, προσπαθούμε να επιλύσουμε το πρόβλημα χρησιμοποιώντας μια προσέγγιση δύο επιπέδων ομαδοποίησης. Στο πρώτο επίπεδο, καθώς τα δεδομένα έρχονται σε πολλούς κατανεμημένους κόμβους, σε κάθε περίοδο του χρόνου, κάθε κόμβος ομαδοποιεί τα δεδομένα και εξάγει την πιο χρήσιμη πληροφορία από τα δεδομένα (exemplars) η οποία θα σταλεί σε έναν κεντρικό κόμβο, για να εκτελέσει με την σειρά του το δεύτερο επίπεδο ομαδοποίησης για να εντοπίσει τα ολικά cluster από όλα τα δεδομένα που κατέφθασαν σε κάθε κόμβο. Οι exemplars που υπολογίστηκαν στον κεντρικό κόμβο, θα σταλούν πίσω σε κάθε κόμβο για να αναθεωρήσουν το βάρος του κάθε exemplar και αυτή η διαδικασία θα συνεχιστεί σε όλη την διάρκεια της ροής δεδομένων.