Οντοκεντρική σύνοψη αποτελεσμάτων μηχανών αναζήτησης με τη χρήση MapReduce

 
Το τεκμήριο παρέχεται από τον φορέα :
Πανεπιστήμιο Κρήτης
Αποθετήριο :
E-Locus Ιδρυματικό Καταθετήριο
δείτε την πρωτότυπη σελίδα τεκμηρίου
στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
κοινοποιήστε το τεκμήριο




2013 (EL)
Entity-based Summarization of Web Search Results using MapReduce
Οντοκεντρική σύνοψη αποτελεσμάτων μηχανών αναζήτησης με τη χρήση MapReduce

Κίτσος, Ιωάννης Γ.

Τζίτζικας, Ιωάννης

Παρόλο που οι Μηχανές Αναζήτησης ευρετηριάζουν τεράστιους όγκους ιστοσελίδων (εγγράφων γενικότερα), για τις επερωτήσεις των χρηστών επιστρέφουν μόνο μια γραμμική λίστα «επιτυχιών» (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, ποσοστό ανισορροπίας, μεταξύ του χρόνου ολοκλήρωσης των τελευταίων διαδικασιών, κ.α.). (EL)
Although Web Search Engines index and provide access to huge amounts of documents, user queries typically return only a linear list of hits. While this is often satisfactory for focalized search, it does not provide an exploration or deeper analysis of the results. One way to achieve advanced exploration facilities, while exploiting also the structured (and semantic) data that are now available, is to enrich the search process with entity mining over the full contents of the search results where the entities of interest can be specified by semantic sources. Such services provide the users with an initial overview of the information space, allowing them to gradually restrict it until locating the desired hits, even if they are low ranked. In this thesis we consider a general scenario of providing such services as meta- services (that is, layered over systems that support keywords search) without apriori indexing of the underlying document collection(s). To make such services feasible for large amounts of data we use the MapReduce distributed computation model on a Cloud infrastructure (Amazon EC2). Specifically, we show how the required computational tasks can be factorized and expressed as MapReduce functions and we introduce two different evaluation procedures the Single-Job (SJ) and the Chain-Job (CJ). Moreover, we specify criteria that determine the selection and ranking of the (often numerous) discovered entities. In the sequel, we report experimental results about the achieved speedup in various settings. We show that with the SJ procedure the achieved speedup is close to the theoretically optimal speedup (2, 5% − 19, 7% lower than the optimal for a 300MB dataset and from 2 up to 8 Amazon EC2 VMs respectively) and justify this difference. Indicatively, we achieve a speedup of up to x6.4 on 8 EC2 VMs when analyzing 4, 365 hits (corresponding to 300MB) with a total runtime of less than 7 minutes (an infeasible task when using a single machine due to high computational and memory requirements). CJ exhibits somewhat lower scalability compared to SJ (x5.66 on 8 EC2 VMs) with a longer total runtime (about 30 secs more for a 300MB dataset) due to the overhead of using two rather than one MapReduce job. On the other hand, CJ offers the qualitative benefit of providing a quick preview of the results of the analysis. Another important contribution of this thesis is a thorough evaluation of platform configuration and tuning, an aspect that is often disregarded and inadequately addressed in prior work, but crucial for the efficient utilization of resources. We show that the proposed evaluation methods utilize well the resources (fully utilized CPU, efficient memory allocation), and the tasks do not have an unreasonably high overhead (e.g. garbage collection, unnecessarily startup/teardown of JVMs during task initialization and termination, imbalance in last-task execution times). (EN)

text
Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης

Πανεπιστήμιο Κρήτης (EL)
University of Crete (EN)

Αγγλική γλώσσα

2013-11-15


Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης



*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.