Spatial join strategies in distributed spatial DBMS

Lecture notes in computer sciencePublished 1 January 1995

David J. Abel, Beng Chin Ooi, Kian‐Lee Tan, Robert Power, Jeffrey Xu Yu

DOI10.1007/3-540-60159-7_21

Source URL

Citations48

SJR quartileQ2

SJR score0.35

SNIP0.55

TL;DR

The problems of spatial joins between sites are examined, and spatial join processing strategies used in a heterogeneous spatial database system are presented.

Abstract

In a distributed spatial database system, a user may issue a query that relates two spatial relations that are stored at different sites. Because of the sheer volume and complexity of spatial data, spatial joins between two spatial relations at different sites are expensive in terms of computation and transmission cost. In this paper, we examine the problems of spatial joins between sites, and present spatial join processing strategies used in a heterogeneous spatial database system. Preliminary experimental results are reported.

Keywords

Computer Science

R-trees

6,543 Citations1984Antonin Guttman

A dynamic index structure called an R-tree is described which meets this need, and algorithms for searching and updating it are given and it is concluded that it is useful for current database systems in spatial applications.

Principles of Distributed Database Systems

2,349 Citations2019M. TAMER ÖZSU, Patrick Valduriez

This third edition of a classic textbook can be used to teach at the senior undergraduate and graduate levels and concentrates on fundamental theories as well as techniques and algorithms in distributed data management.

Efficient processing of spatial joins using R-trees

575 Citations1993Thomas Brinkhoff, Hans‐Peter Kriegel +1 more

This paper presents a first detailed study of spatial join processing using R-trees, particularly R*-tree, and presents several techniques for improving its execution time with respect to both, CPU- and I/O-time.

Journal of the ACMUsing Semi-Joins to Solve Relational Queries

463 Citations1981Philip A. Bernstein, Dah-Ming W. Chiu

The exact class of relational queries that can be solved using semi-joins is shown and it is shown that queries outside of this class may not even be partially solvable using "short" semi-join programs.

View PDF

ACM SIGMOD RecordSpatial query processing in an object-oriented database system

398 Citations1986Jack Orenstein

Multi-step processing of spatial joins

226 Citations1994Thomas Brinkhoff, Hans‐Peter Kriegel +2 more

This paper presents a complete approach of spatial join processing on complex spatial objects that is based on three steps and reduces the total execution time of the spatial join by factors.

View PDF

Spatial query processing in an object-oriented database system

182 Citations1986Jack Orenstein

This work unifies much of the work on spatial query processing capabilities by identifying common principles and distilling them into a small set of constructs that can be supported with only minor modifications to current DBMS implementations.

View PDF

Spatial joins using seeded trees

159 Citations1994Ming-Ling Lo, Chinya V. Ravishankar

This paper develops a technique that uses intermediate linked lists during tree construction and significantly speeds up the tree construction process and the CPU penalties incurred are also lower except when seed-level filtering is used.

Efficient computation of spatial joins

136 Citations2002Oliver Günther

A class of tree structures, called generalization trees, that can be applied efficiently to compute spatial joins in a hierarchical manner are described.

Computer Vision Graphics and Image ProcessingA B+-tree structure for large quadtrees

73 Citations1984David J. Abel

Analysis of space requirements and solution times suggests the B+-tree structure offers advantages in applications involving large quadtrees where use of auxiliary storage is required.