Εξατομίκευση επερωτήσεων σύμφωνα με τις προτιμήσεις του χρήστη

Abstract

This thesis studies Query Personalization, a process of dynamically enhancing a query with preferences stored in a user profile with the purpose of generating a customized focused and hopefully smaller answer for a specific user. We present a preference model that combines expressivity and concision and provides a direct way to personalize queries. User preferences are stored as degrees of interest in atomic query elements (individual selection and join conditions), which may be used to transform a query. The degree of interest expresses the interest of a person to include the associated condition into the qualification of a given query. Specific logic is introduced for derivation of preferences combining stored atomic ones. We propose a personalization framework according to which personalized results should satisfy at least L out of the top K most important preferences that are related to the given query. Parameters K and L can be specified with the use of various criteria. Personalized results are ranked based on the estimated degree of interest in the combination of preferences they satisfy. Preference selection from a structured user profile is formulated as a graph computation problem. Efficient algorithms that derive the top K preferences from a user profile that are related to a query are described. The top K preferences derived from the user profile may be integrated into the initial query so that the resulting one should return results satisfying at least L from the top K preferences. Alternative query rewriting schemes have been examined. A specialized algorithm that allows for progressive generation of personalized results is also proposed. Query personalization is formulated as a constrained optimization problem, where constraints may concern the personalized query execution time and result size. This is the first realistic approach to personalization that takes into account real-time factors and conditions in order to return personalized results. Constrained query personalization is formulated as a state space search problem. Each personalized query that is a potential solution is a state in a space (a node in a graph), characterized by degree of interest, execution cost, and result size. Transitions (edges) arrange states in partial orders based on each of the aforementioned query parameters. State-space search algorithms are devised that take advantage of these partial orders to solve these problems efficiently

Η παρούσα διατριβή πραγματεύεται την Εξατομίκευση Ερωτήσεων, μία διαδικασία δυναμικού εμπλουτισμού μίας ερώτησης με προτιμήσεις που είναι αποθηκευμένες στο προφίλ ενός χρήστη με στόχο τη δημιουργία μίας μικρότερης επιλεκτικής απάντησης προσαρμοσμένης στο συγκεκριμένο χρήστη. Η διατριβή προτείνει ένα μοντέλο το οποίο παρέχει ένα σύντομο και περιεκτικό τρόπο περιγραφής ποικίλλων προτιμήσεων, άμεσα συνδεδεμένο με τη διαδικασία εξατομίκευσης επερωτήσεων. Συγκεκριμένα, μία προτίμηση αποθηκεύεται ως ένας βαθμός ενδιαφέροντος σε μία ατομική συνθήκη συνένωσης ή επιλογής. Ο βαθμός ενδιαφέροντος εκφράζει τη σημασία που αποδίδει το συγκεκριμένο άτομο στην εισαγωγή της σχετικής συνθήκης σε μία επερώτηση. Δοθείσης μίας ερώτησης, η διατριβή προτείνει ένα πλαίσιο εξατομίκευσης σύμφωνα με το οποίο τα εξατομικευμένα αποτελέσματα ικανοποιούν τουλάχιστον L από τις Κ καλύτερες προτιμήσεις του χρήστη που είναι σχετικές με τη δοθείσα επερώτηση. Ο προσδιορισμός των παραμέτρων Κ και L γίνεται με τη βοήθεια ποικίλλων κριτηρίων. Τα αποτελέσματα είναι βαθμολογημένα και διατεταγμένα με βάση το βαθμό ενδιαφέροντος, ο οποίος υπολογίζεται λαμβάνοντας υπόψη ποιες L από τις K προτιμήσεις ικανοποιούνται. Η επιλογή προτιμήσεων από ένα δομημένο προφίλ μοντελοποιείται ως ένα πρόβλημα υπολογισμού σε γράφο και προτείνονται αλγόριθμοι που βρίσκουν τις Κ καλύτερες προτιμήσεις ενός χρήστη που είναι σχετικές με μία επερώτηση πραγματοποιώντας κατά-βέλτιστο διάσχιση του γράφου που αντιστοιχεί στο προφίλ του. Η δημιουργία της εξατομικευμένης απάντησης που θα ικανοποιεί τουλάχιστον L από τις Κ-καλύτερες προτιμήσεις του χρήστη μπορεί να γίνει ενσωματώνοντας τις επιλεγμένες προτιμήσεις στη δοθείσα ερώτηση και εκτελώντας την εξατομικευμένη ερώτηση που προκύπτει. Η διατριβή προτείνει διαφορετικούς τρόπους μετασχηματισμού της αρχικής επερώτησης και παρουσιάζει ένα αλγόριθμο που επιτρέπει τη σταδιακή ανάκτηση εξατομικευμένων αποτελεσμάτων. Η διατριβή γενικεύει την εξατομίκευση ερωτήσεων σε ένα πρόβλημα βελτιστοποίησης υπό περιορισμούς, όπου οι περιορισμοί αφορούν στον χρόνο εκτέλεσης της εξατομικευμένης ερώτησης και στο πλήθος των αποτελεσμάτων. Αυτή είναι και η πρώτη ρεαλιστική προσέγγιση σε πρόβλημα εξατομίκευσης που λαμβάνει υπόψη παραμέτρους και συνθήκες που ισχύουν σε πραγματικό χρόνο για να επιστρέψει εξατομικευμένα αποτελέσματα. Η εξατομίκευση υπό περιορισμούς μοντελοποιείται ως ένα πρόβλημα αναζήτησης σε χώρο καταστάσεων. Κάθε εξατομικευμένη ερώτηση που είναι μια πιθανή λύση στο πρόβλημα είναι μία κατάσταση σε ένα χώρο (ένας κόμβος σε ένα γράφο), και χαρακτηρίζεται από βαθμό ενδιαφέροντος, χρόνο εκτέλεσης, και μέγεθος απάντησης. Οι μεταβάσεις (ακμές) διευθετούν τις καταστάσεις σε μερικές διατάξεις με βάση τις προαναφερθείσες παραμέτρους. Προτείνονται και συγκρίνονται αλγόριθμοι αναζήτησης στον χώρο καταστάσεων, οι οποίοι εκμεταλλεύονται τις μερικές διατάξεις για την αποδοτική επίλυση τέτοιων προβλημάτων εξατομίκευσης