University of Patras
Επεξεργασία πολύπλοκων ερωτημάτων και εκτίμηση ανομοιόμορφων κατανομών σε κατανεμημένα δίκτυα κλίμακας ίντερνετ
Abstract
dc:descriptionThe distributed, Internet-scale networks, and mainly, the peer-to-peer networks (p2p), that constitute their most representative example, recently attract a great interest from the researchers and the industry, due to their outstanding properties, such as full decentralization, autonomy of nodes, scalability, etc. Initially designed to support file sharing applications with simple lookup operations, they soon developed in a new model of distributed systems, with many and increasing possibilities for Internet applications, supporting complex applications of structured and semantically rich data. Our research to the area has two basic points of view: (a) complex query processing and (b) estimation of skewness in various distributions existing in these networks (e.g. load distribution, distribution of offer, or consumption of resources, data value distributions, etc), which, among others, it is an important tool to complex query processing support. Specifically, we deal with and solve three basic open problems. The first open problem is range query processing in p2p systems based on distributed hash tables (DHT), with simultaneous guarantees of access load balancing and fault tolerance. We propose an overlay DHT architecture, coined Saturn. Saturn uses a novel order-preserving hash function that places consecutive data values in successive nodes to provide efficient range query processing, and replication to guarantee access load balancing (vertical, load-driven replication) and fault tolerance (horizontal replication). With extensive experimentation, we evaluate and compare Saturn with two basic DHT networks (Chord and OP - Chord), and certify its superiority to cope with the three above requirements, but also its ability to tune the degree of replication to trade off replication costs for access load balancing. The second open problem that we face concerns the lack of appropriate metrics to express the degree of skewness of various distributions (for example, the fairness degree of load balancing) in p2p networks, and the inefficient and offline-only exploitation of metrics of skewness, which does not enable any cooperation with corrective algorithms (for example, load balancing algorithms). The problem is important because estimation of distribution fairness contributes to system scalability and efficiency. First, after a comprehensive study and evaluation of popular metrics of skewness, we propose three of them (the coefficient of Gini, the fairness index, and the coefficient of variation), and, then, we develop sampling techniques (three already known techniques, and three novel ones) to dynamically estimate these metrics. With extensive experimentation, which comparatively evaluates both the various proposed estimation algorithms and the three metrics we propose, we show how these three metrics, and especially, the coefficient of Gini, can be easily utilized online by higher-level algorithms, which can now know when to best intervene to correct unfairness. The third and last open problem concerns self-join size estimation of a relation whose tuples are distributed over data nodes which comprise an overlay network. Self-join size has been extensively used in centralized databases for query optimization purposes, and we support that it can also be used in various other applications, specifically in p2p networks (e.g. web clustering, web searching, etc). Our contribution first includes the adaptations of five well-known self-join size estimation, centralized techniques (specifically, sequential sampling, cross-sampling, adaptive and bifocal sampling, and sample-count) to the p2p environment and a novel estimation technique which is based on the Gini coefficient. With mathematical analysis we show that, the estimates of the Gini coefficient can lead to estimates of the degree of skewness of the underlying data distribution, when these follow the power, or Zipf’s law, and these estimates can lead to self-join size estimates of those data relations. With extensive experimental study and comparison of all above techniques, we prove that the proposed technique is very efficient in terms of accuracy, precision, and cost of estimation against the other five methods.
Degree
thesis:*- Grantor dc:publisher
- University of Patras
- Year dc:date
- 2008
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Pitoura, Theoni
- Πιτουρά, Θεώνη
Subjects
dc:subject × 31- Ίντερνετ
- Δίκτυα ομοτίμων εταίρων
- Κατανεμημένα δίκτυα
- Επεξεργασία ερωτημάτων
- Ερωτήματα εύρους τιμών
- Εκτίμηση κατανομών
- Ανομοιόμορφες κατανομές
- Κατανομές Zipf
- Μέγεθος αυτοσύνδεσης
- Δειγματοληψία
- Εξισορρόπηση φορτίου νημάτων
- Συντελεστής Gini
- Internet
- Peer-to-peer networks
- P2P
- Distributed networks
- Query processing
- Range queries
- Estimation
- Skew distributions
- Zipf's law
- Self-join size
- Thread load balancing
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Natural Sciences
- Computer and Information Sciences
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/27775