University of Ioannina
Τεχνικές ευρετηριοποίησης και συσταδοποίησης για την αποδοτική αποτίμηση ερωτημάτων σε συστήματα ομότιμων κόμβων
Abstract
dc:descriptionNowadays, 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.
Degree
thesis:*- Grantor dc:publisher
- University of Ioannina
- Year dc:date
- 2009
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Koloniari, Georgia
- Κολωνιάρη, Γεωργία
Subjects
dc:subject × 20- Σύστημα ομότιμων κόμβων
- Συσταδοποιημένο δίκτυο επικάλυψης
- XML δεδομένα
- Ευρετηριοποίηση
- Προσεγγιστική επεξεργασία ερωτημάτων
- Επιλογή βάσης δεδομένων
- Θεωρία παιγνίων
- Αναδιαμόρφωση συστάδων
- Peer-to-peer systems
- Networks, Clustered overlay
- XML data
- Indexing
- Approximate query processing
- Database selection
- Game theory
- Cluster reformulation
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Computer and Information Sciences
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/17995