Similarity computation in modern applications

Abstract

Computing the similarity between data items is a fundamental operation in data management. The first part of the thesis proposes a technique that is utilized in distributed applications for computing the similarity between data descriptions that are streamed from remote sources. The proposed technique utilizes prior knowledge of the data distribution in order to produce, with the same space, more accurate descriptions than the Random Hyperplane Projection (RHP) method (i.e. a locality sensitive hashing method). We present algorithms that materialize RHP dimensions that better describe the underlying data, while additional dimensions are derived in real-time using simple stored statistics we maintain. Our method is resilient to data distribution changes because of a fail-safe mechanism that detects in real time cases where particular data instances cannot be accurately described using the selected dimensions. In such cases the method automatically falls-back into using the basic RHP scheme. The second part of this work introduces a novel user-centric approach for similarity computation between products. Unlike techniques that focus on product features our method takes into account users’ preferences by utilizing the recent concept of reverse top-k queries. In contrast to a top-k query that returns the k products with the best score for a specific customer, the result of a reverse top-k query is the set of customers(or their rankings) for whom a given product belongs to their top-k set. Two novel query types (θ-similarity and m-nearest neighbor) for user-centric similarity search are defined, while algorithms for efficient processing of these queries are also discussed. The presented algorithms prune the search space by identifying effective similarity bounds and exploit conventional multi-dimensional indexes for efficient query processing. In the third part of this thesis we address the problem of outlier detection in hierarchically organized data domains. Outlier detection is critical for modern applications such as decision support (OLAP) and network management. However, existing techniques do not take into consideration the hierarchical nature of the data domains that is inherent in such applications. The natural aggregation of atomic values along a domain hierarchy is an intuitive summarization technique that can be used to detect diferent grades of abnormal behavior by looking across all levels of the hierarchy. In this work, we first formally define the notion of a hierarchical outlier and describe an intuitive monotonicity property that permits us to rate an outlier with a single grade value. We then present a technique that combines locality sensitive hashing and clustering in order to index the data descriptions. The fusion of both techniques permits us to reduce the storage space for the index and the execution time for an outlier computation query.

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