Parallel algorithms for spatial data partition and join processing

Author

Zhang, Yanchun ; Xiao, Jitian ; Roberts, A.J.

Author_Institution

Dept. of Maths & Comput., Univ. of Southern Queensland, Toowoomba, Qld., Australia

fYear

1997

fDate

10-12 Dec 1997

Firstpage

703

Lastpage

716

Abstract

The spatial join operations combine two sets of spatial data by their spatial relationships. They are among the most important, yet most time-consuming operations in spatial databases. We consider the problem of binary polygon intersection joins based on the filter-and-refine strategy. Our objective is to minimize the I/O cost and the response time for the refinement step. First, a graph model is proposed to formalize the refinement cost and matrix-based sequential data partition algorithms are introduced. Then a parallel data partitioning algorithm is developed with a detailed complexity analysis. Based on the data partition results, a distribution algorithm is also proposed for scheduling parallel spatial join processing

Keywords

computational complexity; database theory; parallel algorithms; query processing; relational algebra; relational databases; scheduling; spatial data structures; visual databases; binary polygon intersection joins; complexity analysis; filter-and-refine strategy; graph model; input output cost; join processing; matrix-based sequential data partition; parallel algorithms; parallel data partitioning algorithm; refinement cost; response time; scheduling; spatial data partition; spatial databases; spatial join operations; Algorithm design and analysis; Chemicals; Clustering algorithms; Costs; Database languages; Filtering; Geometry; Parallel algorithms; Partitioning algorithms; Production facilities;

fLanguage

English

Publisher

ieee

Conference_Titel

Algorithms and Architectures for Parallel Processing, 1997. ICAPP 97., 1997 3rd International Conference on

Conference_Location

Melbourne, Vic.

Print_ISBN

0-7803-4229-1

Type

conf

DOI

10.1109/ICAPP.1997.651536

Filename

651536