Article

Optimizing distributed spatial joins using R-Trees

Authors:

Orlando Karam,

Fred PetryAuthors Info & Claims

ACMSE '05 vol 1: Proceedings of the 43rd annual ACM Southeast Conference - Volume 1

Pages 222 - 226

https://doi.org/10.1145/1167350.1167417

Published: 18 March 2005 Publication History

Get Access

Abstract

One of the basic problems in distributed databases is how to efficiently perform distributed joins. Spatial databases are particularly appropriate for distribution, but we need special techniques to deal with spatial data efficiently.In this work we study the distributed spatial join problem and how to perform this operation efficiently. We develop cost models for estimating the cost of this operation. We study the issues involved in optimizing it and develop specific techniques using R-Trees. Our techniques outperform other widely-used approaches for this operation.

References

[1]

O. J. A. Redundancy in spatial databases. ACM SIGMOD Conf, 1989.

Digital Library

Google Scholar

[2]

D. J. Abel, B. C. Ooi, K. L. Tan, R. Power, and J. X. Yu, Spatial join strategies in distributed spatial dbms. In Proceedings of the International Symposium on Large Spatial Databases, pages 348--367, Aug. 1995.

Digital Library

Google Scholar

[3]

S. Acharya, V. Poosala, and S. Ramaswamy. Selectivity estimation in spatial databases. In Proceedings ACM SIGMOD, 1999.

Digital Library

Google Scholar

[4]

A. Guttman. R-trees a dynamic index structure for spatial searching. In Proceedings ACM SIGMOD, pages 47--57, June 1984.

Digital Library

Google Scholar

[5]

I. Kamel and C. Faloutsos. Hilbert r-tree: An improved r-tree using fractals. In J. B. Bocca, M. Jarke, and C. Zaniolo, editors, VLDB'94, Proceedings of 20th International Conference on Very Large Data Bases, September 12--15, 1994, Santiago de Chile, Chile, pages 500--509. Morgan Kaufmann, 1994.

Digital Library

Google Scholar

[6]

O. Karam. On optimizing distributyed spatial joins. PhD thesis, Tulane University, 2001.

Digital Library

Google Scholar

[7]

T. Sellis, N. Roussopoulos, and C. Faloutsos. The R+-tree: A dynamic index for multi-dimensional data. In Proceedings VLDB, pages 507--518, Sept. 1987.

Digital Library

Google Scholar

[8]

K.-L. Tan, B. C. Ooi, and D. J. Abel. Exploiting spatial indexes for semijoin-based join processing in distributed spatial databases. IEEE Transactions on Knowledge and Data Engineering.

Digital Library

Google Scholar

[9]

Y. Theodoridis, E. Stefanakis, and T. Sellis. Efficient cost models for spatial queries using R-trees. IEEE Transactions on Knowledge and Data Engineering, 12(1):19--32, 2000.

Digital Library

Google Scholar

[10]

Y. Theodoris, E. Stefanakis, and T. Sellis. Cost models for join queries in spatial databases. In Proceedings ICDE, 1998.

Digital Library

Google Scholar

Cited By

View all

Osborn W(2021)Join Processing in Varying Periodic and Aperiodic Spatial Data StreamsAdvances in Networked-Based Information Systems10.1007/978-3-030-84913-9_4(35-49)Online publication date: 8-Aug-2021
https://doi.org/10.1007/978-3-030-84913-9_4
Osborn W(2020)Join processing in unbounded spatial data streamsProcedia Computer Science10.1016/j.procs.2020.07.035175(237-244)Online publication date: 2020
https://doi.org/10.1016/j.procs.2020.07.035
Osborn W(2019)Exploring Bit Arrays for Join Processing in Spatial Data StreamsAdvances in Networked-based Information Systems10.1007/978-3-030-29029-0_7(73-85)Online publication date: 15-Aug-2019
https://doi.org/10.1007/978-3-030-29029-0_7
Show More Cited By

Recommendations

Multi-way Spatial Joins Using R-Trees: Methodology and Performance Evaluation
SSD '99: Proceedings of the 6th International Symposium on Advances in Spatial Databases

We propose a new multi-way spatial join algorithm called M-way R-tree join which synchronously traverses M R-trees. The M-way R-tree join can be considered as a generalization of the 2-way R-tree join. Although a generalization of the 2-way R-tree join ...
Optimizing distributed spatial joins
Efficient processing of spatial joins using R-trees

Spatial joins are one of the most important operations for combining spatial objects of several relations. The efficient processing of a spatial join is extremely important since its execution time is superlinear in the number of spatial objects of the ...

Comments

Information & Contributors

Information

Published In

ACMSE '05 vol 1: Proceedings of the 43rd annual ACM Southeast Conference - Volume 1

March 2005

408 pages

ISBN:1595930590

DOI:10.1145/1167350

General Chair:
Mario Guimaraes
Kennesaw State University

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 March 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ACM SE05

Sponsor:

ACM SE05: ACM Southeast Regional Conference 2005

March 18 - 20, 2005

Georgia, Kennesaw

Acceptance Rates

Overall Acceptance Rate 502 of 1,023 submissions, 49%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
238
Total Downloads

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

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Osborn W(2021)Join Processing in Varying Periodic and Aperiodic Spatial Data StreamsAdvances in Networked-Based Information Systems10.1007/978-3-030-84913-9_4(35-49)Online publication date: 8-Aug-2021
https://doi.org/10.1007/978-3-030-84913-9_4
Osborn W(2020)Join processing in unbounded spatial data streamsProcedia Computer Science10.1016/j.procs.2020.07.035175(237-244)Online publication date: 2020
https://doi.org/10.1016/j.procs.2020.07.035
Osborn W(2019)Exploring Bit Arrays for Join Processing in Spatial Data StreamsAdvances in Networked-based Information Systems10.1007/978-3-030-29029-0_7(73-85)Online publication date: 15-Aug-2019
https://doi.org/10.1007/978-3-030-29029-0_7
Zaamout SOsborn W(2013)A strategy for optimizing a multi-site query in a distributed spatial databaseProceedings of the 12th international conference on Web and Wireless Geographical Information Systems10.1007/978-3-642-37087-8_2(16-24)Online publication date: 4-Apr-2013
https://dl.acm.org/doi/10.1007/978-3-642-37087-8_2

View Options

Login options

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

Cited By

Recommendations

Multi-way Spatial Joins Using R-Trees: Methodology and Performance Evaluation