Efficient analysis in event logs

Abstract

In recent decades, there has been a noticeable increase in the presence of event sequences as a form of data. This surge is mainly due to the rise and widespread use of Internet of Things (IoT) devices, which continuously collect data by observing their surroundings and detecting changes. These large volumes of event sequences are stored in databases to facilitate various forms of analysis, enabling organizations to uncover valuable insights. This thesis addresses several critical challenges in efficiently managing and analyzing such data. More specifically, this thesis introduces SIESTA, an infrastructure designed to facilitate efficient pattern analysis over large event logs by leveraging inverted indexing techniques. Pattern analysis includes the detection of arbitrary patterns and the exploration of potential continuations for unfinished event sequences. SIESTA comprises two separate components: (a) the preprocessing component that incrementally builds the indices utilizing the massive parallelization offered by the Apache Spark framework, storing them in Cassandra, a scalable key-value database; and (b) the query processor, which uses these indices to prune the search space and expedite response times of the pattern queries. Various alternative approaches in both components have been investigated to optimize performance. Extensive evaluation demonstrates that SIESTA achieves significantly lower response times compared to state-of-the-art systems, confirming its effectiveness and scalability in big data scenarios. SIESTA's capabilities are further extended to establish it as a comprehensive, scalable, and trustworthy tool for cloud-native pattern detection with enhanced expressiveness. By integrating a Complex Event Processing (CEP) engine, specifically SASE, within SIESTA's query processor, the system can efficiently handle more complex patterns, including those with negations and iterations, while also providing explanations for unexpected result sets. Additionally, alternatives for storage solutions offering a more cost-efficient solution for cloud deployment are explored. The evaluation of these enhancements highlights SIESTA's superior scalability and pattern detection capabilities compared to competitors like Elasticsearch, FlinkCEP, and MATCH_RECOGNIZE. The effective pruning mechanisms and inherent parallelization of SIESTA enabled its adaptation to mine declarative constraints in big data scenarios. Specifically, the query processor was extended while the index building remained unchanged, making this an extension to SIESTA's functionalities without losing any of the previously supported queries. Through thorough evaluation using real-world datasets, the proposed solution demonstrates superior performance compared to existing ad-hoc solutions from the Business Process Management (BPM) field, such as Declare Miner and MINERful, particularly when multiple support thresholds are considered. Finally, this thesis investigates the detection of temporal anomalies in business process event logs. Four distinct proximity-based techniques tailored to detect temporal anomalies at both the event and trace levels are introduced. Additionally, the impact of different distance metrics on these techniques is investigated. The conclusions drawn from extensive experimentation offer guidance on selecting the appropriate proximity technique based on the type of anomalies being targeted and the characteristics of the dataset.

