Συντάχθηκε 14-10-2013 10:01
από Eleni Stamataki
Email συντάκτη: estamataki<στο>tuc.gr
Ενημερώθηκε:
-
Ιδιότητα: σύνταξη/αποχώρηση υπάλληλος.
Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΦΡΑΓΚΙΑΔΟΥΛΑΚΗ ΓΕΩΡΓΙΟΥ
με θέμα
Υλοποίηση Μηχανής Αναζήτησης βασισμένης στο PageRank με χρήση του Hadoop
Implementation of a Pagerank-based Search Engine using Hadoop
Τρίτη 15 Οκτωβρίου 2013, 11πμ
Αίθουσα Συνεδριάσεων Εργαστηρίου SoftNet, Κτίριο Επιστημών, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Καθηγητής Γαροφαλάκης Μίνως (επιβλέπων)
Καθηγητής Πετράκης Ευριπίδης
Επίκουρος Καθηγητής Δεληγιαννάκης Αντώνιος
Περίληψη
Οι μηχανές αναζήτησης αποτελούν δίχως αμφιβολία αναπόσπαστο κομμάτι του παγκόσμιου ιστού. Τα αποτελέσματα μίας αναζήτησης με βάση το επερώτημα (query) του εκάστοτε χρήστη προκύπτουν από τη συλλογή, την επεξεργασία και την αξιολόγηση τεράστιου όγκου δεδομένων. Επομένως, το μέγεθος της πληροφορίας που καλούμαστε να διαχειριστούμε μας οδηγεί στη χρησιμοποίηση του προγραμματιστικού μοτίβου Map-Reduce και της υλοποίησής του στο Hadoop, με σκοπό την παράλληλη εκτέλεση των απαιτούμενων διεργασιών. Μετά την ολοκλήρωση της συλλογής των δεδομένων χρησιμοποιώντας το Nutch ως web crawler, κατασκευάσαμε τη δομή Inverted Index στο κατανεμημένο σύστημα αρχείων HDFS. Εκμεταλλευόμενοι το λεκτικό περιεχόμενο των ιστοσελίδων, υπολογίσαμε scores όπως το Tf-Idf και η Ομοιότητα Συνημιτόνου (Cosine Similarity) ώστε να καταταχθούν οι σελίδες που προκύπτουν από queries διαφόρων κατηγοριών. Στη συνέχεια, προχωρήσαμε στην εξατομίκευση (personalization) του αλγορίθμου PageRank, ώστε να υπολογιστούν επιπλέον scores για όλες τις σελίδες της συλλογής μας, λαμβάνοντας υπόψιν τις προτιμήσεις των χρηστών του συστήματος. Οι τιμές PageRank είναι ανεξάρτητες από το εκάστοτε query και επηρεάζονται μόνο από τη δομή του γράφου (webgraph) που απεικονίζει τους συνδέσμους μεταξύ των σελίδων. Τέλος, έγινε ο συνδυασμός των παραπάνω μεθόδων αξιολόγησης, με αποτέλεσμα την εξαγωγή ενός ενοποιημένου score. Διεξήχθησαν πειραματικές αναζητήσεις με βάση διαφορετικές περιπτώσεις, ώστε να προκύψουν όσο το δυνατόν πιο χρήσιμα συμπεράσματα σχετικά με την υλοποίησή μας.
Abstract
Search engines are undoubtedly an integral part of the Web. The search results based on the query of each user are derived from the collection, processing and evaluation of huge amounts of data. Therefore, the size of the information we need to manage leads us to the use of MapReduce programming model and its implementation on Hadoop for parallel execution of the necessary processes. After completion of data collection using Nutch web crawler, the Inverted Index structure was constructed in the distributed file system HDFS. Taking advantage of the web pages' text content, we calculated scores such as Tf-Idf and Cosine Similarity in order to classify the pages resulting from queries of various categories. Afterwards, we proceeded to the personalization of PageRank algorithm to calculate additional scores for all pages of the collection, taking into account the system users' preferences. The PageRank values are independent of each query and they are only influenced by the structure of the webgraph that represents the links between the pages. Finally, the above ranking methods were combined, leading to the calculation of a unified score. Experimental searches were conducted under different conditions in order to obtain the most useful conclusions possible about our implementation.
Συνημμένα:
-
ΑΝΑΚΟΙΝΩΣΗ ΦΡΑΓΚΙΑΔΟΥΛΑΚΗ ΓΕΩΡΓΙΟΥ.docx
Μεταφορτώσεις: 165,
Μέγεθος: 28 KB application/vnd.openxmlformats-officedocument.wordprocessingml.document
