Similarity computation in modern applications
Authors: Γεωργούλας Κωνσταντίνος 
Published: September 2021

Ο υπολογισμός της ομοιότητας μεταξύ δεδομένων είναι μια θεμελιώδης λειτουργία στη διαχείριση δεδομένων. Το πρώτο μέρος της διατριβής προτείνει μια τεχνική που χρησιμοποιείται σε κατανεμημένες εφαρμογές για τον υπολογισμό της ομοιότητας μεταξύ περιγραφών δεδομένων που παράγονται από απομακρυσμένους κόμβους. Η προτεινόμενη τεχνική χρησιμοποιεί προηγούμενη γνώση της κατανομής των δεδομένων προκειμένου να παράγει, στον ίδιο χώρο, πιο ακριβείς περιγραφές από τη μέθοδο Random Hyperplane Projection (RHP). Παρουσιάζουμε αλγόριθμους που υπολογίζουν RHP διαστάσεις οι οποίες περιγράφουν καλύτερα τα δεδομένα, ενώ παράλληλα παράγονται πρόσθετες διαστάσεις σε πραγματικό χρόνο χρησιμοποιώντας απλά αποθηκευμένα στατιστικά στοιχεία που διατηρούμε. Η μέθοδος μας είναι ανθεκτική στις μεταβολές της κατανομής των δεδομένων εξαιτίας ενός μηχανισμού ασφαλούς αποτυχίας ο οποίος ανιχνεύει σε πραγματικό χρόνο περιπτώσεις όπου συγκεκριμένα υποσύνολα δεδομένων δεν μπορούν να περιγραφούν με ακρίβεια χρησιμοποιώντας τις επιλεγμένες διαστάσεις. Σε τέτοιες περιπτώσεις η μέθοδος επιστρέφει αυτόματα στη χρήση της βασικής RHP τεχνικής. Το δεύτερο μέρος αυτής της διατριβής εισάγει μια νέα προσέγγιση για τον υπολογισμό ομοιότητας μεταξύ προϊόντων η οποία βασίζεται στον χρήστη. Σε αντίθεση με τις τεχνικές που επικεντρώνονται στα χαρακτηριστικά του προϊόντος, η μέθοδος μας λαμβάνει υπόψη τις προτιμήσεις των χρηστών, χρησιμοποιώντας την έννοια των reverse top-k ερωτημάτων. Σε αντίθεση με ένα top-k ερώτημα, το οποίο επιστρέφει τα κ προϊόντα με την καλύτερη βαθμολογία για έναν συγκεκριμένο πελάτη, το αποτέλεσμα ενος reverse top-k ερωτήματος είναι το σύνολο των πελατών (ή οι σειρές κατάταξης) για τους οποίους ένα συγκεκριμένο προϊόν ανήκει στο top-k αποτέλεσμα τους. Καθορίζονται δύο νέοι τύποι επερωτήσεων (θ-ομοιότητα και μ-πλησιέστεροι γείτονες) για τον υπολογισμό ομοιότητας με επίκεντρο τις προτιμήσεις των χρηστών, ενώ επίσης συζητούνται αλγόριθμοι για την αποτελεσματική επεξεργασία αυτών των ερωτημάτων. Οι αλγόριθμοι που παρουσιάζονται μειώνουν το χώρο αναζήτησης εντοπίζοντας αποτελεσματικά όρια ομοιότητας και εκμεταλλεύονται συμβατικά πολυδιάστατα ευρετήρια για αποτελεσματική επεξεργασία των ερωτημάτων. Στο τρίτο μέρος της διατριβής εξετάζουμε το πρόβλημα της ανίχνευσης ακραίων τιμών σε ιεραρχικά οργανωμένα σύνολα δεδομένων. Η ανίχνευση ακραίων τιμών είναι κρίσιμη για τις σύγχρονες εφαρμογές, όπως η υποστήριξη λήψης αποφάσεων (OLAP) και η διαχείριση δικτύου. Ωστόσο, οι υπάρχουσες τεχνικές δεν λαμβάνουν υπόψη την ιεραρχική φύση των δεδομένων που είναι εγγενής σε τέτοιες εφαρμογές. Η φυσική άθροιση των ατομικών τιμών ακολουθώντας τη δομή μιας ιεραρχίας είναι μια διαισθητική τεχνική σύνοψης των δεδομένων που μπορεί να χρησιμοποιηθεί για την ανίχνευση διαφορετικών βαθμών ακραίων τιμών, εξετάζοντας όλα τα επίπεδα της ιεραρχίας. Σε αυτή την εργασία, αρχικά ορίζουμε την έννοια μιας ιεραρχικά ακραίας τιμής και περιγράφουμε μια διαισθητική ιδιότητα μονοτονίας που μας επιτρέπει να διαβαθμίσουμε μια ακραία τιμή με εναν μοναδικό αριθμό. Στη συνέχεια, παρουσιάζουμε μια μέθοδο που συνδυάζει την τεχνική του locality sensitive κατακερματισμού και της ομαδοποίησης των δεδομένων για τη δημιουργία ενός ευρετηρίου. Ο συνδυασμός και των δύο τεχνικών μας επιτρέπει να μειώσουμε το χώρο αποθήκευσης του ευρετηρίου αλλά και τον χρόνο εκτέλεσης ενός ερωτήματος υπολογισμού ιεραρχικά ακραίας τιμής.