| Περίληψη |
Τα τελευταία χρόνια, η μοντελοποίηση και η διαχείριση των προτιμήσεων έχουν προσελκύσει ιδιαίτερη προσοχή στους τομείς των Βάσεων Δεδομένων, των Βάσεων Γνώσης και των Συστημάτων Ανάκτησης Πληροφοριών. Αυτό το ενδιαφέρον πηγάζει από το γεγονός ότι ολοένα και περισσότεροι μη ειδικευμένοι κοινοί χρήστες έρχονται σε επαφή με τεράστιες συλλογές δεδομένων, συνήθως μέσω του Διαδικτύου, χωρίς, κατά κανόνα, να έχουν μια σαφή άποψη ούτε για το περιεχόμενο ούτε και για τη δομή της πληροφορίας, χωρίς καν να έχουν ένα συγκεκριμένο αντικείμενο υπ? όψει τους. Πιο πολύ προσπαθούν να ανακαλύψουν αντικείμενα που ενδεχομένως θα τους είναι χρήσιμα, αντικείμενα, με άλλα λόγια, που ταιριάζουν καλύτερα στις προτιμήσεις τους. Συνεπώς, ένα σύγχρονο πληροφοριακό σύστημα θα πρέπει να διευκολύνει τους χρήστες στο γρήγορο εντοπισμό των k βέλτιστων αντικειμένων βάσει των προτιμήσεων τους. Στην εργασία αυτή, μοντελοποιώντας τις προτιμήσεις ως δυαδικές σχέσεις, εισάγουμε αποδοτικούς αλγορίθμους αποτίμησης των k βέλτιστων αντικειμένων. Η έως τώρα σχετική έρευνα, αντιμετώπιζε τις εκφράσεις επί προτιμήσεων ως «μαύρα κουτιά» και εφάρμοζε την ιδέα των εξαντλητικών διαδοχικών ελέγχων υπεροχής μεταξύ των αντικειμένων μιας βάσης δεδομένων για τον προσδιορισμό των καλύτερων εξ? αυτών, γεγονός που οδηγούσε σε τετραγωνικά ως προς τον αριθμό των αντικειμένων κόστη. Αντιθέτως, εμείς υποστηρίζουμε μια προσέγγιση που βασίζεται στη διάταξη επερωτήσεων. Η κύρια ιδέα μας βασίζεται στην εκμετάλλευση της σημασιολογίας μιας έκφρασης από προτιμήσεις, σε ό,τι αφορά τόσο τους εμπλεκόμενους τελεστές όσο και τις εμπλεκόμενες προτιμήσεις, με σκοπό τον ορισμό μιας διάταξης μεταξύ εκείνων των επερωτήσεων, των οποίων η αποτίμηση είναι αναγκαία, ώστε να ανακτηθούν τα k βέλτιστα αντικείμενα. Παρουσιάζουμε δύο πρωτότυπους αλγόριθμους, τους LBA και TBA. Ο LBA ορίζει μια διάταξη επερωτήσεων, οι οποίες ουσιαστικά αποτελούν συζεύξεις ατομικών συνθηκών επιλογής, συμπεριλαμβάνοντας όλα τα γνωρίσματα που εμπλέκονται στις προτιμήσεις του χρήστη. Ο αλγόριθμος εξασφαλίζει ότι ο τρόπος και η σειρά ανάκτησης των αντικειμένων σέβεται τις προτιμήσεις του χρήστη, αποφεύγοντας τους ελέγχους υπεροχής, και προσπελάζοντας μόνο τα k βέλτιστα αντικείμενα, μία φορά το καθένα. Από διαφορετική οπτική, ο TBA ορίζει μια διάταξη επερωτήσεων που αποτελούν διαζεύξεις ατομικών συνθηκών επιλογής πάνω σε μοναδικά γνωρίσματα, και χρησιμοποιεί κατάλληλα κατώφλια τιμών για να σημάνει τη διακοπή της ανάκτησης των αντικειμένων, εξασφαλίζοντας ότι όλα τα εναπομείναντα αντικείμενα είναι χειρότερα των ανακτηθέντων. Εν προκειμένω, πραγματοποιούνται έλεγχοι υπεροχής μόνο για τα ήδη ανακτηθέντα αντικείμενα. Τόσο η αναλυτική μελέτη όσο και η πειραματική αποτίμηση καταδεικνύουν την υπεροχή των αλγορίθμων που παρουσιάζουμε έναντι των υφισταμένων σε όλες τις περιπτώσεις του προβλήματος.
|
Top-k Αλγόριθμοι Βασισμένοι Σε Διατάξεις Επερωτήσεων Για Ποιοτικώς Καθορισμένες Προτιμήσεις
