Back to search

University of Ioannina

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

Abstract

dc:description

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.

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

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/17995

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Koloniari, Georgia; Κολωνιάρη, Γεωργία. Τεχνικές ευρετηριοποίησης και συσταδοποίησης για την αποδοτική αποτίμηση ερωτημάτων σε συστήματα ομότιμων κόμβων. University of Ioannina, 2009. http://hdl.handle.net/10442/hedi/17995