Συντάχθηκε 22-07-2016 07:51
από Esthir Gelasaki
Email συντάκτη: egelasaki<στο>tuc.gr
Ενημερώθηκε:
-
Ιδιότητα: υπάλληλος.
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΔΗΜΗΤΡΑΣ ΚΑΡΑΤΖΑ
με θέμα
Αλγόριθμοι Εξόρυξης Δεδομένων στα Συστήματα Akka και Storm
Data Mining Algorithms over Akka and Storm Frameworks
Εξεταστική Επιτροπή
Αναπληρωτής Καθηγητής Αντώνιος Δεληγιαννάκης (επιβλέπων)
Καθηγητής Μίνως Γαροφαλάκης
Αναπληρωτής Καθηγητής Μιχαήλ Λαγουδάκης
Abstract
Efficient processing over massive data sets has taken an increasing importance in the last few decades due to the growing availability of large volumes of data in a variety of applications in computer science. In particular, monitoring huge and rapidly changing streams of data that arrive online has emerged as an important data management problem. Relevant applications include analyzing network traffic, telephone call records, internet advertising and data bases. For these reasons, the streaming model has recently received a lot of attention. This model differs from computation over traditional stored data sets since algorithms must process their input by making only one pass over it, using only a limited amount of working memory. The streaming model applies to settings where the size of the input far exceeds the size of the main memory available and the only feasible access to the data is by making one pass over it.
Typical streaming algorithms use space at most polylogarithmic in the length of input stream. Using linear space motivates the design for summary data structures with small memory footprints, also known as synopses. Algorithms such as Misra Gries, Lossy Counting, Sticky Sampling and Space Saving use parameters support, error and probability of failure, which are specified by the user, in order to extract the items that exceed some threshold (support) from an unbounded data stream.
Since we make only one pass over the unbounded data stream we have to use suitable computation systems. We introduce Storm and Akka frameworks which are both real-time, distributed, fault-tolerant frameworks. We execute Misra Gries, Lossy Counting, Sticky Sampling and Space Saving algorithms in those two frameworks in a multi node cluster tuning the topologies in order to optimize performance. We observe throughput, the number of processed items in input data set per second. Our goal is to compare the algorithms’ behavior in two frameworks.
Περίληψη
Η επεξεργασία δεδομένων με αποτελεσματικό τρόπο έχει μονοπωλήσει, κατά τις τελευταίες δεκαετίες, το ενδιαφέρον των επιστημόνων λόγω του αυξανόμενου όγκου διαθέσιμων δεδομένων που αφορούν ποικίλες εφαρμογές της επιστήμης των υπολογιστών. Ειδικότερα, η εποπτεία ταχύτατα μεταβαλλόμενων ροών δεδομένων σε πραγματικό χρόνο έχει αναδειχθεί ως ένα σημαντικό ζήτημα στη διαχείριση δεδομένων. Σχετικές εφαρμογές αφορούν την ανάλυση της κίνησης στο διαδίκτυο, την καταγραφή τηλεφωνικών κλήσεων, τη διαφήμιση στο Internet και τις βάσεις δεδομένων. Για τους παραπάνω λόγους, υπάρχει μεγάλο ενδιαφέρον για το μοντέλο streaming. Πρόκειται για ένα διαφορετικό τρόπο διαχείρισης των αποθηκευμένων, με παραδοσιακό τρόπο δεδομένων. Το μοντέλο streaming χρησιμοποιεί αλγορίθμους οι οποίοι επεξεργάζονται, με ένα μόνο πέρασμα, τα δεδομένα στην πηγή τους καταναλώνοντας λίγη μνήμη, ώστε το μοντέλο αυτό να αναδεικνύεται ως μοναδική εφικτή λύση όταν ο όγκος των δεδομένων ξεπερνά κατά πολύ το μέγεθος της διαθέσιμης μνήμης .
Οι τυπικοί αλγόριθμοι που χρησιμοποιούνται στο εν λόγω μοντέλο streaming έχουν πολυλογαριθμική χωρική πολυπλοκότητα στην επεξεργασία της ροής δεδομένων. Η γραμμική χωρική πολυπλοκότητα αποτελεί κίνητρο για τον σχεδιασμό data synopsis. Ειδικότερα, αντί να αποθηκεύεται ο μεγάλος όγκος δεδομένων προς επεξεργασία, αποθηκεύονται μόνο τα γενικά χαρακτηριστικά της ροής δεδομένων σε μια δομή. Οι αλγόριθμοι του μοντέλου streaming είναι οι εξής: Misra Gries, Lossy Counting, Sticky Sampling, και Space Saving. Οι εν λόγω αλγόριθμοι χρησιμοποιούν κάποιες παραμέτρους όπως support, error και probability of failure οι οποίες καθορίζονται απ’ τον χρήστη προκειμένου να παραχθεί το υποσύνολο των δεδομένων (από τη μη πεπερασμένη ροή δεδομένων) το οποίο υπερβαίνει κάποιο όριο (threshold).
Δεδομένου ότι οι streaming αλγόριθμοι επεξεργάζονται τα δεδομένα της ροής μόνο μια φορά οφείλουμε να χρησιμοποιήσουμε ανάλογα υπολογιστικά συστήματα. Τέτοια συστήματα είναι το Storm, καθώς και το Akka τα οποία χρησιμοποιούνται για real-time ανάλυση δεδομένων. Ακόμα, είναι κατανεμημένα, και έχουν το χαρακτηριστικό ότι έχουν μεγάλη ανοχή λάθους στην ποιότητα και ακρίβεια των αποτελεσμάτων που εξάγουν. Υλοποιούνται και εκτελούνται οι αλγόριθμοι Misra Gries, Lossy Counting, Sticky Sampling, και Space Saving και στα συστήματα Storm και Akka σε cluster με πολλούς κόμβους (nodes). Στόχος της εργασίας είναι η βελτιστοποίηση της απόδοσης των αλγορίθμων σε σχέση με τον τρόπο που εκτελούνται στον cluster. Η απόδοση καταγράφεται με βάση τον ρυθμό προσπέλασης των δεδομένων στη μορφή των tuples ανά δευτερόλεπτο (throughput).
Τόπος: Λ - Κτίριο Επιστημών/ΗΜΜΥ, 137Π-39,-38
Έναρξη: 25/07/2016 11:00
Λήξη: 25/07/2016 12:00
