Relevance and diversity-based ranking in network-centric information management systems

Abstract

With the explosion of the amount of information currently available online, locating valuable or important information can prove out to be an overwhelming task. This abundance of accessible information creates the need for developing methods towards selecting and presenting to users representative subsets. Various ranking techniques have been developed in the past, to allow users to quickly access what is most useful to them. Ranking of information is usually based on some notion of relevance of each specific piece of information, or item, to the user needs. Ranking based solely on relevance, however, may lead to enhancing the overspecialization problem, i.e., the retrieval of too homogeneous results for a user query. For this reason, retrieving diverse results, i.e., items that are different to each other, has recently attracted great attention as a means to complement relevance-based ranking and increase the quality of results retrieved by information systems. Selecting diverse items has been shown to be an NP-hard problem. This PhD thesis concerns the development, implementation and evaluation of models, algorithms and techniques for the ranking of information being presented to users of network-centric information management systems. This ranking is based on the importance of each piece of information. We consider that importance is influenced by both relevance to user information needs and diversity. Relevance is important so that users are only presented with the most useful results according to their needs, while diversity ensures that the received results do not all contain similar information. We focus on two different axes: (i) diversifying dynamic data and (ii) diversifying data based on dissimilarity and coverage. In addition to this, we also develop a system prototype, called Poikilo (from the Greek ‘‘ποικίλο’’, meaning ‘‘diverse’’) for evaluating the results of various diversification models and algorithms.

Ο όγκος της πληροφορίας που γίνεται καθημερινά διαθέσιμος στους χρήστες διαδικτυακών συστημάτων είναι τεράστιος. Ο εντοπισμός χρήσιμης πληροφορίας μέσα σε αυτόν τον όγκο δεδομένων μπορεί να αποδειχθεί εξαιρετικά δύσκολος. Για τον λόγο αυτό, διάφορες τεχνικές διαβάθμισης πληροφορίας έχουν προταθεί κατά καιρούς, οι οποίες στοχεύουν στη διευκόλυνση των χρηστών κατά την αναζήτηση πληροφορίας. Η διαβάθμιση της πληροφορίας είναι συνήθως βασισμένη σε κάποια έννοια συνάφειας ως προς το ερώτημα που έχει θέσει ο χρήστης. Ωστόσο, η διαβάθμιση με βάση αποκλειστικά τη συνάφεια μπορεί να ενισχύσει το πρόβλημα της υπερ-εξειδίκευσης, δηλαδή την ανάκτηση αποτελεσμάτων που είναι μεν σχετικά το καθένα με το ερώτημα του χρήστη αλλά είναι πολύ όμοια μεταξύ τους. Η ποικιλομορφία των δεδομένων έχει αναδειχθεί τα τελευταία χρόνια ως ένας τρόπος αντιμετώπισης του προβλήματος της υπερ-εξειδίκευσης. Πέραν αυτού, πολλές φορές, οι χρήστες θέτουν ερωτήματα με μία διάθεση εξερεύνησης, δηλαδή ενδιαφέρονται να ανακτήσουν αποτελέσματα τα οποία να καλύπτουν διαφορετικές οπτικές γωνίες του ερωτήματός τους. Η αύξηση της ποικιλομορφίας των αποτελεσμάτων δρα συμπληρωματικά με τη συνάφειά τους για τη βελτίωση της ποιότητας του αποτελέσματος που παρουσιάζεται στον χρήστη. Γενικά, το πρόβλημα της επιλογής ποικιλόμορφων αποτελεσμάτων ορίζεται ως εξής: δοσμένου ενός συνόλου P αποτελεσμάτων, σκοπός είναι να βρούμε ένα υποσύνολο S του P τέτοιο ώστε να μεγιστοποιείται η ποικιλομορφία των επιλεγμένων αποτελεσμάτων, σύμφωνα με κάποιο κριτήριο ποικιλομορφίας. Στόχος αυτής της διατριβής είναι η ανάπτυξη, υλοποίηση και αξιολόγηση μοντέλων, αλγορίθμων και τεχνικών για την υποστήριξη διαβάθμισης με βάση τόσο τη συνάφεια όσο και την ποικιλομορφία των αποτελεσμάτων σε δίκτυο-κεντρικά συστήματα διαχείρισης πληροφορίας. Επικεντρώνουμε το ενδιαφέρον μας κυρίως πάνω σε δύο άξονες: (i) την ποικιλομορφία πληροφορίας που αλλάζει δυναμικά στο χρόνο και (ii) την ποικιλομορφία πληροφορίας με βάση την ανομοιότητα και την κάλυψη.