Συντάχθηκε 29-09-2026 16:00
Τόπος:
Σύνδεσμος τηλεδιάσκεψης
Έναρξη: 01/10/2026 16:00
Λήξη: 01/10/2026 17:00
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
Βασιλείου Κουτσοβασίλη
με θέμα
Υλοποίηση ενός Καθολικού Σκίτσου για Συχνά Δεδομένα και Συχνοτικές Στιγμές στο Apache Flink
Implementation of a Universal Sketch for Heavy Hitters and Frequency Moments in Apache Flink
Εξεταστική Επιτροπή
Καθηγητής Αντώνιος Δεληγιαννάκης (Σχολή ΗΜΜΥ, Επιβλέπων)
Αναπληρωτής Καθηγητής Βασίλειος Σαμολαδάς (Σχολή ΗΜΜΥ)
Καθηγητής Μίνως Γαροφαλάκης (Σχολή ΗΜΜΥ)
Περίληψη
Στον τομέα της επεξεργασίας ροών δεδομένων, υπάρχουν δύο επικρατέστερα μοντέλα: το μοντέλο μόνο εισαγωγής και το μοντέλο turnstile, το οποίο επιτρέπει τόσο την εισαγωγή όσο και την διαγραφή στοιχείων. Στο πλαίσιο του turnstile μοντέλου με «φραγμένες» διαγραφές, όπου ο αριθμός των διαγραφών είναι περιορισμένος σε σχέση με τις εισαγωγές, ο υπολογισμός καθολικών μετρικών ροών καθίσταται ιδιαίτερα απαιτητικός, ειδικά υπό περιορισμούς μνήμης και την ανάγκη για επεξεργασία σε πραγματικό χρόνο. Οι καθολικές μετρικές αφορούν ταυτόχρονη εκτίμηση πολλαπλών στατιστικών δεικτών, συμπεριλαμβανομένης της ανά-στοιχείο συχνότητας, συχνών δεδομένων και συχνοτικών στιγμών. Σε αυτό το πλαίσιο προκύπτουν δύο κύριες προκλήσεις. Πρώτον, οι περισσότερες προηγούμενες μέθοδοι ανίχνευσης συχνών δεδομένων δεν μπορούν να εξασφαλίσουν «φραγμένο» σφάλμα ανίχνευσης όταν υπάρχουν συμβάντα διαγραφής. Δεύτερον, δεν υπάρχει ακόμη προηγούμενη εργασία για την ανά-κλειδί εκτίμηση συχνοτικών στιγμών υπό το turnstile μοντέλο, ειδικά σε πραγματικό χρόνο. Η παρούσα διπλωματική εργασία παρουσιάζει μια ανεξάρτητη υλοποίηση σε Java και εμπειρική αξιολόγηση του Αφαιρούμενου Επαυξημένου Σκίτσου (RAS) και του Αφαιρούμενου Καθολικού Σκίτσου (RUS), ενισχυμένο με έναν Εκτιμητή Στιγμών Πραγματικού Χρόνου (OME). Το πλαίσιο αυτό προτάθηκε αρχικά από τους Liang Zheng, Qingjun Xiao και Xuyuan Cai το 2024, με στόχο την αντιμετώπιση των δύο αυτών προκλήσεων μέσω σχεδιασμού ενός συμπιεσμένου μετρητή 16-bit με υποστήριξη αφαίρεσης και πρόσθεσης για την βελτίωση της εκτίμησης συχνοτήτων, ενός σκίτσου ενισχυμένου με προ-φίλτρο για την ακριβή ανίχνευση συχνών στοιχείων και μιας επαυξανόμενης τεχνικής εκτίμησης συχνοτικών στιγμών, η οποία λειτουργεί σε πραγματικό χρόνο. Κατά τον χρόνο συγγραφής της παρούσας διπλωματικής εργασίας, δεν υπήρχε διαθέσιμη προηγούμενη δημόσια υλοποίηση αυτού του πλαισίου. Τα πειραματικά αποτελέσματα επιβεβαιώνουν τα αναφερόμενα πλεονεκτήματα του πλαισίου και καταδεικνύουν ότι υπερτερεί των τωρινών διαθέσιμων αλγορίθμων τόσο στην ανίχνευση συχνών στοιχείων όσο και στην εκτίμηση συχνοτικών στιγμών, σε ένα ευρύ φάσμα αναλογιών διαγραφών και κατανομών συνόλων δεδομένων. Τέλος, η παρούσα εργασία επεκτείνει το πλαίσιο με μια κατανεμημένη ανάπτυξη χρησιμοποιώντας το Apache Flink και Apache Kafka καταδεικνύοντας την δυνατότητα ενσωμάτωσης του προτεινόμενου πλαισίου σε έναν αγωγό επεξεργασίας δεδομένων σε πραγματικό χρόνο-μια επέκταση που δεν εξετάζεται στην αρχική εργασία.
Abstract
In the field of data stream processing, there are two prevalent models, the insertion-only model and the turnstile model, which permits both insertions and deletions of elements. Under the turnstile model with bounded deletions, where the number of deletions is constrained relative to insertions, computing universal stream measurements becomes significantly challenging, especially under memory constraints and the need for online processing. Universal measurements simultaneously estimate multiple statistical metrics including per-element frequency, heavy hitters and frequency moments. In this setting two key challenges emerge. Firstly, most previous methods for detecting heavy hitters cannot ensure a bounded detection error when there are deletion events. Secondly, there is still no prior work to estimate per-key element frequency moments under the turnstile model, especially in an online fashion. This thesis presents an independent Java implementation and empirical evaluation of the Removable Augmented Sketch (RAS) and Removable Universal Sketch (RUS) enhanced with an Online Moment Estimator (OME). This framework was originally proposed by Liang Zheng, Qingjun Xiao and Xuyuan Cai in 2024, to address these two challenges through a compressed 16-bit counter design supporting subtraction and addition to improve frequency estimation, a prefilter-augmented sketch for accurate heavy hitter tracking and an incremental moment estimation technique, which works in an online manner. At the time of writing this thesis no prior public reference implementation was available. Experimental results validate the frameworks reported advantages and demonstrate that it outperforms currently available algorithms both in the case of heavy hitter detection and frequency moment estimations, across a range of deletion ratios and dataset distributions. Finally, this thesis extends the framework with a distributed deployment using Apache Flink and Apache Kafka, demonstrating the feasibility of integrating the proposed framework into a real-time stream processing pipeline-an extension not addressed in the original work.
