Analysis of Outlier Effects on Spatial Indices

다국어 초록 (Multilingual Abstract)

Outliers in spatial databases influence on the performance of spatial indexing methods including R-tree. They enlarge the size and overlapping area of MBRs in R-tree which are important factors in determining the performance. In this paper, we give an analysis of outlier effects on R-tree by analytical and experimental work, and propose a method for properly handling outliers. Our experimental results show that our method improves about 15 percents of the performance.

국문 초록 (Abstract)

공간 데이터베이스에서 예외자는 R-tree 계열의 공간색인의 성능에 많은 영향을 미친다. 즉, 예외자로 인하여 R-tree 계열의 공간색인에서 최소경계사각형의 넓이가 불필요하게 넓어지고 겹침 현상이 심해지게 되고 이로 인해 질의처리 시 더 많은 디스크 접근을 필요하게 된다. 따라서, 본 논문에서는 예외자가 공간색인에 주는 영향을 분석하여, 예외자를 미리 처리할 경우, 얼마만큼의 성능을 향상시킬 수 있는지 비용모델과 적절한 예외자의 처리방법을 제안한다. 그리고 실험을 통해 예외자를 미리 처리함으로써 어느 정도의 공간색인의 질의처리 성능을 향상시킬 수 있는지 보여준다. 실험 결과에 따른면, 본 논문에서 제안된 예외자의 처리방법이 기존의 공간색인의 성능을 평균 15%정도 향상시킬 수 있음을 보여준다.

참고문헌 (Reference)

1 "Towards an Analysis of Range Query Performance in Spatial Data Structures" 214-221, 1993

2 "R-trees a dynamic index structure for spatial searching" 47-57, 1984

3 "Optimization Issues in R-tree Construction" 270-273, 1994

4 "LOF: Identifying density-based local outliers," 93-104, 2000

5 "Efficient cost models for spatial queries using R-trees" 19-32, 200019-32

6 "Efficient algorithms for mining outliers from large data sets" 427-438, 2000

7 "Analysis of R-trees Using the Concept of Fractal Dimension" 4-13, 1994

8 "An efficient and robust access method for points and rectangles" 322-331, 1990

9 "Algorithms for mining distance-based outliers in large datasets" 392-403, 1998

10 "A simple and efficient algorithm for R-tree packing" 497-506, 1997

11 "A dynamix index for multi-dimensional objects" 1987