Η εύρεση λειτουργικών εξαρτήσεων στα δεδομένα χρησιμοποιείται σε διάφορους τομείς της ανάλυσης δεδομένων: διαχείριση βάσεων δεδομένων, καθαρισμός δεδομένων, αντίστροφη μηχανική βάσης δεδομένων και εξερεύνηση δεδομένων. Έχουμε ήδη δημοσιεύσει για τις ίδιες τις εξαρτήσεις Anastasia Birillo και Nikita Bobrov. Αυτή τη φορά, η Αναστασία, απόφοιτος του Κέντρου Επιστήμης Υπολογιστών φέτος, μοιράζεται την εξέλιξη αυτής της εργασίας ως μέρος του ερευνητικού έργου που υπερασπίστηκε στο κέντρο.
Επιλογή εργασιών
Ενώ σπούδαζα στο κέντρο CS, άρχισα να μελετάω σε βάθος τις βάσεις δεδομένων, δηλαδή την αναζήτηση λειτουργικών και διαφορετικών εξαρτήσεων. Αυτό το θέμα σχετιζόταν με το θέμα των μαθημάτων μου στο πανεπιστήμιο, έτσι ενώ εργαζόμουν στα μαθήματα, άρχισα να διαβάζω άρθρα σχετικά με διάφορες εξαρτήσεις σε βάσεις δεδομένων. Έγραψα μια κριτική για αυτήν την περιοχή - μια από τις πρώτες μου στα αγγλικά και το υπέβαλε στο συνέδριο SEIM-2017. Χάρηκα πολύ όταν έμαθα ότι τελικά έγινε αποδεκτή και αποφάσισα να εμβαθύνω στο θέμα. Η ίδια η ιδέα δεν είναι νέα - άρχισε να χρησιμοποιείται στη δεκαετία του '90, αλλά ακόμη και τώρα χρησιμοποιείται σε πολλούς τομείς.
Κατά τη διάρκεια του δεύτερου εξαμήνου μου στο κέντρο, ξεκίνησα ένα ερευνητικό έργο για τη βελτίωση των αλγορίθμων για την εύρεση λειτουργικών εξαρτήσεων. Εργάστηκε σε αυτό μαζί με τον μεταπτυχιακό φοιτητή του κρατικού πανεπιστημίου της Αγίας Πετρούπολης Nikita Bobrov στο JetBrains Research.
Υπολογιστική πολυπλοκότητα αναζήτησης λειτουργικών εξαρτήσεων
Το κύριο πρόβλημα είναι η υπολογιστική πολυπλοκότητα. Ο αριθμός των πιθανών ελάχιστων και μη τετριμμένων εξαρτήσεων περιορίζεται παραπάνω από την τιμή Όπου — αριθμός χαρακτηριστικών πίνακα. Ο χρόνος λειτουργίας των αλγορίθμων εξαρτάται όχι μόνο από τον αριθμό των χαρακτηριστικών, αλλά και από τον αριθμό των σειρών. Στη δεκαετία του '90, οι αλγόριθμοι αναζήτησης ομοσπονδιακού νόμου σε έναν κανονικό επιτραπέζιο υπολογιστή μπορούσαν να επεξεργάζονται σύνολα δεδομένων που περιέχουν έως και 20 χαρακτηριστικά και δεκάδες χιλιάδες σειρές σε έως και αρκετές ώρες. Οι σύγχρονοι αλγόριθμοι που εκτελούνται σε επεξεργαστές πολλαπλών πυρήνων ανιχνεύουν εξαρτήσεις για σύνολα δεδομένων που αποτελούνται από εκατοντάδες χαρακτηριστικά (έως 200) και εκατοντάδες χιλιάδες σειρές σε περίπου τον ίδιο χρόνο. Ωστόσο, αυτό δεν αρκεί: ένας τέτοιος χρόνος είναι απαράδεκτος για τις περισσότερες εφαρμογές του πραγματικού κόσμου. Ως εκ τούτου, αναπτύξαμε προσεγγίσεις για να επιταχύνουμε τους υπάρχοντες αλγόριθμους.
Σχήματα προσωρινής αποθήκευσης για διασταυρώσεις διαμερισμάτων
Στο πρώτο μέρος της εργασίας, αναπτύξαμε σχήματα προσωρινής αποθήκευσης για μια κατηγορία αλγορίθμων που χρησιμοποιούν τη μέθοδο τομής διαμερισμάτων. Ένα διαμέρισμα για ένα χαρακτηριστικό είναι ένα σύνολο λιστών, όπου κάθε λίστα περιέχει αριθμούς γραμμών με τις ίδιες τιμές για ένα δεδομένο χαρακτηριστικό. Κάθε τέτοια λίστα ονομάζεται σύμπλεγμα. Πολλοί σύγχρονοι αλγόριθμοι χρησιμοποιούν κατατμήσεις για να καθορίσουν εάν μια εξάρτηση διατηρείται ή όχι, δηλαδή, τηρούν το λήμμα: Εξάρτηση πραγματοποιήθηκε αν . Εδώ ορίζεται ένα διαμέρισμα και χρησιμοποιείται η έννοια του μεγέθους διαμερίσματος - ο αριθμός των συμπλεγμάτων σε αυτό. Οι αλγόριθμοι που χρησιμοποιούν κατατμήσεις, όταν παραβιάζεται η εξάρτηση, προσθέτουν πρόσθετα χαρακτηριστικά στην αριστερή πλευρά της εξάρτησης και στη συνέχεια την υπολογίζουν εκ νέου, εκτελώντας τη λειτουργία τομής κατατμήσεων. Αυτή η λειτουργία ονομάζεται εξειδίκευση στα άρθρα. Ωστόσο, παρατηρήσαμε ότι τα διαμερίσματα για εξαρτήσεις που θα διατηρούνταν μόνο μετά από μερικούς γύρους εξειδίκευσης μπορούν να επαναχρησιμοποιηθούν ενεργά, γεγονός που μπορεί να μειώσει σημαντικά τον χρόνο εκτέλεσης των αλγορίθμων, καθώς η λειτουργία διασταύρωσης είναι δαπανηρή.
Ως εκ τούτου, προτείναμε μια ευρετική βασισμένη στην εντροπία Shannon και στην αβεβαιότητα Ginny, καθώς και στη μέτρησή μας, την οποία ονομάσαμε Αντίστροφη Εντροπία. Είναι μια μικρή τροποποίηση της εντροπίας Shannon και αυξάνεται καθώς αυξάνεται η μοναδικότητα του συνόλου δεδομένων. Η προτεινόμενη ευρετική είναι η εξής:
Εδώ — βαθμός μοναδικότητας του πρόσφατα υπολογισθέντος διαμερίσματος Και είναι η διάμεσος των βαθμών μοναδικότητας για μεμονωμένα χαρακτηριστικά. Και οι τρεις μετρήσεις που περιγράφονται παραπάνω δοκιμάστηκαν ως μέτρηση μοναδικότητας. Μπορείτε επίσης να παρατηρήσετε ότι υπάρχουν δύο τροποποιητές στην ευρετική. Το πρώτο δείχνει πόσο κοντά είναι το τρέχον διαμέρισμα στο πρωτεύον κλειδί και σας επιτρέπει να αποθηκεύετε προσωρινά σε μεγαλύτερο βαθμό εκείνα τα διαμερίσματα που απέχουν πολύ από το δυνητικό κλειδί. Ο δεύτερος τροποποιητής σάς επιτρέπει να παρακολουθείτε την κατάληψη της κρυφής μνήμης και έτσι ενθαρρύνει την προσθήκη περισσότερων κατατμήσεων στην κρυφή μνήμη εάν υπάρχει διαθέσιμος ελεύθερος χώρος. Η επιτυχής επίλυση αυτού του προβλήματος μας επέτρεψε να επιταχύνουμε τον αλγόριθμο PYRO κατά 10-40%, ανάλογα με το σύνολο δεδομένων. Αξίζει να σημειωθεί ότι ο αλγόριθμος PYRO είναι ο πιο επιτυχημένος σε αυτόν τον τομέα.
Στο παρακάτω σχήμα μπορείτε να δείτε τα αποτελέσματα της εφαρμογής της προτεινόμενης ευρετικής σε σύγκριση με μια βασική προσέγγιση προσωρινής αποθήκευσης με αναστροφή νομισμάτων. Ο άξονας Χ είναι λογαριθμικός.
Ένας εναλλακτικός τρόπος αποθήκευσης κατατμήσεων
Στη συνέχεια προτείναμε έναν εναλλακτικό τρόπο αποθήκευσης κατατμήσεων. Τα διαμερίσματα είναι ένα σύνολο συμπλεγμάτων, καθένα από τα οποία αποθηκεύει αριθμούς πλειάδων με ίδιες τιμές για ορισμένα χαρακτηριστικά. Αυτά τα συμπλέγματα μπορεί να περιέχουν μεγάλες ακολουθίες πολλαπλών αριθμών, για παράδειγμα, εάν τα δεδομένα σε έναν πίνακα είναι ταξινομημένα. Ως εκ τούτου, προτείναμε ένα σχήμα συμπίεσης για την αποθήκευση των κατατμήσεων, δηλαδή την αποθήκευση τιμών διαστήματος σε ομάδες κατατμήσεων:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{First interval}, underbrace{7, 8}_{Second interval}, 10}}\ downarrow{ Compression} \ pi(X) = {{underbrace{$, 1, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}$$display$$
Αυτή η μέθοδος μπόρεσε να μειώσει την κατανάλωση μνήμης κατά τη λειτουργία του αλγορίθμου TANE από 1 σε 25%. Ο αλγόριθμος TANE είναι ένας κλασικός αλγόριθμος για την αναζήτηση ομοσπονδιακών νόμων· χρησιμοποιεί κατατμήσεις κατά τη διάρκεια της εργασίας του. Ως μέρος της πρακτικής, επιλέχθηκε ο αλγόριθμος TANE, καθώς ήταν πολύ πιο εύκολο να εφαρμοστεί η διαλειμματική αποθήκευση σε αυτόν από ό,τι, για παράδειγμα, στο PYRO προκειμένου να αξιολογηθεί εάν η προτεινόμενη προσέγγιση λειτουργεί. Τα αποτελέσματα που προέκυψαν παρουσιάζονται στο παρακάτω σχήμα. Ο άξονας Χ είναι λογαριθμικός.
Συνέδριο ADBIS-2019
Με βάση τα αποτελέσματα της έρευνας, τον Σεπτέμβριο του 2019 δημοσίευσα ένα άρθρο στο 23ο Ευρωπαϊκό Συνέδριο για τις εξελίξεις στις βάσεις δεδομένων και τα συστήματα πληροφοριών (ADBIS-2019). Κατά τη διάρκεια της παρουσίασης, το έργο σημειώθηκε από τον Bernhard Thalheim, σημαντικό πρόσωπο στον τομέα των βάσεων δεδομένων. Τα αποτελέσματα της έρευνας αποτέλεσαν τη βάση της διατριβής μου στο μεταπτυχιακό στα μαθηματικά και τη μηχανική στο Κρατικό Πανεπιστήμιο της Αγίας Πετρούπολης, κατά την οποία εφαρμόστηκαν και οι δύο προτεινόμενες προσεγγίσεις (caching και συμπίεση) και στους δύο αλγόριθμους: TANE και PYRO. Επιπλέον, τα αποτελέσματα έδειξαν ότι οι προτεινόμενες προσεγγίσεις είναι καθολικές, αφού και στους δύο αλγόριθμους, και με τις δύο προσεγγίσεις, παρατηρήθηκε σημαντική μείωση στην κατανάλωση μνήμης, καθώς και σημαντική μείωση του χρόνου λειτουργίας των αλγορίθμων.
Πηγή: www.habr.com