A fault tolerant data structure for Peer-to-Peer range query processing
| dc.contributor.advisor | Nickerson, Bradford | |
| dc.contributor.author | Mirikharaji, Zahra | |
| dc.date.accessioned | 2023-03-01T16:42:53Z | |
| dc.date.available | 2023-03-01T16:42:53Z | |
| dc.date.issued | 2015 | |
| dc.date.updated | 2016-04-06T00:00:00Z | |
| dc.description.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. | |
| dc.description.copyright | © Zahra Mirikharaji, 2015 | |
| dc.format | text/xml | |
| dc.format.extent | xii, 96 pages | |
| dc.format.medium | electronic | |
| dc.identifier.uri | https://unbscholar.lib.unb.ca/handle/1882/14372 | |
| dc.language.iso | en_CA | |
| dc.publisher | University of New Brunswick | |
| dc.rights | http://purl.org/coar/access_right/c_abf2 | |
| dc.subject.discipline | Computer Science | |
| dc.title | A fault tolerant data structure for Peer-to-Peer range query processing | |
| dc.type | master thesis | |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.fullname | Master of Computer Science | |
| thesis.degree.grantor | University of New Brunswick | |
| thesis.degree.level | masters | |
| thesis.degree.name | M.C.S. |
Files
Original bundle
1 - 1 of 1