Binary Search Tree: An Efficient Overlay Structure to Support Range Query

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 fr...

Full description

Saved in:
Bibliographic Details
Main Authors: Shrivastava, B.K., Khataniar, G., Goswami, D.
Format: Conference Proceeding
Language:English
Subjects:
Binary
Binary search trees
Churn Rate
Computer science
Distributed computing
Distributed Hash Table (DHT)
Information retrieval
P2P System
Peer to peer computing
Query processing
Routing
Search Tree (BST)
Telephony
Tree data structures
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 |G j |) messages, where |G j | 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.
ISSN:1545-0678
2332-5666
DOI:10.1109/ICDCSW.2007.99