공간 질의 최적화를 위한 힐버트 공간 순서화에 따른 공간 분할
Spatial Partitioning using HilbertSpace Filling Curve for Spatial Query Optimization
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
공간 질의 크기에 대한 근사치를 구하기 위해서는 입력 데이터 공간을 분할한 후 분할된 영역에 대하여 질의 결과 크기를 추정한다. 본 논문에서는 데이터 편재가 심한 공간 데이터에 대한 질의 크기 추정의 문제를 논의한다. 공간을 분할하는 기법으로 관계 데이터베이스에서 많이 사용되는 너비 균등, 높이 균등 히스토그램에 해당되는 면적 균등, 개수 균등 분할에 대한 방법을 검토하고 공간 인덱싱에 기초한 공간 분할 방법에 대해서 알아본다. 본 논문에서는 공간 순서화 기법인 힐버트 공간 채움 곡선을 이용한 공간 분할을 제안한다. 제안한 방법과 기존의 방법을 실제 데이터와 인위 데이터를 사용하여 편재된 공간 데이터에 대한 질의 결과 크기의 추정에 대한 정확도를 비교한다. 본 실험에서 힐버트 채움 곡선에 의한 공간 분할이 공간 질의 크기, 버켓수의 변화, 데이터 위치 편재도의 변화, 데이터 크기의 변화에 대해서 기존의 분할 방법보다 질의 결과 크기 추정에 대해서 우수한 성능을 보였다.
Abstract
In order to approximate the spatial query result size we partition the input rectangles into subsets and estimate the query result size based on the partitioned spatial area. In this paper we examine query result size estimation in skewed data. We examine the existing spatial partitioning techniques such as equi-area and equi-count partitioning, which are analogous to the equi-width and equi-height histograms used in relational databases, and examine the other partitioning techniques based on spatial indexing. In this paper we propose a new spatial partitioning technique based on the Hilbert space filling curve. We present a detailed experimental evaluation comparing the proposed technique and the existing techniques using synthetic as well as real-life datasets. The experiments showed that the proposed partitioning technique based on the Hilbert space filling curve achieves better query result size estimation than the existing techniques for space query size, bucket numbers, skewed data, and spatial data size.
참고문헌 (14)
- GutingR. H, "An Introduction to Spatial Database Systems", 3(4), pp.357~400 (1994)
- ARC, "INFO", Understaning GIS - the ARC, pp.1993.[DOI]
- Ubell, "The Mantage Extensible Datablade Architecture" (1994)
- Selinger, "Access Path Selection in a Relational Database Mangement System Proc. SIGMOD Intl. Conf. on Management of Data", pp.23~34 (1979)
- Poosala, "Improved Histogram for Selectivity Estimation of Range Predicates", pp.pp.294-~305 (1996)
- Lipton, "Practical Selectivity Estimation through Adaptive Sampling", pp.1~11 (1990)
- Chen,C. M, "Adaptive Selectivity Estimation using Query Feedback", pp.161~172 (1994)
- Acharya, S.,, "Selectivity Estimation in Spatial Databases" (1999)
- Poosala, "Selectivity Estimation without the Attribute Value Independence Assumption" (1997)
- Faloutsos,C, "Fractals for Secondary Key Retrieval", pp.247~252 (1989)
- Beckman, "The R*-Trees：An Efficient and Robust Access Method for Points and Rectangles", pp.322-331 (1990)
- G, "Accurate Estimation of the Number of Tuples Satisfying a Condition Proc. SIGMOD Intl. Conf. on Management of Data" (1984)
- Tiger, "line files", U. S. Bureau of the Census, 1992technicaldocumentation1992., ~
- Zipf, "Human behavior and the principle of least effort" (1949)