Scalable spatial information discovery over Distributed Hash Tables

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

References

1. A. Andrzejak and Z. Xu. Scalable, Efficient Range Queries for Grid Information Services. In Proceedings of the 2nd International Conference on P2P Computing, page 33. IEEE Computer Society, 2002.
2. F. Araújo and L. Rodrigues. GeoPeer: A Location-Aware Peer-to-Peer System. In Proceedings of the 3rd International Symposium on Network Computing and Applications, pages 39--46. IEEE Computer Society, 2004.
3. J. J. Bartholdi and P. Goldsman. Continuous Indexing of Hierarchical Subdivisions of the Globe. International Journal of Geographical Information Science, 15(6):489--522, 2001.
4. M. Cai, M. Frank, J. Chen, and P. Szekely. MAAN: A Multi-Attribute Addressable Network for Grid Information Services. In Proceedings of the 4th International Workshop on Grid Computing, page 184. IEEE Computer Society, 2003.
5. Y. Chawathe, S. Ramabhadran, S. Ratnasamy, A. LaMarca, S. Shenker, and J. Hellerstein. A Case Study in Building Layered DHT Applications. In Proceedings of the 2005 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pages 97--108. ACM, 2005.
6. N. V. Earth. Earth's City Lights. http://visibleearth.nasa.gov/, 2008.
7. C. A. Furuti. Polyhedral Map Projections. http://www.progonos.com/furuti/MapProj/Normal/ProjPoly/projPoly.html, 1996--97.
8. P. Ganesan, B. Yang, and H. Garcia-Molina. One Torus to Rule Them All: Multi-dimensional Queries in P2P Systems. In Proceedings of the 7th International Workshop on the Web and Databases, pages 19--24. ACM, 2004.
9. A. Harwood and E. Tanin. Hashing Spatial Content over Peer-to-Peer Networks. In Proceedings of the 2003 Australian Telecommunications, Networks and Applications Conference, 2003.
10. D. Hilbert. Über die stetige Abbildung einer Linie auf ein Flächenstück. In Mathematische Annalen, 1891.
11. H.-Y. Kang, B.-J. Lim, and K.-J. Li. P2P Spatial Query Processing by Delaunay Triangulation. In Proceedings of the 4th International Workshop on Web and Wireless Geographical Information Systems, pages 136--150. Springer, 2004.
12. M. Knoll and T. Weis. Optimizing Locality for Self-organizing Context-Based Systems. In Proceedings of the 1st International Workshop on Self-Organizing Systems. Springer, 2006.
13. A. Kovacevic, N. Liebau, and R. Steinmetz. Globase. KOM - A P2P Overlay for Fully Retrievable Location-based Search. In Proceedings of the 7th International Conference on Peer-to-Peer Computing, pages 87--96. IEEE Computer Society, 2007.
14. R. Laurini and D. Thompson. Fundamentals of Spatial Information Systems. Academic Press Ltd., 1992.
15. K. Loesing and S. Kaffille. Open Chord. http://sourceforge.net/projects/open-chord/, 2006.
16. F. Memon, D. Tiebler, F. Dürr, K. Rothermel, M. Tomsu, and P. Domschitz. OID: Optimized Information Discovery using Space Filling Curves in P2P Overlay Networks. In Proceedings of 14th IEEE International Conference on Parallel and Distributed Systems, pages 311--319. IEEE Computer Society, 2008.
17. J. A. Orenstein and T. H. Merrett. A Class of Data Structures for Associative Searching. In Proceedings of the 3rd SIGACT-SIGMOD Symposium on Principles of Database Systems, pages 181--190. ACM, 1984.
18. G. Peano. Sur une courbe, qui remplit toute une aire plane (On a Curve Which Completely Fills a Planar Region). In Mathematishe Annalen, 1890.
19. S. Ramabhadran, J. Hellerstein, S. Ratnasamy, and S. Shenker. Prefix Hash Tree - An Indexing Data Structure over Distributed Hash Tables. In 23rd Annual SIGACT-SIGOPS Symposium on Principles of Distributed Computing. ACM, 2004.
20. S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Schenker. A Scalable Content-Addressable Network. In Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pages 161--172. ACM, 2001.
21. A. Rowstron and P. Druschel. Pastry: Scalable, Decentralized Object Location and Routing for Large-scale Peer-to-Peer Systems. In Proceedings of IFIP/ACM International Conference on Distributed Systems Platforms, pages 329--350. ACM, 2001.
22. C. Schmidt and M. Parashar. Flexible Information Discovery in Decentralized Distributed Systems. In Proceedings of the 12th International Symposium on High Performance Distributed Computing, page 226. IEEE Computer Society, 2003.
23. Y. Shu, B. C. Ooi, K.-L. Tan, and A. Zhou. Supporting Multi-dimensional Range Queries in Peer-to-Peer Systems. In Proceedings of the 5th International Conference on P2P Computing, pages 173--180. IEEE Computer Society, 2005.
24. I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. In Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pages 149--160. ACM, 2001.
25. E. Tanin, A. Harwood, H. Samet, S. Nutanong, and M. T. Truong. A Serverless 3D World. In Proceedings of the 12th International Workshop on Geographic Information Systems, pages 157--165. ACM, 2004.
26. H. Wang, R. Zimmermann, and W.-S. Ku. ASPEN: An Adaptive Spatial Peer-to-Peer Network. In Proceedings of the 13th International Workshop on Geographic Information Systems, pages 230--239. ACM, 2005.

Index Terms

• Information systems

  • Information retrieval

    • Information retrieval query processing

• Networks

  • Network architectures