| Περίληψη |
Παρόλο που οι Μηχανές Αναζήτησης ευρετηριάζουν τεράστιους όγκους ιστοσελίδων (εγγράφων γενικότερα), για τις επερωτήσεις των χρηστών επιστρέφουν μόνο μια γραμμική λίστα «επιτυχιών» (hits). Αν και αυτό να είναι ικανοποιητικό για τις ανάγκες τις επικεντρωμένης αναζήτησης (focalized search), αυτού του τύπου οι αποκρίσεις δεν παρέχουν στο χρήστη ούτε εποπτεία των επιτυχιών, ούτε τη δυνατότητα ευέλικτης εξερεύνησής τους, ούτε κάποια βαθύτερη ανάλυση των περιεχομένων τους.
Ένας τρόπος για παροχή προηγμένης πλοήγησης, και συνάμα αξιοποίησης των (σημασιολογικά) δομημένων δεδομένων που είναι πλέον διαθέσιμα, είναι ο εμπλουτισμός της διαδικασίας αναζήτησης με εξόρυξη οντοτήτων επί του περιεχομένου των επιτυχιών, όπου οι οντότητες που μας ενδιαφέρουν μπορούν να προσδιοριστούν από σημασιολογικές πηγές. Αυτός ο εμπλουτισμός δίνει στο χρήστη μια εποπτεία του πληροφοριακού χώρου των επιτυχιών, η οποία επίσης του επιτρέπει τη σταδιακή μείωση τους ώστε να μπορεί εκείνος να εντοπίσει τις επιθυμητές επιτυχίες (hits), ακόμα και αν αυτές είναι πολύ πίσω στην κατάταξη.
Σε αυτήν τη διατριβή θεωρούμε το γενικό σενάριο όπου αυτές οι υπηρεσίες προσφέρονται ως μέτα-υπηρεσίες (ήτοι επί συστημάτων που προσφέρουν αναζήτηση μέσω λέξεων κλειδιών), χωρίς να απαιτείται ο εκ των προτέρων ευρετηριασμός των υποκείμενων συλλογών εγγράφων. Για να κάνουμε εφικτή την παροχή τέτοιων υπηρεσιών για μεγάλους όγκους αποτελεσμάτων, χρησιμοποιούμε το μοντέλο κατανεμημένου υπολογισμού MapReduce επί μιας υποδομής Υπολογιστικού Νέφους (Amazon EC2). Συγκεκριμένα δείχνουμε πως ο απαιτούμενος υπολογισμός μπορεί να παραγοντοποιηθεί σε συναρτήσεις MapReduce και παρουσιάζουμε δυο διαφορετικές διαδικασίες υπολογισμού, την «μονοκόμματη» (στο εξής SJ από το single-Job) και την «αλυσιδωτή» (CJ, από το chain-job). Επιπλέον, προσδιορίζουμε κριτήρια που καθορίζουν την επιλογή και κατάταξη των, συχνά πολυπληθών, ευρεθέντων οντοτήτων.
Στη συνέχεια, αναφέρουμε εκτενή πειραματικά αποτελέσματα σχετικά με την επιτευχθείσα επιτάχυνση σε διαφορετικές ρυθμίσεις. Δείχνουμε ότι με τη διαδικασία SJ επιτυγχάνουμε επιτάχυνση (speedup) η οποία είναι κοντά στην θεωρητικά βέλτιστη επιτάχυνση (2,5-19,7% χαμηλότερη από την θεωρητικά βέλτιστη για ένα σύνολο δεδομένων 300MB και από 2 έως 8 Amazon EC2 VMs αντίστοιχα) και αναλύουμε αυτή την απόκλιση. Ενδεικτικά, μπορούμε να επιτύχουμε επιτάχυνση έως και x6.4 με 8 EC2 VMs κατά την ανάλυση 4.365 «επιτυχιών» (hits) (που αντιστοιχούν σε 300MB) με συνολικό χρόνο εκτέλεσης λιγότερο από 7 λεπτά (μια ανέφικτη διαδικασία από ένα μόνο μηχάνημα λόγω των υψηλών απαιτήσεων, υπολογιστικών και μνήμης). Η διαδικασία CJ παρουσιάζει κάπως χαμηλότερη κλιμακωσιμότητα σε σύγκριση με την SJ (x5.66 στις 8 EC2 VMs) με μεγαλύτερο συνολικό χρόνο εκτέλεσης (περίπου 30 δευτερόλεπτα περισσότερο για ένα σύνολο δεδομένων 300MB), ο οποίος οφείλεται στην επιβάρυνση από τη χρήση δύο αντί της μιας MapReduce διεργασίας. Από την άλλη, ένα ποιοτικό πλεονέκτημα της διαδικασίας CJ (σε σύγκριση με την SJ) είναι ότι προσφέρει μια γρήγορη προεπισκόπηση των αποτελεσμάτων της ανάλυσης.
Μια ακόμη σημαντική συνεισφορά αυτής της διατριβής είναι η εκτενής αξιολόγηση των θεμάτων διαμόρφωσης (configuration and tuning), μια διάσταση η οποία συχνά παραβλέπεται ή δεν μελετάται επαρκώς, η οποία όμως είναι κρίσιμη για την επίδοση και την καλή χρησιμοποίηση των πόρων γενικότερα. Δείξαμε ότι οι προτεινόμενες διαδικασίες υπολογισμού χρησιμοποιούν βέλτιστα τους υπολογιστικούς πόρους (πλήρης χρησιμοποίηση των διαθέσιμων CPU, αποτελεσματική κατανομή μνήμης), και ότι δεν υπάρχει κάποια αδικαιολόγητη επιβάρυνση (π.χ. στη συλλογή απορριμμάτων, άσκοπα ξεκινήματα/τερματισμοί των JVMs, ποσοστό ανισορροπίας, μεταξύ του χρόνου ολοκλήρωσης των τελευταίων διαδικασιών, κ.α.).
|
Entity-based Summarization of Web Search Results using MapReduce
