4th International ICST Conference on Communication System Software and Middleware

Research Article

Scalable Spatial Information Discovery over Distributed Hash Tables

  • @INPROCEEDINGS{10.1145/1621890.1621892,
        author={Faraz Memon and Daniel Tiebler and Marco Tomsu and Peter Domschitz and Frank D\'{y}rr and Kurt  Rothermel},
        title={Scalable Spatial Information Discovery over Distributed Hash Tables},
        proceedings={4th International ICST Conference on Communication System Software and Middleware},
        publisher={ACM},
        proceedings_a={COMSWARE},
        year={2010},
        month={5},
        keywords={Peer-to-Peer overlay networks spatial information discovery location- based queries space-filling curves distributed hash tables},
        doi={10.1145/1621890.1621892}
    }
    
  • Faraz Memon
    Daniel Tiebler
    Marco Tomsu
    Peter Domschitz
    Frank Dürr
    Kurt Rothermel
    Year: 2010
    Scalable Spatial Information Discovery over Distributed Hash Tables
    COMSWARE
    ACM
    DOI: 10.1145/1621890.1621892
Faraz Memon1,*, Daniel Tiebler1,*, Marco Tomsu2,*, Peter Domschitz2,*, Frank Dürr1,*, Kurt Rothermel1,*
  • 1: Frank Dürr, Kurt Rothermel IPVS – Distributed Systems Department Universität Stuttgart Universitätsstraße 38, 70569 Stuttgart, Germany
  • 2: Bell Laboratories Alcatel–Lucent Lorenzstraße 10, 70435 Stuttgart, Germany
*Contact email: Daniel.Tiebler@ipvs.uni-stuttgart.de, Faraz.Memon@ipvs.uni-stuttgart.de, Marco.Tomsu@alcatel-lucent.de, Peter.Domschitz@alcatel-lucent.de, frank.dürr@alcatel-lucent.de, kurt.rothermel@alcatel-lucent.de

Abstract

In this paper, we present a Peer-to-Peer (P2P) spatial information discovery system that enables spatial range queries over Distributed Hash Tables (DHTs). Our system utilizes a less-distorting octahedral map projection in contrast to the quadrilateral projections used by majority of the previously proposed systems, to represent the spatial information. We also introduce a Space-Filling Curve (SFC)-based data placement strategy that reduces the probability of data hot-spots in the network. Moreover, we show that our system achieves scalable resolution of location-based range queries, by utilizing a tree-based query optimization algorithm. Compared to the basic query resolution algorithm, the query optimization algorithm reduces the average number of parallel messages used to resolve a query, by a factor of 96%.