Efficient query routing in distributed spatial databases

ABSTRACT

Spatial databases are prominently used in Geographic Information System (GIS) applications. However, many of the current architectures rely on a centralized data repository. The next evolution will be GIS applications that utilize and integrate a multitude of remotely accessible data sets, for example via Web services. Our involvement in a project where geotechnical borehole information is retrieved from a large number of repositories that are under different administrative control has motivated us to design an efficient distributed access structure and routing middleware for spatial queries. In this study we present our middleware design based on distributed R-tree and Quadtree index structures. Importantly, the framework supports both spatial range and <i>k</i> nearest neighbor queries. We have performed a theoretical analysis and simulations with synthetic and real data sets. The results show a large reduction in message traffic to a level only slightly above what is minimally necessary.

REFERENCES

• 1: Jean-Pierre Bardet, Roger Zimmermann, Wei-Shinn Ku, and Jianping Hu. Web Services for Exchange and Utilization of Geotechnical Information. Computers & Geosciences, 2004. Currently under review.
• 2: R.A. Finkel and J.L. Bentley. Quadtree: A data structure for retrieval on composite keys. ACTA Informatica, 4(1):1--9, 1974.
• 3: Leonidas Galanis, Yuan Wang, Shawn R. Jeffery, and David J. DeWitt. Locating Data Sources in Large Distributed Systems. In Proceedings of the 29th International Conference on Very Large Databases, Berlin, Germany, September 9-12, 2003.
• 4: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 5: Aaron Harwood and Egemen Tanin. Hashing Spatial Content over Peer-to-Peer Networks. In Australian Telecommunications, Networks and Applications Conference (ATNAC), Melbourne, Australia, December 8-10, 2003.
• 6: Gershon Kedem, The quad-CIF tree: A data structure for hierarchical on-line algorithms, Proceedings of the 19th conference on Design automation, p.352-357, January 1982
• 7: J.B. McQueen. Some methods of classification and analysis of multivariate observations. In 5th Berkeley Symposium in Mathematics, Statistics and Probability, pages 281--297, 1967.
• 8: Apostolos Papadopoulos , Yannis Manolopoulos, Performance of Nearest Neighbor Queries in R-Trees, Proceedings of the 6th International Conference on Database Theory, p.394-408, January 08-10, 1997
• 9: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 10: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 11: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 12: Hanan Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys (CSUR), v.16 n.2, p.187-260, June 1984 [doi>10.1145/356924.356930]
• 13: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 14: Cyrus Shahabi , Mohammad R. Kolahdouzan , Mehdi Sharifzadeh, A road network embedding technique for k-nearest neighbor search in moving object databases, Proceedings of the 10th ACM international symposium on Advances in geographic information systems, November 08-09, 2002, McLean, Virginia, USA [doi>10.1145/585147.585167]
• 15: R.L. Sproull. Refinements to nearest-neighbor searching in k-dimensional trees. In Algorithmica, 6, 1991.
• 16: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 17: Roger Zimmermann, Jean-Pierre Bardet, Wei-Shinn Ku, Jianping Hu, and Jennifer Swift. Design of a Geotechnical Information Architecture Using Web Services. In Proceedings of the Seventh World Multi-Conference on Systemics, Cybernetics and Informatics (SCI 2003), Orlando, Florida, July 27--30, 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms

Keywords:
database middleware, distributed spatial databases, query routing