3rd International ICST Conference on Scalable Information Systems

Research Article

GRaSP: Generalized Range Search in Peer-to-peer Networks

Download699 downloads
  • @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
Michail Argyriou1,*, Vasilis Samoladas1,*, Spyros Blanas2,*
  • 1: Technical University of Crete
  • 2: Univ. of Wisconsin at Madison
*Contact email: micharg@intelligence.tuc.gr, vsam@softnet.tuc.gr, sblanas@cs.wisc.edu

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.