Μέθοδοι βελτίωσης αποτελεσμάτων αναζήτησης στον παγκόσμιο ιστό

Abstract

The quality of a search engine depends mainly from the 10 first results that are presented as answer in a user’s question. The presentation order of the results has direct relation with the algorithm that rates the web pages of a search engine. In this thesis new methods of rating are proposed, that aim to the improvement of the quality of the results. We also introduce a method of personalized search in the World Wide Web, and an implicit metric of evaluation for the results of a search engine that does not require explicit information from the users. Finally we present a distributed crawler for the Web which selectively collects web pages, as well as the architecture and implementation of two search engines. More specific, three algorithms are proposed: the Compass Filter, the WordRank and the BlogRank. The Compass Filter is an algorithm that personalizes the results of a search, and gives priority in the web pages of web communities that already the user has visited in the past. The WordRank rates the web pages giving priority in those that link, and have similar content. The BlogRank utilizes the particular characteristics of the blogs (authors, subjects, news, dates of publication) and rates them based on their common attributes. It is experimentally proved that these three algorithms considerably improve the results that are presented to the users. The Success Index is presented in the experiments; a new metric for the evaluation of the quality for the results of a search engine. The Success Index uses the implicit feedback of the users, in order to give a rank to the quality of the results. We consider that the user expresses his criticism for the results of a search, with the web pages that he selects to view (which pages he selects, and with what order). We show experimentally that the mark that the Success Index computes, is similar with the rating of an explicit evaluation. We developed two search engines and a distributed web crawler, for the testing of the proposed algorithms and the evaluation metric.

Η ποιότητα μιας μηχανής αναζήτησης εξαρτάται κυρίως από τα 10 πρώτα αποτελέσματα που παρουσιάζονται ως απάντηση σε ένα ερώτημα του χρήστη. Η σειρά παρουσίασης των αποτελεσμάτων έχει άμεση σχέση με τον αλγόριθμο βαθμολόγησης (rating) ιστοσελίδων της μηχανής αναζήτησης. Στην διατριβή αυτή προτείνονται νέες μέθοδοι βαθμολόγησης ιστοσελίδων που αποσκοπούν στη βελτίωση της ποιότητας των αποτελεσμάτων των μηχανών αναζήτησης, και στην εξατομίκευση των αναζητήσεων στον Παγκόσμιο Ιστό (World Wide Web). Προτείνεται ένα μέτρο αξιολόγησης των αποτελεσμάτων της αναζήτησης που δεν απαιτεί ρητή πληροφορία από τους χρήστες, και αξιοποιεί τα υποκρυπτόμενα χαρακτηριστικά της συμπεριφοράς τους. Τέλος παρουσιάζεται μία κατανεμημένη εφαρμογή περιήγησης του Web η οποία επιλεκτικά συλλέγει ιστοσελίδες, καθώς και η υλοποίηση δύο μηχανών αναζήτησης. Συγκεκριμένα, προτείνονται τρεις αλγόριθμοι: ο Compass Filter, ο WordRank και ο BlogRank. Ο Compass Filter είναι αλγόριθμος που εξατομικεύει τα αποτελέσματα της αναζήτησης, και δίνει προτεραιότητα στις ιστοσελίδες των διαδικτυακών κοινοτήτων που έχει ήδη επισκεφτεί ο χρήστης στο παρελθόν. Ο WordRank βαθμολογεί τις ιστοσελίδες δίνοντας προτεραιότητα σε αυτές που συνδέονται μεταξύ τους, και έχουν όμοιο περιεχόμενο. Ο BlogRank αξιοποιεί τα ιδιαίτερα χαρακτηριστικά των blogs (όπως συντάκτες, θέματα, ειδήσεις, ημερομηνίες δημοσίευσης) και τα βαθμολογεί βάσει των κοινών ιδιοτήτων τους. Αποδεικνύεται πειραματικά ότι οι τρεις αυτοί αλγόριθμοι βελτιώνουν σημαντικά τα αποτελέσματα που παρουσιάζονται στους χρήστες. Στα πειράματα παρουσιάζεται ο Success Index, ένα νέο μέτρο για την αξιολόγηση της ποιότητας των αποτελεσμάτων μιας μηχανής αναζήτησης. Ο Success Index χρησιμοποιεί την υποκρυπτόμενη κριτική (implicit feedback) των χρηστών για να απεικονίσει την ποιότητα των αποτελεσμάτων. Θεωρούμε ότι ο χρήστης εκφράζει την κριτική του στα αποτελέσματα μίας αναζήτησης, με τις ιστοσελίδες που επιλέγει να δει (ποιες σελίδες επιλέγει, και με ποια σειρά). Δείχνουμε πειραματικά ότι ο βαθμός που αποδίδει ο Success Index είναι παρόμοιος με αυτόν μιας ρητής (explicit) αξιολόγησης. Για τον έλεγχο των προτεινόμενων αλγορίθμων και του μέτρου αξιολόγησης αναπτύχθηκαν δύο μηχανές αναζήτησης, και ένας κατανεμημένος παραμετρικός περιηγητής ιστού (web crawler).