loading...
Binary Search Tree: An Efficient Overlay Structure to Support Range Query
Toronto, Canada June 22-June 29
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICDCSW.2007.9927th International Conference on Dist ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Brajesh Kumar Shrivastava, Indian Institute of Technology Guwahati, India
Guruprasad Khataniar, Indian Institute of Technology Guwahati, India
Diganta Goswami, Indian Institute of Technology Guwahati, India
Finding an efficient and scalable solution for range query to discover the contents in the presence of transient node populations and heterogeneity among them is a well-known challenging problem in peer-to-peer (P2P) systems. Transient node population results in high churn rate and hence requires frequent updates in routing table, while heterogeneity causes unfair distribution of resources as well as responsibilities among nodes. We propose an overlay structure based on m- Binary Search Tree (BST) that provides an efficient and scalable solution for point and range query. We arrange the whole key space in lexicographic order and divide it into different key intervals. Each key interval is assigned to a BST. We have achieved intra-group and inter-group query processing in O(log |Gj |) messages, where |Gj | is the number of nodes in the destination group. Our approach results in less overhead to update the routing table even in the case of high churn rate.
Index Terms:
P2P System, Churn Rate, Binary Search Tree (BST), Distributed Hash Table (DHT).
Citation:
Brajesh Kumar Shrivastava, Guruprasad Khataniar, Diganta Goswami, "Binary Search Tree: An Efficient Overlay Structure to Support Range Query," icdcsw, pp.77, 27th International Conference on Distributed Computing Systems Workshops (ICDCSW'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.