Μονάδα:
Κατεύθυνση / ειδίκευση Διαχείριση Πληροφορίας και Δεδομένων (ΔΕΔ)Πληροφορική
Ημερομηνία κατάθεσης:
2023-12-08
Συγγραφέας:
Φούφουλας Ιωάννης
Στοιχεία επταμελούς επιτροπής:
Ιωάννης Ιωαννίδης, Καθηγητής, Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Μιχάηλ Χατζόπουλος, Ομότιμος Καθηγητής, Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Αλέξης Δελης, Καθηγητής, Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Μέμα Ρουσσοπούλου, Καθηγήτρια, Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Ιωάννης Παπακωνσταντίνου, Καθηγητής, Πανεπιστήμιο Καλιφόρνια - Σαν Ντιέγκο
Ευστράτιος Υδραίος, Αναπληρωτής Καθηγητής, Πανεπιστήμιο Χάρβαρντ
"Άλκης Σιμιτσής, Διευθυντής Ερευνών, Ερευνητικό κέντρο ΑΘΗΝΑ"
Πρωτότυπος Τίτλος:
Αντιμετώπιση σημείων συμφόρησης στην ανάλυση συμβολοσειρών σε εφαρμογές επιστήμης δεδομένων
Γλώσσες διατριβής:
Αγγλικά
Μεταφρασμένος τίτλος:
Αντιμετώπιση σημείων συμφόρησης στην ανάλυση συμβολοσειρών σε εφαρμογές επιστήμης δεδομένων
Περίληψη:
Η ποικιλομορφία και η πολυπλοκότητα των σύγχρονων εφαρμογών διαχείρισης δεδομένων
μαζί με την αύξηση των διαθέσιμων δεδομένων ανοίγουν ευκαιρίες για βελτιώσεις σε
όλα τα επίπεδα εκτέλεσης μιας κοινής ροής ανάλυσης δεδομένων. Σε αυτή τη διατριβή,
στοχεύουμε την ανάλυση συμβολοσειρών και βελτιστοποιούμε την αναλυτική επεξεργασία
δεδομένων κειμένου με την αντιμετώπιση σημαντικών σημείων αυξημένης πολυπλοκότητας.
Εξετάζουμε το πρόβλημα της αντιστοίχισης αναφορών. Είναι ένα σημαντικό πρόβλημα
καθώς η λύση του επιτρέπει στους ερευνητές να αναζητούν βιβλιογραφία, να βρίσκουν
σχετικές δημοσιεύσεις, να διεξάγουν ανάλυση των τάσεων της έρευνας και ούτω καθεξής.
Είναι επίσης ένα πολύπλοκο πρόβλημα, δεδομένης της ποικιλομορφίας των πηγών δεδομένων,
της εκθετικής αύξησης της βιβλιογραφίας ανοιχτής πρόσβασης και της βαριάς
επεξεργασίας που εμπεριέχει. Αναλύουμε το πρόβλημα σε τρία διαφορετικά επίπεδα: 1)
επίπεδο αλγορίθμου 2) επίπεδο αποθήκευσης/επεξεργασίας συμβολοσειρών 3) επίπεδο
υλοποίησης.
Καθένα από αυτά τα επίπεδα εισάγει τα δικά του σημεία αυξημένης πολυπλοκότητας. Η
τρέχουσα βιβλιογραφία προτείνει αλγόριθμους που αρχικά εξάγουν δομημένες αναφορές
από κείμενα, χρησιμοποιώντας μηχανική μάθηση και ευρετικές μεθόδους. Οι δομημένες
αναφορές ενώνονται με τα μεταδεδομένα για να δημιουργήσουν ένα γράφο αναφορών. Το
βήμα της εξαγωγής δομημένων αναφορών είναι το πιο πολύπλοκο υπολογιστικά. Δεδομένων
των διαφόρων τρόπων που υπάρχουν για να δομηθεί η ενότητα με τις αναφορές
σε ένα άρθρο, δεν είναι δυνατό να παραχθεί μια ακριβής λύση βασισμένη σε κανόνες για
την εξαγωγή αναφορών.
Το επίπεδο αποθήκευσης και επεξεργασίας συμβολοσειρών περιλαμβάνει τη δική του
πολυπλοκότητα. Η επεξεργασία συμβολοσειρών είναι χρονοβόρα, και επίσης οι όγκοι των
δεδομένων είναι μεγάλοι. Μια αποτελεσματική διάταξη για την αποθήκευση συμβολοσειρών
θα μπορούσε να βελτιστοποιήσει τόσο την αποθήκευση δεδομένων όσο και τη μεταφορά
και την εκτέλεση σαρώσεων και ζεύξεων σε συμβολοσειρές.
Το επίπεδο υλοποίησης περιέχει πράξεις διαδικαστικού προγραμματισμού (π.χ. επεξεργασία
κειμένου, κανονικοποιήσεις και ούτω καθεξής) που συνήθως υλοποιούνται σε γλώσσες
υψηλού επιπέδου όπως η Python, και πράξεις επεξεργασίας συμβολοσειρών (π.χ. σαρώσεις,
ζεύξεις) που θα μπορούσαν να εκτελεστούν πιο αποτελεσματικά σε ένα σύστημα
διαχείρισης δεδομένων. Το πρόβλημα λοιπόν είναι ποιος είναι ο πιο αποδοτικός τρόπος
να συγχωνευτούν αυτοί οι δύο τύποι πράξεων σε ένα σύστημα ανάλυσης δεδομένων.
Οι συνεισφορές της διατριβής μπορούν να συνοψιστούν ως εξής:
• Σχεδιάζουμε έναν αλγόριθμο αντιστοίχισης αναφορών που παρακάμπτει το βήμα
εξαγωγής δομημένων αναφορών και συγχωνεύει τα βήματα επεξεργασίας κειμένου
και αντιστοίχισης αναφορών σε ένα. Σύμφωνα με τα πειράματα, η προτεινόμενη
τεχνική παράγει έως 20% περισσότερες συνδέσεις και είναι έως και περισσότερο
από δύο τάξεις μεγέθους γρηγορότερη από τεχνικές που εξάγουν δομημένες αναφορές
πριν την αντιστοίχηση.
• Εισάγουμε έναν αλγόριθμο συμπίεσης για αποθήκευση κολώνων με συμβολοσειρές
που βασίζεται σε συμπίεση με προσαρμοστικά λεξικά και επιτρέπει γρήγορες σαρώσεις,
φίλτρα, ταξινομήσεις, ζεύξεις και τυχαίες αναζητήσεις τιμών. Τα πειράματά μας
έχουν υποσχόμενα αποτελέσματα που δείχνου ότι σε πολλές περιπτώσεις η μέθοδος
με τα προσαρμοστικά λεξικά είναι πολύ πιο αποδοτική από τις υπάρχουσες τεχνικές.
• Παρουσιάζουμε μια επέκταση της SQL που επιτρέπει την εύκολη και αποτελεσματική
ενσωμάτωση διαδικαστικών πράξεων γραμμένων σε Python εντός της SQL. Η προτεινόμενη
επέκταση της SQL υποστηρίζει τη δημιουργία εκφραστικών συναρτήσεων
καθορισμένων από το χρήστη (UDF) που ενσωματώνονται άψογα με ένα ενσωματωμένο
ή βασισμένο σε διακομιστή σύστημα διαχείρησης βάσεων δεδομένων και χρησιμοποιεί
σύγχρονες τεχνικές όπως μεταγλώττιση την ώρα της εκτέλεσης, διανυσματοποίηση,
συγχώνευση UDF για τη βελτίωση της απόδοσης. Η πειραματική ανάλυση
αναδεικνύει την χρηστικότητα και την εκφραστικότητα της προτεινόμενης επέκτασης
της SQL και δείχνει ότι οι τεχνικές είναι πολύ αποδοτικές και επιτυγχάνουν μεγάλες
επιταχύνσεις έως και 68 φορές σε κοινά σενάρια σε σύγκριση με προηγούμενες
προσεγγίσεις και εναλλακτικές επιλογές υλοποίησης.
• Υλοποιούμε μια βιβλιοθήκη με συναρτήσεις για ανάλυση κειμένου συμβολοσειρών.
Στόχος της βιβλιοθήκης είναι η ανάλυση κειμένου να γίνεται μέσα σε μια βάση δεδομένων
χρησιμοποιώντας τα χαρακτηριστικά ευχρηστίας και απόδοσης της επέκτασης
της SQL. Η βιβλιοθήκη περιλαμβάνει πάνω από 150 συναρτήσεις οι οποίες μπορούν
να χρησιμοποιηθούν στην υλοποίηση αλγορίθμων ανάλυσης κειμένου.
• Πραγματοποιούμε μια ποικιλία πειραμάτων που αποδεικνύουν την αποτελεσματικότητα
των προτεινόμενων λύσεων. Αξιολογούμε όλες τις λύσεις για την ταχύτητα
εκτέλεσής τους. Επιπλέον αξιολογούμε τον αλγόριθμο αντιστοίχησης αναφορών
για την ακρίβειά του, την κωδικοποίηση με προσαρμοστικά λεξικά για τον βαθμό
συμπίεσής τους, και εξετάζουμε την χρηστικότητα της YeSQL και της βιβλιοθήκης
συναρτήσεων. Τα πειράματα δείχνουν ότι οι προτεινόμενες λύσεις επιτυγχάνουν
καλύτερες επιδόσεις από τις εναλλακτικές λύσεις της τρέχουσας βιβλιογραφίας.
Τέλος, προτείνουμε ευκαιρίες βελτιστοποίησης που αποτελούν μέρος της τρέχουσας και
μελλοντικής μας εργασίας.
Κύρια θεματική κατηγορία:
Τεχνολογία – Πληροφορική
Λέξεις-κλειδιά:
Αντιστοίχηση αναφορών, Συμπίεση, Επέκταση SQL
Αρ. σελίδων ευρετηρίου:
4
Αρ. βιβλιογραφικών αναφορών:
114