Τις τελευταίες δεκαετίες, παρατηρείται μια αξιοσημείωτη αύξηση ακολουθιών συμβάντων ως μορφή δεδομένων. Εκτός από την ανάλυση σε πραγματικό χρόνο, τα δεδομένα αυτά αποθηκεύονται σε βάσεις δεδομένων επιτρέποντας άλλες μορφές ανάλυσης, όπως η εξαγωγή συχνών μοτίβων. Κατά συνέπεια, συσσωρεύεται μεγάλος όγκος δεδομένων συμβάντων. Αυτό δίνει ιδιαίτερη έμφαση στη σπουδαιότητα της ανάπτυξης αποτελεσματικών μεθόδων για την ανάλυση αυτών των ακολουθιών συμβάντων και την ανακάλυψη χρήσιμων πληροφοριών. Ένα σημαντικό πρόβλημα είναι η ανίχνευση συγκεκριμένων συμπεριφορών σε ένα μεγάλο όγκο αποθηκευμένων δεδομένων, οι οποίες δεν είναι γνωστές εκ των προτέρων. Για την αποδοτική επίλυση αυτού του προβλήματος, η παρούσα διατριβή παρουσιάζει το SIESTA, μια υποδομή που αξιοποιεί μια δομή ευρετηρίασης, γνωστή ως αντεστραμμένος κατάλογος, με σκοπό τη μείωση του χρόνου απόκρισης. Το SIESTA αποτελείται από δύο διακριτά υποσυστήματα. Το πρώτο είναι υπεύθυνο για την προεπεξεργασία των δεδομένων, δημιουργώντας και ενημερώνοντας τις δομές ευρετηρίασης από συνεχώς εισερχόμενα δεδομένα. Για τη βέλτιστη επίτευξη του στόχου αυτού αξιοποιεί τον παραλληλισμό που προσφέρεται από το πλαίσιο Apache Spark. Οι δομές αυτές αποθηκεύονται στη συνέχεια σε μια κλιμακούμενη βάση δεδομένων. Το δεύτερο υποσύστημα χρησιμοποιεί τις δομές για να μειώσει τον χώρο αναζήτησης και να επιταχύνει τους χρόνους απόκρισης στα ερωτήματα εύρεσης μοτίβων. Διερευνήθηκαν διάφορες εναλλακτικές προσεγγίσεις και για τα δύο υποσυστήματα, με σκοπό τη βελτιστοποίηση της συνολικής τους απόδοσης. Η εκτεταμένη αξιολόγηση δείχνει ότι το SIESTA επιτυγχάνει σημαντικά χαμηλότερους χρόνους απόκρισης στον εντοπισμό μοτίβων σε σύγκριση με άλλα state-of-the-art συστήματα, όπως το Elasticsearch και το FlinkCEP. Επιπλέον, στο δεύτερο υποσύστημα ενσωματώθηκε μια μηχανή Complex Event Processing (CEP), η οποία επιτρέπει αφενός στο προτεινόμενο σύστημα να εντοπίζει πιο πολύπλοκα μοτίβα, τα οποία περιέχουν αρνήσεις και επαναλήψεις, και αφετέρου την εύρεση της αιτίας για μη αναμενόμενα αποτελέσματα. Οι αποτελεσματικοί μηχανισμοί κλαδέματος και η εγγενής παραλληλοποίηση του SIESTA επιτρέπουν την προσαρμογή του για την εξόρυξη δηλωτικών περιορισμών σε σενάρια μεγάλων δεδομένων. Συγκεκριμένα, το υποσύστημα που χειρίζεται τα ερωτήματα επεκτάθηκε, ενώ η διαδικασία δημιουργίας των δομών ευρετηρίασης παρέμεινε αμετάβλητη. Με αυτόν τον τρόπο επεκτάθηκαν οι λειτουργίες του SIESTA, χωρίς όμως να χαθεί καμία από τις υπάρχουσες δυνατότητές του. Η αξιολόγηση της προτεινόμενης λύσης, αξιοποιώντας δεδομένα πραγματικού κόσμου, έδειξε πως παρουσιάζει καλύτερες επιδόσεις σε σύγκριση με τις υπάρχουσες ad-hoc λύσεις από τον χώρο των επιχειρησιακών διαδικασιών, όπως το Declare Miner και το MINERful, ιδίως όταν αυξάνεται ο όγκος των δεδομένων και λαμβάνονται υπόψη πολλαπλά όρια υποστήριξης. Το τελευταίο αλλά εξίσου σημαντικό πρόβλημα που αναλύεται, είναι η ανίχνευση χρονικών ανωμαλιών, οι οποίες περιγράφουν μη-κανονικούς χρόνους εκτέλεσης ενός συμβάντος ή μίας ακολουθίας. Για την επίλυση αυτού του προβλήματος, εισάγονται τέσσερις τεχνικές που χρησιμοποιούν την έννοια της απόστασης μεταξύ των δεδομένων, για την εύρεση χρονικών ανωμαλιών. Αυτές οι τεχνικές δοκιμάστηκαν σε συνδυασμό με διαφορετικές συναρτήσεις απόστασης, όπως είναι η Ευκλίδεια και η Mahalanobis. Η εκτενής αξιολόγηση έδειξε πως αυτές οι μέθοδοι έχουν μεγαλύτερη ακρίβεια από μεθόδους που βασίζονται στη στατιστική, ενώ παράλληλα φανέρωσε κάποιες κατευθυντήριες γραμμές για το ποια από τις προτεινόμενες μεθόδους πρέπει να προτιμάται ανάλογα με τον τύπο των ανωμαλιών που αναζητούνται (μεμονωμένα συμβάντα ή ολόκληρες ακολουθίες) και τα χαρακτηριστικά του συνόλου των δεδομένων.