Engineering search algorithms for web data

Abstract

The massive growth of the information produced and disseminated through the Worldwide Web (WWW) has rendered Information Retrieval (IR) one of the most important and challenging research fields in modern computer science. As hundreds of Gigabytes are being published on the Web in a daily basis and billions of users require access to this huge amount of data, search engines have to constantly scale up in terms of both efficiency and effectiveness. In this dissertation we present novel engineering algorithms which contribute to the solution of key problems related to the current Web search engines. These algorithms lead to improvements in the query throughput of these systems (that is, the rate at which they serve the incoming queries), and the quality of the results they produce in response to these queries. In particular, we introduce PFBC, an efficient algorithm for organizing and compressing the positional data stored within an inverted index. In the sequel, we expand PFBC with the aim of supporting additional data within an inverted list posting such as the field (or zone) of a document where a word occurs. The new algorithm, namely TZP, exhibits a wide range of advantages against the current state-of-the-art generic integer compression methods. Based on TZP, we introduce BM25TOPF, a probabilistic ranking function which in contrast to the existing probabilistic functions of the Okapi family, takes into consideration the word ordering in the query, and combines term proximity with zone scoring. Furthermore, we examine the essential problems related to vertical searching, that is, searching for information by accounting only a specific portion of the Web. In particular, we study the problem of quantifying the influence flow in Blogosphere by taking into consideration the particular features which characterize Blogosphere such as the rapid blog post production and the temporal instability of this environment. We propose three such metrics: MEIBI, MEIBIX and the BP/BI-index. In the sequel, we examine how the proposed models for quantifying the bloggers’ influence can be employed by a vertical blog search engine to improve the quality of the generated results. Another vertical search system which gained our attention is academic search engines. In this dissertation we conducted a three-way research; The first part includes proposal of new scientometrics that is, metrics which measure the quality of the work of a scientist. We introduce the f-index, a novel metric which embodies coterminal citations and presents them as a generalization of self-citations and of co-citation. In addition, we introduce the topic-sensitive extensions, special versions of the most important scientometrics which attempt to evaluate the work of a scientist in only one particular research field. In the sequel, we discuss four strategies for computing these metrics in large-scale datasets by using a special-purpose algorithm parallelization framework (Hadoop/MapReduce). Finally, our last contribution regards a supervised machine-learning algorithm for classifying research papers. The results of all these three parts of our research can be utilized by all the current academic search engines and digital libraries to enhance their functionality. The final contribution of this dissertation concerns the problem of rank aggregation, or rank fusion. Here we present a family of algorithms which provide an effective manner for combining and re-ranking the results coming from multiple search engines. The new algorithms, QuadRank and the KE family take into consideration both statistical data (i.e. the individual rankings of each item and the number of its appearances) and document-related information (i.e. zone weighting, URL, etc.). All these algorithms have been implemented within QuadSearch, a prototype metasearch engine which we have developed as a testbed for evaluating new rank aggregation methods and generic solutions related to the wider problem of metasearching.

Η μεγάλη διόγκωση της πληροφορίας που παράγεται και διακινείται μέσω του Παγκόσμιου Ιστού κατέστησε το επιστημονικό πεδίο της Ανάκτησης Πληροφορίας (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, ένα πρωτότυπο σύστημα μετα-αναζήτησης που αναπτύξαμε με σκοπό την αξιολόγηση νέων μεθόδων σύγκρισης κατατάξεων, αλλά και γενικών λύσεων σε προβλήματα που σχετίζονται με το ευρύτερο ζήτημα της μετα-αναζήτησης.