Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/41492
Title: BATON: A balanced tree structure for peer-to-peer networks
Authors: Jagadish, H.V.
Ooi, B.C. 
Vu, Q.H.
Issue Date: 2005
Source: Jagadish, H.V.,Ooi, B.C.,Vu, Q.H. (2005). BATON: A balanced tree structure for peer-to-peer networks. VLDB 2005 - Proceedings of 31st International Conference on Very Large Data Bases 2 : 661-672. ScholarBank@NUS Repository.
Abstract: We propose a balanced tree structure overlay on a peer-to-peer network capable of supporting both exact queries and range queries efficiently. In spite of the tree structure causing distinctions to be made between nodes at different levels in the tree, we show that the load at each node is approximately equal. In spite of the tree structure providing precisely one path between any pair of nodes, we show that sideways routing tables maintained at each node provide sufficient fault tolerance to permit efficient repair. Specifically, in a network with N nodes, we guarantee that both exact queries and range queries can be answered in O(logN) steps and also that update operations (to both data and network) have an amortized cost of O(logN). An experimental assessment validates the practicality of our proposal.
Source Title: VLDB 2005 - Proceedings of 31st International Conference on Very Large Data Bases
URI: http://scholarbank.nus.edu.sg/handle/10635/41492
ISBN: 1595931546
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

53
checked on Jan 20, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.