Τεχνικές ευρετηριοποίησης και συσταδοποίησης για την αποδοτική αποτίμηση ερωτημάτων σε συστήματα ομότιμων κόμβων
Authors: Κολωνιάρη Γεωργία 
Published: January 2014

Σήμερα, εξαιτίας της ευρείας διάδοσης που παρουσιάζουν εφαρμογές όπως τα συστήματα ομότιμων κόμβων (peer-to-peer systems) και τα κοινωνικά δίκτυα (social networks), σημαντικό ενδιαφέρον επικεντρώνεται στη μελέτη κατανεμημένων συστημάτων μεγάλης κλίμακας, τα οποία αποτελούνται από αυτόνομους δυναμικούς κόμβους που διαμοιράζονται περιεχόμενο. Σε τέτοια συστήματα, βασική πρόκληση αποτελεί η αποδοτική αποτίμηση ερωτημάτων. Στόχος της διατριβής αυτής είναι να παρέχει νέες τεχνικές που βελτιώνουν την αποδοτικότητα της αποτίμησης ερωτημάτων όσον αφορά τόσο το επικοινωνιακό όσο και το επεξεργαστικό κόστος που απαιτείται. Για τον σκοπό αυτό, παρουσιάζουμε λύσεις βασισμένες σε δύο κεντρικούς άξονες: (i) τον ορισμό και τη χρήση κατάλληλων δομών ευρετηρίου και (ii) την αυτό-οργάνωση των κόμβων του λογικού δικτύου επικάλυψης (logical overlay network) σε συστάδες. Επικεντρωνόμαστε σε κατανεμημένα συστήματα στα οποία οι κόμβοι διατηρούν και διαμοιράζονται ημιδομημένα δεδομένα, όπως για παράδειγμα XML έγγραφα, που αναπαριστούν την πληροφορία ακολουθώντας μια δενδρική δομή. Εισάγουμε μια νέα δομή ευρετηρίου βασισμένη στον κατακερματισμό, το πολύ-επίπεδο φίλτρο Bloom, το οποίο αποτελεί μια επέκταση του γνωστού φίλτρου Bloom σχεδιασμένη έτσι ώστε να διατηρεί τις ιεραρχικές ιδιότητες των ημιδομημένων δεδομένων που συνοψίζει. Εισάγουμε μια δεύτερη δομή που συνδυάζει το πολύ-επίπεδο φίλτρο Bloom με ιστογράμματα, το πολύ-επίπεδο ιστόγραμμα Bloom, έτσι ώστε να παρέχει επιπλέον και εκτιμήσεις επιλεκτικότητας. Οι δύο δομές χαρακτηρίζονται από χαμηλό σφάλμα αποτίμησης ενώ έχουν πολύ χαμηλές απαιτήσεις αποθηκευτικού χώρου. Ακόμη, προτείνουμε ένα κατανεμημένο ευρετήριο συστάδων για ημιδομημένα δενδρικά δεδομένα του οποίου η κατασκευή βασίζεται στη χρήση του πολύ-επίπεδου ιστογράμματος Bloom ως κύριου δομικού στοιχείου. Επειδή τα δεδομένα σε τέτοια κατανεμημένα περιβάλλοντα είναι συνήθως ετερογενή, παρέχουμε τεχνικές για την υποστήριξη προσεγγιστικής επεξεργασίας ερωτημάτων. Συγκεκριμένα, προτείνουμε ένα σύνολο αλγορίθμων για τη δομική χαλάρωση (structural relaxation) XPath ερωτημάτων, οι οποίοι εφαρμόζονται πάνω στο κατανεμημένο ευρετήριο και άρα είναι πολύ πιο αποδοτικοί από αντίστοιχους αλγορίθμους που εφαρμόζονται πάνω στα πραγματικά δεδομένα. Παρουσιάζουμε τα πλεονεκτήματα της χρήσης του κατανεμημένου ευρετηρίου συστάδων εξετάζοντας δύο σημαντικά σενάρια επεξεργασίας ερωτημάτων: την ανάκτηση των κορυφαίων K (top-K) αποτελεσμάτων και την αυξητική (pay-as-you-go) αποτίμηση ερωτημάτων, συγκρίνοντας την απόδοση που επιτυγχάνουμε με το ευρετήριο συστάδων σε σχέση με ένα τυχαία διαμοιρασμένα κατανεμημένο ευρετήριο. Επιπρόσθετα, θεωρούμε μια παραλλαγή των πολύ-επίπεδων φίλτρων Bloom για την υποστήριξη ερωτημάτων με λέξεις-κλειδιά στα πλαίσια μιας τεχνικής για την επιλογή κατανεμημένων συλλογών XML εγγράφων, η οποία δε χρειάζεται να προσπελάσει τα δεδομένα αλλά λειτουργεί πάνω στα ευρετήρια που τα συνοψίζουν. Υιοθετούμε σημασιολογία ελάχιστου κοινού απογόνου (LCA-based) και χρησιμοποιούμε το ύψος του ελάχιστου κοινού απόγονου ως ένα μέτρο του πόσο σχετικά είναι τα αποτελέσματα σε σχέση με το ερώτημα. Προτείνουμε ένα προσεγγιστικό τρόπο εκτίμησης του ύψους και σε συνδυασμό με τη χρήση του πολύ-επίπεδου φίλτρου Bloom, παρέχουμε μια κατάταξη των συλλόγων πολύ κοντά σε αυτήν που θα παίρναμε αν επεξεργαζόμασταν αναλυτικά κάθε έγγραφο αλλά με πολύ μικρότερο κόστος. Αναφορικά με το δεύτερο άξονα, μελετάμε την αυτό-οργάνωση των κόμβων στο λογικό δίκτυο επικάλυψης σε συστάδες με βάση παρόμοιο περιεχόμενο και ενδιαφέροντα όπως αυτά εκφράζονται μέσα από τα ερωτήματα που θέτουν οι κόμβοι. Η βασική καινοτομία της προσέγγισης μας είναι ότι μοντελοποιεί τη διαμόρφωση των συστάδων ως ένα στρατηγικό παίγνιο στο οποίο οι κόμβοι (παίκτες) καθορίζουν στην στρατηγική τους επιλέγοντας σε ποιες συστάδες θα συμμετάσχουν. Στόχος κάθε παίκτη είναι να επιλέξει τη στρατηγική (συστάδες) που θα βελτιστοποιήσουν μια συνάρτηση ωφέλειας η οποία εξαρτάται από το ποσοστό ανάκλησης των ερωτημάτων (query recall) και το κόστος συμμετοχής σε μια συστάδα. Θεωρούμε παίκτες εγωιστές που προσπαθούν να βελτιώσουν το ποσοστό ανάκλησης των δικών τους ερωτημάτων, καθώς και παίκτες αλτρουιστές που στοχεύουν στη βελτίωση της ανάκλησης των ερωτημάτων, καθώς και παίκτες αλτρουιστές που στοχεύουν στη βελτίωση της ανάκλησης των ερωτημάτων των άλλων και ορίζουμε κατάλληλες συναρτήσεις ωφέλειας. Μελετάμε θεωρητικά τις ιδιότητες του παιγνίου και εξετάζουμε συγκεκριμένα σενάρια στα οποία το σύστημα καταλήγει σε κατάσταση ισορροπίας. Βασισμένοι στο μοντέλο μας, προτείνουμε ένα πλήρως κατανεμημένο πρωτόκολλο για το σχηματισμό και την συντήρηση των συστάδων που βασίζεται σε τοπικές αποφάσεις που παίρνονται από κάθε κόμβο ανεξάρτητα για να βελτιώσει τη συνάρτηση ωφέλειας του. Με μια εκτενή πειραματική μελέτη, δείχνουμε ότι μέσα από τις τοπικές αποφάσεις βελτιώνεται η συνολική απόδοση του συστήματος, και το πρωτόκολλο μας αποτυγχάνει βελτίωση στο συνολικό ποσοστό ανάκλησης ερωτημάτων του συστήματος εφάμιλλη με ένα αντίστοιχο συντονισμένο (coordinated) πρωτόκολλο ενώ μειώνει δραστικά το επικοινωνιακό κόστος που θα απαιτούνταν για το συντονισμό και διατηρεί την αυτονομία των κόμβων.