Engineering search algorithms for web data
Authors: Ακριτίδης Λεωνίδας 
Published: January 2014

Η μεγάλη διόγκωση της πληροφορίας που παράγεται και διακινείται μέσω του Παγκόσμιου Ιστού κατέστησε το επιστημονικό πεδίο της Ανάκτησης Πληροφορίας (Information Retrieval, IR) ένα από τα σημαντικότερα στη μοντέρνα επιστήμη των Υπολογιστών. Καθώς εκατοντάδες gigabytes δημοσιεύονται στον Παγκόσμιο Ιστό σε καθημερινή βάση και δισεκατομμύρια χρηστών απαιτούν άμεση πρόσβαση στην παραχθείσα πληροφορία, οι σύγχρονες μηχανές αναζήτησης πρέπει να επιτυγχάνουν συνεχή κλιμάκωση τόσο σε αποτελεσματικότητα, όσο και σε αποδοτικότητα. Σε αυτή τη διατριβή παρουσιάζουμε νέους και καινοτόμους αλγορίθμους οι οποίοι συνεισφέρουν στην επίλυση σημαντικών προβλημάτων που σχετίζονται με τις τρέχουσες μηχανές αναζήτησης. Οι αλγόριθμοι που παρουσιάζονται εδώ οδηγούν σε βελτίωση τόσο της ταχύτητας απάντησης των ερωτημάτων (δηλαδή του ρυθμού με τον οποίο οι μηχανές αναζήτησης εξυπηρετούν τα εισερχόμενα ερωτήματα), όσο και της ποιότητας των αποτελεσμάτων που επιστρέφουν οι μηχανές σε απόκριση αυτών των ερωτημάτων. Πιο συγκεκριμένα, εισάγουμε τον PFBC, ένα αποδοτικό αλγόριθμο για την οργάνωση και τη συμπίεση των δεδομένων θέσης που είναι αποθηκευμένα στο ανεστραμμένο ευρετήριο μιας μηχανής αναζήτησης. Στη συνέχεια, επεκτείνουμε τον PFBC αλγόριθμο με σκοπό την υποστήριξη επιπρόσθετης πληροφορίας μέσα σε μια ανεστραμμένη λίστα του ευρετηρίου. Η επιπρόσθετη πληροφορία αφορά στο πεδίο (ή στη ζώνη) ενός εγγράφου μέσα στο οποίο συναντάται μία λέξη. Ο νέος αλγόριθμος που ονομάζεται ΤΖΡ, παρουσιάζει ένα μεγάλο εύρος πλεονεκτημάτων έναντι των τρεχουσών, κορυφαίων και γενικών μεθόδων συμπίεσης ακεραίων. Με βάση τον αλγόριθμο ΤΖΡ εισάγουμε την BM25TOPF πιθανοτική συνάρτηση κατάταξης η οποία σε αντίθεση με τις υπάρχουσες συναρτήσεις της οικογένειας Okapi, λαμβάνει υπόψη της τη σειρά με την οποία διατάσσονται οι λέξεις στα υποβληθέντα ερωτήματα και συνδυάζει την εγγύτητα όρων (term proximity) και την απόδοση βάρους στις ζώνες (zone weighting). Επιπλέον, εξετάζουμε ορισμένα από τα πιο ουσιαστικά προβλήματα που σχετίζονται με τις κάθετες αναζητήσεις, δηλαδή τις αναζητήσεις που πραγματοποιούνται λαμβάνοντας υπόψη μόνο ένα συγκεκριμένο τμήμα του Παγκόσμιου Ιστού. Μελετάμε το πρόβλημα της ποσοτικοποίησης της ροής της επιρροής στη Blogosphere συμπεριλαμβάνοντας υπόψιν τα ιδιαίτερα στοιχεία που τη χαρακτηρίζουν όπως την ταχύτατη παραγωγή εγγράφων και τη χρονική αστάθεια του περιβάλλοντος. Προτείνουμε τρία διαφορετικά μετρικά: το ΜΕΙΒΙ, το ΜΕΙΒΙΧ και το δείκτη ΒΡ/ΒΙ. Στη συνέχεια εξετάζουμε μεθοδολογίες με τις οποίες είναι δυνατή η εκμετάλλευση των προτεινόμενων μοντέλων από μία κάθετη μηχανή αναζήτησης ιστολογιών, ώστε να βελτιωθεί η ποιότητα των παραγόμενων αποτελεσμάτων. Ένα άλλο κάθετο σύστημα αναζήτησης το οποίο κέρδισε την προσοχή μας είναι οι ακαδημαϊκές μηχανές αναζήτησης. Η έρευνα που πραγματοποιήσαμε σε αυτή τη διατριβή συγκροτείται από τρία διαφορετικά μέτωπα: Το πρώτο μέτωπο περιλαμβάνει προτάσεις νέων βιβλιομετρικών δεικτών, δηλαδή μετρικών τα οποία επιχειρούν να μετρήσουν την αντικειμενική αξία της συνολικής εργασίας ενός επιστήμονα. Εισάγουμε το δείκτη f (findex) ο οποίος ενσωματώνει την έννοια των συν-τερματικών αναφορών και τις παρουσιάζει σαν μία γενίκευση των αυτό-αναφορών (self-citations) και των συναναφορών (co-citations). Επιπροσθέτως, εισάγουμε νέες επεκτάσεις στους πιο διαδεδομένους βιβλίο μετρικούς δείκτες, οι οποίες επιτρέπουν την αξιολόγηση του επιστημονικού έργου κάθε ερευνητή κατά επιστημονικό πεδίο. Στο επόμενο στάδιο παρουσιάζουμε τέσσερις στρατηγικές για τον παράλληλο υπολογισμό των βιβλιομετρικών δεικτών σε μεγάλα σύνολα δεδομένων, χρησιμοποιώντας το Hadoop/MapReduce, ένα γενικού σκοπού σύστημα κατανομής αλγορίθμων σε πολυπληθείς ομάδες υπολογιστών. Στο τρίτο και τελικό στάδιο παρουσιάζουμε ένα νέο αλγόριθμο εκμάθησης μηχανής (machine-learning algorithm, MLA) για την κατηγοριοποίηση των ερευνητικών άρθρων. Τα αποτελέσματα και των τριών μετώπων έρευνας που παρουσιάζονται εδώ μπορούν να χρησιμοποιηθούν από τις σύγχρονες ακαδημαϊκές μηχανές αναζήτησης και τις ψηφιακές βιβλιοθήκες ώστε να βελτιώσουν την ποιότητα των παρεχομένων υπηρεσιών τους. Η τελευταία συνεισφορά που παρουσιάζουμε σε αυτή τη διατριβή αφορά στο πρόβλημα της ενοποίησης και της σύγκρισης λιστών αποτελεσμάτων. Παρουσιάζουμε μία οικογένεια αλγορίθμων οι οποίοι παρέχουν αποτελεσματικό συνδυασμό και ανακατάταξη των αποτελεσμάτων που προέρχονται από πολλαπλές διαφορετικές μηχανές αναζήτησης. Εισάγουμε τη μέθοδο QuadRank και την οικογένεια ΚΕ τα οποία λαμβάνουν υπόψιν τους τόσο στατιστικά δεδομένα (όπως τις μεμονωμένες κατατάξεις κάθε αντικειμένου και το πλήθος των εμφανίσεων του), όσο και πληροφορίες σχετικές με τα ανακτηθέντα έγγραφα (ζώνες εμφάνισης των όρων αναζήτησης, URL, κλπ). Οι αλγόριθμοι αυτοί έχουν υλοποιηθεί μέσα στην QuadSearch, ένα πρωτότυπο σύστημα μετα-αναζήτησης που αναπτύξαμε με σκοπό την αξιολόγηση νέων μεθόδων σύγκρισης κατατάξεων, αλλά και γενικών λύσεων σε προβλήματα που σχετίζονται με το ευρύτερο ζήτημα της μετα-αναζήτησης.