Παρόλο που οι Μηχανές Αναζήτησης ευρετηριάζουν τεράστιους όγκους ιστοσελίδων (εγγράφων γενικότερα), για τις επερωτήσεις των χρηστών επιστρέφουν μόνο μια γραμμική λίστα «επιτυχιών» (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)
