Research Article
GRaSP: Generalized Range Search in Peer-to-peer Networks
@INPROCEEDINGS{10.4108/ICST.INFOSCALE2008.3533, author={Michail Argyriou and Vasilis Samoladas and Spyros Blanas}, title={GRaSP: Generalized Range Search in Peer-to-peer Networks}, proceedings={3rd International ICST Conference on Scalable Information Systems}, publisher={ICST}, proceedings_a={INFOSCALE}, year={2010}, month={5}, keywords={P2P networks range search performance analysis}, doi={10.4108/ICST.INFOSCALE2008.3533} }- Michail Argyriou
Vasilis Samoladas
Spyros Blanas
Year: 2010
GRaSP: Generalized Range Search in Peer-to-peer Networks
INFOSCALE
ICST
DOI: 10.4108/ICST.INFOSCALE2008.3533
Abstract
We present a framework for generalized range search on trie-structured P2P networks, such as P-Grid. Our techniques exploit hitherto unknown properties of randomized tries. We prove that a P-Grid like network has routing diameter O(log n) with high probability, as well as O(log n) congestion, regardless of the shape of the underlying trie. Based on these properties, we propose GRaSP, a simple scheme for handling arbitrary range search problems, with search and update hop latency O(log n) with high probability. We then apply GRaSP on two range search problems: multidimensional range search over points and rectangles, and three-sided search. Our empirical results show that GRaSP delivers excellent search performance and exhibits very good scalability under heavy load. With respect to three-sided search, our proposed scheme is distinguished in that it attempts to improve load balancing by introducing redundancy via the choice of search space.
