A fault tolerant data structure for Peer-to-Peer range query processing

dc.contributor.advisorNickerson, Bradford
dc.contributor.authorMirikharaji, Zahra
dc.date.accessioned2023-03-01T16:42:53Z
dc.date.available2023-03-01T16:42:53Z
dc.date.issued2015
dc.date.updated2016-04-06T00:00:00Z
dc.description.abstractWe 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.formattext/xml
dc.format.extentxii, 96 pages
dc.format.mediumelectronic
dc.identifier.urihttps://unbscholar.lib.unb.ca/handle/1882/14372
dc.language.isoen_CA
dc.publisherUniversity of New Brunswick
dc.rightshttp://purl.org/coar/access_right/c_abf2
dc.subject.disciplineComputer Science
dc.titleA fault tolerant data structure for Peer-to-Peer range query processing
dc.typemaster thesis
thesis.degree.disciplineComputer Science
thesis.degree.fullnameMaster of Computer Science
thesis.degree.grantorUniversity of New Brunswick
thesis.degree.levelmasters
thesis.degree.nameM.C.S.

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
item.pdf
Size:
3.21 MB
Format:
Adobe Portable Document Format