Αναζήτηση

Πλοήγηση

• Κοινότητες
• Συγγραφείς
• Έτος
• Τίτλοι
• Θέματα

Ο Χώρος μου

• Είσοδος

Αλγόριθμοι εξόρυξης δεδομένων στα συστήματα Akka και Storm

Karatza Dimitra

Πλήρης Εγγραφή

---

Περίληψη

Η επεξεργασία δεδομένων με αποτελεσματικό τρόπο έχει μονοπωλήσει, κατά τις τελευταίες δεκαετίες, το ενδιαφέρον των επιστημόνων λόγω του αυξανόμενου όγκου διαθέσιμων δεδομένων που αφορούν ποικίλες εφαρμογές της επιστήμης των υπολογιστών. Ειδικότερα, η εποπτεία ταχύτατα μεταβαλλόμενων ροών δεδομένων σε πραγματικό χρόνο έχει αναδειχθεί ως ένα σημαντικό ζήτημα στη διαχείριση δεδομένων. Σχετικές εφαρμογές αφορούν την ανάλυση της κίνησης στο διαδίκτυο, την καταγραφή τηλεφωνικών κλήσεων, τη διαφήμιση στο Internet και τις βάσεις δεδομένων. Για τους παραπάνω λόγους, υπάρχει μεγάλο ενδιαφέρον για το μοντέλο streaming. Πρόκειται για ένα διαφορετικό τρόπο διαχείρισης των αποθηκευμένων, με παραδοσιακό τρόπο δεδομένων. Το μοντέλο streaming χρησιμοποιεί αλγορίθμους οι οποίοι επεξεργάζονται, με ένα μόνο πέρασμα, τα δεδομένα στην πηγή τους καταναλώνοντας λίγη μνήμη, ώστε το μοντέλο αυτό να αναδεικνύεται ως μοναδική εφικτή λύση όταν ο όγκος των δεδομένων ξεπερνά κατά πολύ το μέγεθος της διαθέσιμης μνήμης .Οι τυπικοί αλγόριθμοι που χρησιμοποιούνται στο εν λόγω μοντέλο streaming έχουν πολυλογαριθμική χωρική πολυπλοκότητα στην επεξεργασία της ροής δεδομένων. Η γραμμική χωρική πολυπλοκότητα αποτελεί κίνητρο για τον σχεδιασμό data synopsis. Ειδικότερα, αντί να αποθηκεύεται ο μεγάλος όγκος δεδομένων προς επεξεργασία, αποθηκεύονται μόνο τα γενικά χαρακτηριστικά της ροής δεδομένων σε μια δομή. Οι αλγόριθμοι του μοντέλου streaming είναι οι εξής: Misra Gries, Lossy Counting, Sticky Sampling, και Space Saving. Οι εν λόγω αλγόριθμοι χρησιμοποιούν κάποιες παραμέτρους όπως support, error και probability of failure οι οποίες καθορίζονται απ’ τον χρήστη προκειμένου να παραχθεί το υποσύνολο των δεδομένων (από τη μη πεπερασμένη ροή δεδομένων) το οποίο υπερβαίνει κάποιο όριο (threshold). Ειδικότερα, το ζήτημα είναι να εξάγουμε τα δεδομένα (items) απ’ την ροή τα οποία εμφανίζονται πιο συχνά σε σχέση με τα υπόλοιπα. Η ακρίβεια στην εξαγωγή των δεδομένων αυτών σχετίζεται άμεσα με τις παραπάνω παραμέτρους με πιθανότητα λάθους το πολύ 1−𝛿 σε σχέση με τη πραγματική συχνότητα εμφάνισης των δεδομένων.Δεδομένου ότι οι streaming αλγόριθμοι επεξεργάζονται τα δεδομένα της ροής μόνο μια φορά οφείλουμε να χρησιμοποιήσουμε ανάλογα υπολογιστικά συστήματα. Τέτοια συστήματα είναι το Storm, καθώς και το Akka τα οποία χρησιμοποιούνται για real-time ανάλυση δεδομένων. Ακόμα, είναι κατανεμημένα, και έχουν το χαρακτηριστικό ότι έχουν μεγάλη ανοχή λάθους στην ποιότητα και ακρίβεια των αποτελεσμάτων που εξάγουν. Τα δύο αυτά συστήματα, τα οποία ονομάζονται αλλιώς frameworks έχουν τελείως διαφορετική αρχιτεκτονική από τα συστήματα που χρησιμοποιούνται για την επεξεργασία δεδομένων τα οποία είναι ήδη αποθηκευμένα σε κάποια βάση δεδομένων (batch processing). Η αρχιτεκτονική τους αναλύεται σε βάθος στη παρούσα διπλωματική εργασία. Η βασική διαφορά των δύο αυτών συστημάτων έγκειται στο ότι το Storm επεξεργάζεται τα δεδομένα με σύγχρονο τρόπο σε αντίθεση με το Akka σύστημα το οποίο επεξεργάζεται τα δεδομένα με ασύγχρονο τρόπο.Στην εργασία αυτή υλοποιούνται και εκτελούνται οι αλγόριθμοι Misra Gries, Lossy Counting, Sticky Sampling, και Space Saving και στα συστήματα Storm και Akka σε cluster με πολλούς κόμβους (nodes). Στόχος της εργασίας είναι η βελτιστοποίηση της απόδοσης των αλγορίθμων σε σχέση με τον τρόπο που εκτελούνται στον cluster. Η απόδοση καταγράφεται με βάση τον ρυθμό προσπέλασης των δεδομένων στη μορφή των tuples ανά δευτερόλεπτο (throughput). Ένας ακόμη στόχος της παρούσας εργασίας είναι η σύγκριση των δύο αυτών συστημάτων Storm και Akka σε σχέση με την αρχιτεκτονική αλλά και με τη συμπεριφορά τους καθώς εκτελούνται στον cluster.Η ροή δεδομένων που χρησιμοποιείται στην εργασία αυτή, προκειμένου να εκτελεστούν τα πειράματα, είναι ένα data set το οποίο περιέχει HTTP requests διάρκειας δύο εβδομάδων στον Server ClarkNet. Ο Server ClarkNet είναι ένας provider που χρησιμοποιείται στο Metro της περιοχής Baltimore –Washington DC.

Διαθέσιμα αρχεία

Υπηρεσίες