| Περίληψη |
Οι μηχανές αναζήτησης του παγκοσμίου ιστού χρησιμοποιούν διάφορες τεχνικές για να μειώσουν τους χρόνους απόκρισης, το κόστος της επεξεργασίας επερωτήσεων και τις απαιτήσεις σε υλικό. Γενικά η αποτίμηση μίας επερώτησης απαιτεί την επεξεργασία (ανάκτηση και διαβάθμιση) μεγάλου όγκου δεδομένων του ευρετηρίου της μηχανής, ιδιαίτερα όταν οι όροι της επερώτησης έχουν μεγάλες λίστες εμφάνισης. Ένας από τους πιο αποτελεσματικούς τρόπους βελτίωσης της απόδοσης μίας μηχανής είναι η χρήση τεχνικών caching οι οποίες διακρίνονται σε δύο μεγάλες κατηγορίες: caches αποτελεσμάτων (Result Caches, για συντομία RC) και caches όρων ευρετηρίου (Posting List Caches, για συντομία PLC). Μία RC μας επιτρέπει να απαντάμε πολύ γρήγορα- και χωρίς να χρειάζεται να ανατρέξουμε στο ευρετήριο - επερωτήσεις που έχουν υποβληθεί αυτούσιες στο παρελθόν. Από την άλλη, μία PLC επιτυγχάνει μεγαλύτερο ποσοστό επιτυχών επισκέψεων (hits), ωστόσο δεν αποφεύγει το κόστος της αποτίμησης των επερωτήσεων.
Η παρούσα μεταπτυχιακή εργασία εισάγει μια νέα τεχνική caching που ονομάζεται SCRC (Set Cover Results Cache), η οποία συνδυάζει τα ατού της RC και της PLC. Συγκεκριμένα, για κάθε μία επερώτηση που υποβάλλεται εάν η SCRC περιέχει μία ισοδύναμη επερώτηση τότε η απάντηση της επιστρέφεται άμεσα (όπως σε μία Result Cache), διαφορετικά επιχειρείται αποτίμηση συνδυάζοντας τις απαντήσεις άλλων cached (υπο-)επερωτήσεων, εκ τούτου αποτελεί γενίκευση της PLC. Ανάγουμε την διαδικασία εύρεσης των πιο κατάλληλων cached υποεπερωτήσεων στην επίλυση του προβλήματος «Ακριβούς Κάλυψης Συνόλων» (Exact Set Cover Problem) και χρησιμοποιούμε έναν άπληστο (greedy) αλγόριθμο για την προσεγγιστική επίλυσή του. Η ορθότητα των αποτελεσμάτων που προκύπτουν από αυτή τη διαδικασία αποτίμησης επερωτήσεων, εξαρτάται από το εάν η συνάρτηση βαθμολόγησης είναι αθροιστικά αποσυνθέσιμη (additively decomposable), και δείχνουμε ότι αρκετά μοντέλα ανάκτησης που παραδοσιακά έχουν χρησιμοποιηθεί στην Ανάκτηση Πληροφορίας και στις μηχανές αναζήτησης (διανυσματικό μοντέλο, Okapi BM25, καθώς και υβριδικά μοντέλα ανάκτησης) βασίζονται σε τέτοιες συναρτήσεις διαβάθμισης.
Για να εκτιμήσουμε την αποδοτικότητα της προτεινόμενης cache σε πραγματικές συνθήκες, αναλύσαμε ροές επερωτήσεων (query logs) πραγματικών μηχανών αναζήτησης (Excite, AllTheWeb, Altavista) με μέτρα που ορίσαμε, και τα αποτελέσματα έδειξαν ότι περί το 35% των επερωτήσεων μπορούν να εκφραστούν ως ένωση άλλων υποβεβλημένων επερωτήσεων. Βάσει αυτών των στοιχείων προτείναμε και αξιοποιήσαμε τεχνικές γεμίσματος της cache για αύξηση της επιτάχυνσης που επιτυγχάνει η SCRC. Επιπροσθέτως, και για να αξιοποιήσουμε το γεγονός ότι η πλειονότητα των χρηστών εξετάζει μόνο τις πρώτες σελίδες αποτελεσμάτων, ορίσαμε και μία παραλλαγή της SCRC, την Top-K SCRC, η οποία αποθηκεύει μόνο τα Κ κορυφαία αποτελέσματα των απαντήσεων και ορίσαμε μέτρα για το χαρακτηρισμό της ποιότητας των κορυφαίων-Κ απαντήσεων που προκύπτουν από τον συνδυασμό υποερωτημάτων.
Οι παραπάνω τεχνικές αξιολογήθηκαν συγκριτικά στη μηχανή αναζήτησης Μίτος και σε δύο εκδόσεις του ευρετηρίου της: μία που βασίζεται σε ένα Αντικειμενο-Σχεσιακό Σύστημα Διαχείρισης Βάσεων Δεδομένων (Object-Relational DBMS), και μία που βασίζεται σε ανεστραμμένο αρχείο (inverted file). Τα αποτελέσματα έδειξαν ότι σε μοντέλα βέλτιστου ταιριάσματος η SCRC επιτυγχάνει την διπλάσια μέση επιτάχυνση σε σχέση με την RC, και την τριπλάσια μέση επιτάχυνση σε σχέση με την PLC.
|
Set cover-based results caching for best match retrieval models
