Article

Efficient query routing in distributed spatial databases

Authors:

Roger Zimmermann,

Wei-Cheng ChuAuthors Info & Claims

GIS '04: Proceedings of the 12th annual ACM international workshop on Geographic information systems

Pages 176 - 183

https://doi.org/10.1145/1032222.1032249

Published: 12 November 2004 Publication History

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.

Digital Library

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

Digital Library

[4]

Antomn Guttman. R-Trees: A Dynamic Index Structure for Spatial Searching. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 47--57, Boston, Massachusetts, June 18-21, 1984.

Digital Library

[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]

G. Kedem. The quad-CIF tree: A data structure for hierarchical on-line algorithms. In Proceedings of the 19th Design Automation Conference, pages 352--357, June 1982.

Digital Library

[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]

A. Papadopoulos and Y. Manolopoulos. Performance of nearest neighbor queries in r-trees. In 6th International Conference on Database Theory, pages 394--408, 1997.

Digital Library

[9]

Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker. A Scalable Content Addressable Network. In Proceedings of ACM SIGCOMM, San Diego, CA, August 27-31, 2001.

Digital Library

[10]

Nick Roussopoulos, Stephen Kelley, and Frédéric Vincent. Nearest neighbor queries. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 71--79, 1995.

Digital Library

[11]

Antony Rowstron and Peter Druschel. Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems. Lecture Notes in Computer Science, 2218:329--350, 2001.

Digital Library

[12]

Hanan Samet. The quadtree and related hierarchical data structures. ACM Computing Surveys, 16(2):187--260, 1984.

Digital Library

[13]

Hanan Samet, editor. The Design and Analysis of Spatial Data Structures, pages 200--211. Addison-Wesley, 1990.

Digital Library

[14]

Cyrus Shahabi, Mohammad R. Kolahdouzan, and Mehdi Sharifzadeh. A Road Network Embedding Technique for k-Nearest Neighbor Search in Moving Object Databases. In Proceedings of the Tenth ACM International Symposium on Advances in Geographic Information Systems, McLean, Virginia, November 2002.

Digital Library

[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, and Hari 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 Press, 2001.

Digital Library

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

Cited By

Troumpoukis AKonstantopoulos SProkopaki-Kostopoulou N(2022)A geospatial source selector for federated GeoSPARQL queryingOpen Research Europe10.12688/openreseurope.14605.22(48)Online publication date: 6-Oct-2022
https://doi.org/10.12688/openreseurope.14605.2
Troumpoukis AKonstantopoulos SProkopaki-Kostopoulou N(2022)A geospatial source selector for federated GeoSPARQL queryingOpen Research Europe10.12688/openreseurope.14605.12(48)Online publication date: 19-Apr-2022
https://doi.org/10.12688/openreseurope.14605.1
Lo CHuang WHo MSun MChen LSakai KKu W(2022) Recurrent Learning on PM 2.5 Prediction Based on Clustered Airbox Dataset IEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.304763434:10(4994-5008)Online publication date: 1-Oct-2022
https://doi.org/10.1109/TKDE.2020.3047634
Show More Cited By

Index Terms

Efficient query routing in distributed spatial databases
1. Human-centered computing
  1. Visualization
    1. Visualization application domains
      1. Geographic visualization
2. Information systems
  1. Data management systems
    1. Database management system engines
      1. Parallel and distributed DBMSs
  2. Information systems applications
    1. Spatial-temporal systems

Recommendations

Query rewriting for semantic query optimization in spatial databases

Query processing is an important challenge for spatial databases due to the use of complex data types that represent spatial attributes. In particular, due to the cost of spatial joins, several optimization algorithms based on indexing structures exist. ...
Efficient query processing on large spatial databases

A spatial index, called xBR+-tree, is compared against the R*-tree and the R+-tree.Performance of tree building and processing of common spatial queries is studied.Existing and new algorithms for processing these queries are utilized.Extensive ...
Query processing and optimization in spatial databases

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GIS '04: Proceedings of the 12th annual ACM international workshop on Geographic information systems

November 2004

282 pages

ISBN:1581139799

DOI:10.1145/1032222

Program Chairs:
Isabel F. Cruz
University of Illinois at Chicago
,
Dieter Pfoser
Research Academic Computer Technology Institute, Greece

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 November 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CIKM04

Sponsor:

CIKM04: Conference on Information and Knowledge Management

November 12 - 13, 2004

Washington DC, USA

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
1,352
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Troumpoukis AKonstantopoulos SProkopaki-Kostopoulou N(2022)A geospatial source selector for federated GeoSPARQL queryingOpen Research Europe10.12688/openreseurope.14605.22(48)Online publication date: 6-Oct-2022
https://doi.org/10.12688/openreseurope.14605.2
Troumpoukis AKonstantopoulos SProkopaki-Kostopoulou N(2022)A geospatial source selector for federated GeoSPARQL queryingOpen Research Europe10.12688/openreseurope.14605.12(48)Online publication date: 19-Apr-2022
https://doi.org/10.12688/openreseurope.14605.1
Lo CHuang WHo MSun MChen LSakai KKu W(2022) Recurrent Learning on PM 2.5 Prediction Based on Clustered Airbox Dataset IEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.304763434:10(4994-5008)Online publication date: 1-Oct-2022
https://doi.org/10.1109/TKDE.2020.3047634
Chaudhry NYousaf MKhan M(2020)Indexing of real time geospatial data by IoT enabled devices: Opportunities, challenges and design considerationsJournal of Ambient Intelligence and Smart Environments10.3233/AIS-200565(1-32)Online publication date: 8-Jul-2020
https://doi.org/10.3233/AIS-200565
Chen BHuang FFang YHuang ZLin H(2019)An approach for heterogeneous and loosely coupled geospatial data distributed computingComputers & Geosciences10.1016/j.cageo.2010.01.00236:7(839-847)Online publication date: 3-Jan-2019
https://dl.acm.org/doi/10.1016/j.cageo.2010.01.002
Karimi HRoongpiboonsopit D(2012)Are Clouds Ready for Geoprocessing?Cloud Computing and Services Science10.1007/978-1-4614-2326-3_16(295-312)Online publication date: 17-Mar-2012
https://doi.org/10.1007/978-1-4614-2326-3_16
Capek JKomarkova JKotsis GTaniar DPardede E(2009)Trustworthy regional spatial information through web-servicesProceedings of the 11th International Conference on Information Integration and Web-based Applications & Services10.1145/1806338.1806440(543-547)Online publication date: 14-Dec-2009
https://dl.acm.org/doi/10.1145/1806338.1806440
Ahullo JLopez PArtigas MGomez Skarmeta A(2008)Supporting geographical queries onto DHTs2008 33rd IEEE Conference on Local Computer Networks (LCN)10.1109/LCN.2008.4664201(435-442)Online publication date: Oct-2008
https://doi.org/10.1109/LCN.2008.4664201
Zimmermann RKu WWang HZand ABardet J(2006)A Distributed Geotechnical Information Management and Exchange ArchitectureIEEE Internet Computing10.1109/MIC.2006.9210:5(26-33)Online publication date: 1-Sep-2006
https://dl.acm.org/doi/10.1109/MIC.2006.92
Tang GChen LLiu YLiu SJing N(2005)Integrated k-NN query processing based on geospatial data servicesProceedings of the 4th international conference on Grid and Cooperative Computing10.1007/11590354_71(554-559)Online publication date: 30-Nov-2005
https://dl.acm.org/doi/10.1007/11590354_71

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten