Query Ordering Based Top-k Algorithms For Qualitatively Specified Preferences

 
This item is provided by the institution :
University of Crete
Repository :
E-Locus Institutional Repository
see the original item page
in the repository's web site and access all digital files if the item*
share




2007 (EN)
Top-k Αλγόριθμοι Βασισμένοι Σε Διατάξεις Επερωτήσεων Για Ποιοτικώς Καθορισμένες Προτιμήσεις
Query Ordering Based Top-k Algorithms For Qualitatively Specified Preferences

Καπανταϊδάκης, Ιωάννης (EL)
Kapantaidakis, Ioannis (EN)

Τα τελευταία χρόνια, η μοντελοποίηση και η διαχείριση των προτιμήσεων έχουν προσελκύσει ιδιαίτερη προσοχή στους τομείς των Βάσεων Δεδομένων, των Βάσεων Γνώσης και των Συστημάτων Ανάκτησης Πληροφοριών. Αυτό το ενδιαφέρον πηγάζει από το γεγονός ότι ολοένα και περισσότεροι μη ειδικευμένοι κοινοί χρήστες έρχονται σε επαφή με τεράστιες συλλογές δεδομένων, συνήθως μέσω του Διαδικτύου, χωρίς, κατά κανόνα, να έχουν μια σαφή άποψη ούτε για το περιεχόμενο ούτε και για τη δομή της πληροφορίας, χωρίς καν να έχουν ένα συγκεκριμένο αντικείμενο υπ? όψει τους. Πιο πολύ προσπαθούν να ανακαλύψουν αντικείμενα που ενδεχομένως θα τους είναι χρήσιμα, αντικείμενα, με άλλα λόγια, που ταιριάζουν καλύτερα στις προτιμήσεις τους. Συνεπώς, ένα σύγχρονο πληροφοριακό σύστημα θα πρέπει να διευκολύνει τους χρήστες στο γρήγορο εντοπισμό των k βέλτιστων αντικειμένων βάσει των προτιμήσεων τους. Στην εργασία αυτή, μοντελοποιώντας τις προτιμήσεις ως δυαδικές σχέσεις, εισάγουμε αποδοτικούς αλγορίθμους αποτίμησης των k βέλτιστων αντικειμένων. Η έως τώρα σχετική έρευνα, αντιμετώπιζε τις εκφράσεις επί προτιμήσεων ως «μαύρα κουτιά» και εφάρμοζε την ιδέα των εξαντλητικών διαδοχικών ελέγχων υπεροχής μεταξύ των αντικειμένων μιας βάσης δεδομένων για τον προσδιορισμό των καλύτερων εξ? αυτών, γεγονός που οδηγούσε σε τετραγωνικά ως προς τον αριθμό των αντικειμένων κόστη. Αντιθέτως, εμείς υποστηρίζουμε μια προσέγγιση που βασίζεται στη διάταξη επερωτήσεων. Η κύρια ιδέα μας βασίζεται στην εκμετάλλευση της σημασιολογίας μιας έκφρασης από προτιμήσεις, σε ό,τι αφορά τόσο τους εμπλεκόμενους τελεστές όσο και τις εμπλεκόμενες προτιμήσεις, με σκοπό τον ορισμό μιας διάταξης μεταξύ εκείνων των επερωτήσεων, των οποίων η αποτίμηση είναι αναγκαία, ώστε να ανακτηθούν τα k βέλτιστα αντικείμενα. Παρουσιάζουμε δύο πρωτότυπους αλγόριθμους, τους LBA και TBA. Ο LBA ορίζει μια διάταξη επερωτήσεων, οι οποίες ουσιαστικά αποτελούν συζεύξεις ατομικών συνθηκών επιλογής, συμπεριλαμβάνοντας όλα τα γνωρίσματα που εμπλέκονται στις προτιμήσεις του χρήστη. Ο αλγόριθμος εξασφαλίζει ότι ο τρόπος και η σειρά ανάκτησης των αντικειμένων σέβεται τις προτιμήσεις του χρήστη, αποφεύγοντας τους ελέγχους υπεροχής, και προσπελάζοντας μόνο τα k βέλτιστα αντικείμενα, μία φορά το καθένα. Από διαφορετική οπτική, ο TBA ορίζει μια διάταξη επερωτήσεων που αποτελούν διαζεύξεις ατομικών συνθηκών επιλογής πάνω σε μοναδικά γνωρίσματα, και χρησιμοποιεί κατάλληλα κατώφλια τιμών για να σημάνει τη διακοπή της ανάκτησης των αντικειμένων, εξασφαλίζοντας ότι όλα τα εναπομείναντα αντικείμενα είναι χειρότερα των ανακτηθέντων. Εν προκειμένω, πραγματοποιούνται έλεγχοι υπεροχής μόνο για τα ήδη ανακτηθέντα αντικείμενα. Τόσο η αναλυτική μελέτη όσο και η πειραματική αποτίμηση καταδεικνύουν την υπεροχή των αλγορίθμων που παρουσιάζουμε έναντι των υφισταμένων σε όλες τις περιπτώσεις του προβλήματος. (EL)
Preference modelling and management has attracted considerable attention in the areas of Databases, Knowledge Bases and Information Retrieval Systems in recent years. This interest stems from the fact that a rapidly growing class of untrained lay users confront vast data collections, usually through the Internet, typically lacking a clear view of either content or structure, moreover, not even having a particular object in mind. Rather, they are attempting to discover potentially useful objects, in other words, objects that best suit their preferences. A modern information system, consequently, should enable users to quickly focus on the k best object according to their preferences. In this thesis, modelling preferences as binary relations, we introduce efficient algorithms for the evaluation of the top-k objects. Previous related work treated preference expressions as black boxes and dealt with the idea of exhaustively applying dominance tests among database objects in order to determine the best ones, resulting in quadratic costs. On the contrary, we advocate a query ordering based approach. Our key idea is to exploit the semantics of the input preference expression itself, in terms of both the operators and the preferences involved, to define an ordering over those queries, whose evaluation is necessary for the retrieval of the top-k objects. We introduce two novel algorithms, LBA and TBA. LBA defines an ordering over queries which are essentially conjunctions of atomic selection conditions, containing all attributes that the user preferences involve. The algorithm ensures that the way and order in which objects are fetched respect user preferences, avoiding any dominance testing, and accessing only the top-k objects, each of them only once. From a different angle, TBA defines an order of queries which are disjunctions of atomic selection conditions over single attributes, and uses appropriate threshold values to signal object fetching termination, ensuring that all remaining objects are worse than those fetched. Dominance tests are performed only for already retrieved objects. Analytical study and experimental evaluation show that our algorithms outperform existing ones under all problem instances. (EN)

text
Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης

Πανεπιστήμιο Κρήτης (EL)
University of Crete (EN)

2007-05-01
2007-10-11


Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)