Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/9C5C98F0-8EAB-4B59-8913-D6FDCB1603CE | - |
| Identifier | https://doi.org/10.26233/heallink.tuc.66133 | - |
| Language | en | - |
| Extent | 1.2 kilobytes | en |
| Title | Data mining algorithms over Akka and Storm frameworks | en |
| Title | Αλγόριθμοι εξόρυξης δεδομένων στα συστήματα Akka και Storm | el |
| Creator | Karatza Dimitra | en |
| Creator | Καρατζα Δημητρα | el |
| Contributor [Thesis Supervisor] | Deligiannakis Antonios | en |
| Contributor [Thesis Supervisor] | Δεληγιαννακης Αντωνιος | el |
| Contributor [Committee Member] | Garofalakis Minos | en |
| Contributor [Committee Member] | Γαροφαλακης Μινως | el |
| Contributor [Committee Member] | Lagoudakis Michael | en |
| Contributor [Committee Member] | Λαγουδακης Μιχαηλ | el |
| Publisher | Πολυτεχνείο Κρήτης | el |
| Publisher | Technical University of Crete | en |
| Academic Unit | Technical University of Crete::School of Electrical and Computer Engineering | en |
| Academic Unit | Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών | el |
| Content Summary | 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. Accuracy guarantees are typically made in terms of those parameters (support, error, probability of failure) meaning that the error in extracting those frequent items is within a factor of 1+error of the true items’ frequency with probability at least 1-δ. The space will depend on these parameters. 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 models. Those two frameworks have a completely different architecture which are deeply explained in the current diploma thesis. The crucial difference is that in Storm framework data stream is processed synchronously while in Akka framework data stream is processed asynchronously. 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. The data set which is used in order to make our experiments contains two weeks HTTP requests to ClarkNet server. ClarkNet is a full Internet access provider for the Metro Baltimore –Washington DC area. | en |
| Content Summary | Η επεξεργασία δεδομένων με αποτελεσματικό τρόπο έχει μονοπωλήσει, κατά τις τελευταίες δεκαετίες, το ενδιαφέρον των επιστημόνων λόγω του αυξανόμενου όγκου διαθέσιμων δεδομένων που αφορούν ποικίλες εφαρμογές της επιστήμης των υπολογιστών. Ειδικότερα, η εποπτεία ταχύτατα μεταβαλλόμενων ροών δεδομένων σε πραγματικό χρόνο έχει αναδειχθεί ως ένα σημαντικό ζήτημα στη διαχείριση δεδομένων. Σχετικές εφαρμογές αφορούν την ανάλυση της κίνησης στο διαδίκτυο, την καταγραφή τηλεφωνικών κλήσεων, τη διαφήμιση στο 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. | el |
| Type of Item | Διπλωματική Εργασία | el |
| Type of Item | Diploma Work | en |
| License | http://creativecommons.org/licenses/by/4.0/ | en |
| Date of Item | 2016-07-26 | - |
| Date of Publication | 2016 | - |
| Subject | Streaming algorithms | en |
| Subject | Data mining algorithms | en |
| Subject | Distributed systems | en |
| Bibliographic Citation | Dimitra Karatza, "Data mining algorithms over Akka and Storm frameworks", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2016 | en |
| Bibliographic Citation | Δήμητρα Καρατζά, "Αλγόριθμοι εξόρυξης δεδομένων στα συστήματα Akka και Storm", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2016 | el |
Copyright © DIAS 2013
