In this work, we propose D3-Tree, a dynamic distributed deterministic structure for data management in decentralized networks. We present in brief the theoretical algorithmic analysis, in which our proposed structure is based on, and we describe thoroughly the key aspects of the implementation. Conducting experiments, we verify that the implemented structure outperforms other well-known hierarchical tree-based structures, since it provides better complexities regarding load-balancing operations. More specifically, the structure achieves a logarithmic amortized bound, using an efficient deterministic load-balancing mechanism, which is general enough to be applied to other hierarchical tree-based structures. Moreover, we investigate the structure's fault tolerance, which hasn't been sufficiently tackled in previous work, both theoretically and through rigorous experimentation. We prove that D3-Tree is highly fault tolerant, since, even for massive node failures, it achieves a significant success rate in element queries. Afterwards we go one step further, in order to achieve sub-logarithmic complexity and propose the ART+ structure (Autonomous Range Tree), exploiting the excellent performance of D3-Tree. ART+ is a fully dynamic and fault-tolerant structure, which achieves sub-logarithmic performance for query and update operations and performs load-balancing in sub-logarithmic amortized cost.
@cite_0: Peer-to-peer systems are mainly used for object sharing although they can provide the infrastructure for many other applications. We extend the idea of object sharing to data sharing on a peer-to-peer system. We propose a method, which is based on the multidimensional CAN system, for efficiently evaluating range queries. The answers of the range queries are cached at the peers and are used to answer future range queries. The scalability and efficiency of our design is shown through simulation.
@cite_1: This third edition of a classic textbook can be used to teach at the senior undergraduate and graduate levels. The material concentrates on fundamental theories as well as techniques and algorithms. The advent of the Internet and the World Wide Web, and, more recently, the emergence of cloud computing and streaming data applications, has forced a renewal of interest in distributed and parallel data management, while, at the same time, requiring a rethinking of some of the traditional techniques. This book covers the breadth and depth of this re-emerging field. The coverage consists of two parts. The first part discusses the fundamental principles of distributed data management and includes distribution design, data integration, distributed query processing and optimization, distributed transaction management, and replication. The second part focuses on more advanced topics and includes discussion of parallel database systems, distributed object management, peer-to-peer data management, web data management, data stream systems, and cloud computing. New in this Edition: New chapters, covering database replication, database integration, multidatabase query processing, peer-to-peer data management, and web data management. Coverage of emerging topics such as data streams and cloud computing Extensive revisions and updates based on years of class testing and feedback Ancillary teaching materials are available.
@cite_6: We present an architecture for a data sharing peer-to-peer system where the data is shared in the form of database relations. In general, peer-to-peer systems try to locate exactmatch data objects to simple user queries. Since peer-to-peer users generally tend to submit broad queries in order to find data of their interest, we develop a P2P data sharing architecture for computing approximate answers for the complex queries by finding data ranges that are similar to the user query. Thus this paper represents the first step towards solving the general range lookup problem over P2P systems instead of exact lookup operations.
@cite_2: In peer-to-peer (P2P) systems, computers from around the globe share data and can participate in distributed computation. P2P became famous, and infamous, due to file-sharing systems like Napster. However, the scalability and robustness of these systems make them appealing to a wide range of applications. This article introduces P-Ring, a new peer-to-peer index structure. P-Ring is fully distributed, fault tolerant, and provides load balancing and logarithmic search performance while supporting both equality and range queries. Our theoretical analysis as well as experimental results, obtained both in a simulated environment and on PlanetLab, show the performance of our system.
Existing structured P2P systems can be classified into two broad categories: Distributed Hash Table (DHT)-based systems and tree-based systems. Examples of the former, which constitute the majority, include Chord, CAN, Pastry, Symphony, Tapestry @cite_1 and P-Ring @cite_2 . In general, DHT-based systems support exact match queries well and use (successfully) probabilistic methods to distribute the workload among nodes equally. Since hashing destroys the ordering on keys, DHT-based systems typically do not possess the functionality to support straightforwardly range queries, or more complex queries based on data ordering (e.g., nearest-neighbour and string prefix queries). Some efforts towards addressing range queries have been made in @cite_6 @cite_0 , getting however approximate answers and also making exact searching highly inefficient. The most recent effort towards range queries is the P-Ring @cite_2 . P-Ring is fully distributed and fault-tolerant, provides load-balancing and supports both exact match and range queries, achieving @math range search performance in average case ( @math is the number of peers, @math is the of the ring and @math is the answer size) and @math in worst case.