개선된 공간 해쉬 조인 알고리즘을 이용한 편중 데이터 처리 기법
Skewed Data handling Technique Using an Enhanced Spatial Hash Join Algorithm
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
지난 수년 동안 공간 데이터의 조인 연산에 대한 많은 연구가 진행되어 왔다. 본 논문에서는 공간 조인연산 시 인덱스가 존재하지 않을 경우, 후보 객체의 여과 단계 처리에 중점을 둔다. 이 분야에 대한 여러 알고리즘들이 제안되었으며 대부분의 경우 공간 데이터의 조인 연산 시 우수한 성능을 나타내고 있다. 하지만, 조인을 위한 입력 테이블의 객체들이 편중되어 분포할 경우 조인 성능이 급격히 저하되는 문제점을 가지고 있으며 이 문제를 해결하려는 연구는 미흡한 실정이다. 따라서, 본 논문에서는 공간 데이터의 편중 문제를 개선하기 위해 기존의 공간 조인 알고리즘 중 Spatial Hash Join 알고리즘과 SSSJ 알고리즘의 장점을 결합한 Spatial Hash Strip Join 알고리즘을 제안한다. 이 알고리즘은 SHJ 알고리즘의 객체 분포에 기반한 공간 분할 특성과 공간 조인 시 SSSJ 알고리즘의 우수한 I/O 특성을 이용한다. 본 논문에서 제안한 SHSJ 알고리즘의 성능 평가를 위해 Tiger/line 데이터를 사용하여 기존 SHJ 알고리즘과 성능을 비교 평가 하였으며 평가 결과 인덱스가 존재하지 않는 입력 테이블에 대한 공간 조인 연산 시 모든 평가 파라미터에 대해 기존의 SHJ 알고리즘보다 우수함이 검증되었다.
Abstract
Much research for spatial join has been extensively studied over the last decade. In this paper, we focus on the filtering step of candidate objects for spatial join operations on the input tables that none of the inputs is indexed. In this case, many algorithms has presented and showed excellent performance over most spatial data. However, if data sets of input table for the spatial join are skewed, the join performance is dramatically degraded. Also, little research on solving the problem in the presence of skewed data has been attempted. Therefore, we propose a spatial hash strip join (SHSJ) algorithm that combines properties of the existing spatial hash join (SHJ) algorithm based on spatial partition for input data set's distribution and SSSJ algorithm. Finally, in order to show SHSJ the outperform in uniform/skew cases, we experiment SHSJ using the Tiger/line data sets and compare it with the SHJ algorithm.
참고문헌 (16)
- J.A. Orenstein, "Redundancy in Spatial Databases", pp.294-305 (1989)
- M. L. Lo, "Spatial Hash-Joins", pp.209-220 (1996)
- L. Arge, "Scalable Sweeping Based Spatial Join", pp.570~581 (1998)
- U. S, "2002 Tiger", line Files, 2002., ~
- A. Guttman, "A Dynamic Index Structure for Spatial Searching In Proceedings of ACM SIGMOD International Conference on Management of Data", pp.47~57 (1984)
- L. Becker, "A New Algorithm for Computing of Spatial Joins Using R-trees In Proceedings of the Ninth International Conference on Data Engineering"
- T. Brinkhoff, "Multi-Step Processing of Spatial Joins In Proceedings of ACM SIGMOD International Conference on Management of Data"
- R. Elmasri, "Fundamental of Database systems", pp.594~600 (2000), Addison-Wesley Publishers
- M. L. Lo, "In Proceedings of ACM SIGMOD International Conference on Management of Data", pp.209~220 (1994)
- M. L. Lo, "Generating seeded trees from data sets", pp.328~347 (1995)
- N. Mamoulis, "Slot Index Spatial Join", feb., pp.15(1), 2003~
- M. L. Lo, "The Design and Implementation of Seeded Trees An Efficient Method for Spatial Joins", 10(1), pp.136~151 (1998)
- J. M. Patel, "Partition Based Spatial-Merge Join", pp.259-270 (1996)
- N. Koudas, "Size Separation Spatial Join", pp.324-335 (1997)
- R. H. Buting, "A Practical Divide- and-Conquer Algorithm for the Rectangle Intersection Problem", 42(2), pp.95~112 (1987)
- J. Edgington, "A Simple and Efficient Algorithm for R-Tree Packing", pp.497~506 (1997)