A fault tolerant data structure for Peer-to-Peer range query processing
Loading...
Files
Date
2015
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of New Brunswick
Abstract
We present a fault tolerant dynamic data structure based on a constant-degree Distributed Hash Table called FissionE that supports orthogonal range search in d-dimensional space. A publication algorithm, which distributes data objects among all nodes in the network is described, along with a search algorithm that processes range queries and reports all objects in range to the query issuer. The worst case orthogonal range search cost in our data structure with n nodes is O(log n + m) messages plus reporting cost, where m is the minimum number of nodes intersecting the query. We have proved that in our data structure the cost of reporting data in range to the query issuer is ∑mi=1 ⌈Ki/B⌉ O(log n) ∈ O((K/B + m) log n) messages, where K is the number points in range, Ki is the number of points in range stored in node i, and B is the number of points fitting in one message. Storing d copies of each data objects on d different nodes provides redundancy for our scheme. This redundancy permits completely answering a query in the case of simultaneous failure of d — 1 nodes. Results of our experimental simulation with up to 12,288 nodes show the practical application of our data structure.