Τεχνικές ευρετηριοποίησης και συσταδοποίησης για την αποδοτική αποτίμηση ερωτημάτων σε συστήματα ομότιμων κόμβων

Abstract

Nowadays, the popularity of applications such as file-sharing peer-to-peer systems and social networks has drawn significant attention to large-scale distributed systems consisting of dynamic, autonomous nodes (peers) that share their content. An issue of great importance and a considerable challenge in such systems is efficient query evaluation. To this end, the goal of this thesis is to provide novel techniques for improving the efficiency of query evaluation in peer-to-peer systems and large-scale distributed systems, in general. The solutions we propose are centered around two basic axes: (i) the design and deployment of appropriate index structures, and (ii) the self-organization of the nodes in the logical overlay network into clusters. Since XML has evolved as the de facto standard for data representation and exchange in the Internet, we focus on distributed systems in which the peers maintain semi-structured data, i.e., XML documents that represent data in a hierarchical form. We introduce a novel path-index structure, the multi-level Bloom filter, which is based on the well-known Bloom filters that are compact hash-based structures designed to represent a set of elements. Multi-level Bloom filters support path expressions look ups by extending the basic Bloom filters so as to preserve the hierarchical relationships of the data they summarize. We define a second index structure, the multi-level Bloom histogram that combines the multi-level Bloom filter with histograms so as to support selectivity estimations for path expressions. Both structures require low space overhead and result in low evaluation and estimation errors. In addition, we propose a distributed clustered index for semi-structured data which is constructed by using the multi-level Bloom histogram as its basic building block. Since the data is usually heterogeneous in large-scale distributed systems like the ones we consider, we propose an approach for supporting approximate query processing over the XML data. In particular, we propose a set of structural relaxation algorithms that do not process the actual data but operate on top of the distributed clustered index, thus, significantly reducing the required processing cost. To illustrate the benefits of using the distributed clustered index, we describe two popular query evaluation scenarios, a top-K query evaluation and an incremental pay-as-you-go approach, and compare their performance when using the distributed clustered index, and when using a randomly partitioned distributed index. We also propose a more efficient organization for the clustered index, which is based on an incremental hierarchical clustering algorithm and the resulting distributed index consists of a set of hierarchies. Through our experimental evaluation, we show that in both query evaluation scenarios the use of the clustered index radically reduces both the communication and processing costs involved as compared to a random index, and the hierarchical organization manages to reduce these costs even further. We also consider a variation of the multi-level Bloom filters for supporting keyword-queries and use it to address the problem of efficient selection of distributed XML document collections. Based on the multi-level bloom filter, we present an approach that does not require accessing the actual collections of data but instead, it is applied on top of the indexes that summarize it. We adopt lowest common ancestor semantics (LCA-based) for query evaluation, and determine the relevance of a result to the query based on the height of the lowest common ancestor of the keywords that form the result. We introduce an approximate algorithm for estimating the height of the lowest common ancestor and combined with the use of the multi-level Bloom filters for summarizing the required information, we provide a ranking for the XML document collections that is very close to the actual ranking we would get if we had processed each document in the collections separately, but with a significantly reduced processing cost. Regarding the second axis of solutions we consider, we study the self-organization of nodes in the logical overlay network in clusters based on the similarity of their content and interests as they are expressed through their query workload. The main novelty of our approach is that we model the problem of cluster evolution as a strategic game in which the peers are the players that determine their strategy by selecting which clusters to join. The goal of the game is for each peer to select the strategy that minimizes its utility function that is defined based on query recall and the cost involved in belonging to clusters. Based on real-life behavior of users in peer-to-peer systems, we model both selfish and altruistic behavior and define appropriate utility functions for both. Selfish peers aim at maximizingthe recall of their own queries, while altruistic peers aim at maximizing the recall of the queries of the other peers in their clusters. We study theoretically the properties of the cluster evolution game and consider specific scenarios in which our game reaches a stable state. Furthermore, we introduce a fully-distributed protocol for cluster maintenance that is based on local decisions made by each peer independently so as to improve its utility function. An extensive experimental evaluation shows that our protocol manages through local decisions to improve the overall query recall in the system as a corresponding coordinated protocol would but without requiring any additional communication cost for coordination and while preserving the autonomy of the peers.

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