누적밀도 히스토그램은 사각형 객체의 네 점에 대응하는 4개의 서브 히스토그램을 유지함으로써 사각형 객체가 여러 버켓에 걸쳐질 경우 발생하는 다중 계산 문제를 해결하고 있다. 이 기법은 빠른 추정시간과 정확한 결과를 제공하고 있지만, 질의 윈도우가 그리드 셀의 경계와 일치해야 한다는 제약사항을 기반으로 수행하므로, 실제 응용에 적용시 많은 에러를 초래하게 된다. 따라서, 이 논문에서는 기존 누적밀도 히스토그램에서 질의 윈도우의 제약사항에 관한 영향을 줄이기 위해, 두가지 확률모델을 기반으로 일반화된 누적밀도 히스토그램을 사용한 선택율 추정 기법을 제안하였다. 제안된 두가지 확률 모델은 \circled1질의 영역 비율을 고려한 확률모델과, \circled2교차 영역 정보를 고려한 확률모델이다. 우리는 실제 데이터 셋을 사용하여 제안된 기법을 실험하였다 실험 결과는 이 논문에서 제안된 기법이 기존의 다른 선택율 추정 기법보다 성능이 뛰어남을 보여주고 있다 더구나, 교차 영역 정보를 기반으로 하는 확률모델의 경우 20% 질의 윈도우에서 5% 미만의 낮은 에러율을 보였다. 이 논문에서 제안된 기법은 사각형 객체의 공간 범위 질의의 선택율을 정확하게 추정하는데 사용될 수 있다.
누적밀도 히스토그램은 사각형 객체의 네 점에 대응하는 4개의 서브 히스토그램을 유지함으로써 사각형 객체가 여러 버켓에 걸쳐질 경우 발생하는 다중 계산 문제를 해결하고 있다. 이 기법은 빠른 추정시간과 정확한 결과를 제공하고 있지만, 질의 윈도우가 그리드 셀의 경계와 일치해야 한다는 제약사항을 기반으로 수행하므로, 실제 응용에 적용시 많은 에러를 초래하게 된다. 따라서, 이 논문에서는 기존 누적밀도 히스토그램에서 질의 윈도우의 제약사항에 관한 영향을 줄이기 위해, 두가지 확률모델을 기반으로 일반화된 누적밀도 히스토그램을 사용한 선택율 추정 기법을 제안하였다. 제안된 두가지 확률 모델은 \circled1질의 영역 비율을 고려한 확률모델과, \circled2교차 영역 정보를 고려한 확률모델이다. 우리는 실제 데이터 셋을 사용하여 제안된 기법을 실험하였다 실험 결과는 이 논문에서 제안된 기법이 기존의 다른 선택율 추정 기법보다 성능이 뛰어남을 보여주고 있다 더구나, 교차 영역 정보를 기반으로 하는 확률모델의 경우 20% 질의 윈도우에서 5% 미만의 낮은 에러율을 보였다. 이 논문에서 제안된 기법은 사각형 객체의 공간 범위 질의의 선택율을 정확하게 추정하는데 사용될 수 있다.
Multiple-count problem is occurred when rectangle objects span across several buckets. The CD histogram is a technique which selves this problem by keeping four sub-histograms corresponding to the four points of rectangle. Although It provides exact results with constant response time, there is stil...
Multiple-count problem is occurred when rectangle objects span across several buckets. The CD histogram is a technique which selves this problem by keeping four sub-histograms corresponding to the four points of rectangle. Although It provides exact results with constant response time, there is still a considerable issue. Since it is based on a query window which aligns with a given grid, a number of errors nay be occurred when it is applied to real applications. In this paper, we propose selectivity estimation techniques using the generalized cumulative density histogram based on two probabilistic models : \circled1 probabilistic model which considers the query window area ratio, \circled2 probabilistic model which considers intersection area between a given grid and objects. Our method has the capability of eliminating an impact of the restriction on query window which the existing cumulative density histogram has. We experimented with real datasets to evaluate the proposed methods. Experimental results show that the proposed technique is superior to the existing selectivity estimation techniques. Furthermore, selectivity estimation technique based on probabilistic model considering the intersection area is very accurate(less than 5% errors) at 20% query window. The proposed techniques can be used to accurately quantify the selectivity of the spatial range query on rectangle objects.
Multiple-count problem is occurred when rectangle objects span across several buckets. The CD histogram is a technique which selves this problem by keeping four sub-histograms corresponding to the four points of rectangle. Although It provides exact results with constant response time, there is still a considerable issue. Since it is based on a query window which aligns with a given grid, a number of errors nay be occurred when it is applied to real applications. In this paper, we propose selectivity estimation techniques using the generalized cumulative density histogram based on two probabilistic models : \circled1 probabilistic model which considers the query window area ratio, \circled2 probabilistic model which considers intersection area between a given grid and objects. Our method has the capability of eliminating an impact of the restriction on query window which the existing cumulative density histogram has. We experimented with real datasets to evaluate the proposed methods. Experimental results show that the proposed technique is superior to the existing selectivity estimation techniques. Furthermore, selectivity estimation technique based on probabilistic model considering the intersection area is very accurate(less than 5% errors) at 20% query window. The proposed techniques can be used to accurately quantify the selectivity of the spatial range query on rectangle objects.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
따라서, 이 논문에서는 포인트 객체뿐만 아니라, 사각형객체의 범위 질의에 관한 정확한 선택율을 추정하는 누적밀도 히스토그램의 질의 윈도우에 대한 제약사항의 영향을 최소화하기 위해 두 가지 확률모델을 기반으로 히스토그램의 일반화를 수행하여 선택율 추정하는 기법을 제안한다. 첫번째는 기존의 MinSkew 히스토그램에서 적용하고 있는 확률모델로 데이터 영역과 질의 윈도우 교차 영역의 비율을 고려한 모델이며, 두번째는 데이터의 교차 영역 정보를 이용한 확률모델이다.
그러나, 질의 윈도우가 그리드 셀의 경계와 일치해야 한다는 제약사항을 기반으로 수행되므로, 실제 응용에 적용 시 많은 에러를 초래하게 된다. 따라서, 이러한 문제점을 해결하기 위해 이 논문에서는 두 가지 확률모델을 기반으로 누적 밀도 히스토그램의 일반화를 수행하였다. 제안된 두 가지 확률 모델은 ① 질의 영역 비율을 고려한 확률모델과, ②교차 영역 정보를 고려한 확률모델이다.
기법이 필요하다. 이 논문에서는 히스토그램은 데이터셋이나 질의 윈도우에 대한 제약사항이 적어야 실제 응용에 적용 가능하다는 연구 동기를 기반으로 확률모델을 이용한 누적밀도 히스토그램의 일반화를 통한 선택율 추정기법을 제시한다.
이 절에서는 공간 선택율 추정 기법에 살펴보고, 이 논문의 기반이 되는 누적밀도 히스토그램의 특성에 대해 기술한다.
질의 윈도우에 대한 제약사항이 적어야 한다. 이 절에서는 누적밀도 히스토그램의 질의 윈도우에 대한 제약사항의 영향을 줄이기 위하여 MinSkew 히스토그램 등의 기법에서 사용되고 있는 질의 영역 비율을 기반으로 하는 확률 모델을 이용하여 누적밀도 히스토그램의 일반화를 수행한다.
제안 방법
공간 범위 질의에 대한 선택율 추정기법에 관한 연구로는 [1, 3, 4, 10, 11]가 있고, 특히 영역 객체를 대상으로 하는 히스토그램 기반 접근 방법에는 [3, 4, 7, 9, 11, 13]이 있다. [4, 기에서는 공간 편중을 줄이기 위한 버켓 분할 기법인 MinSkew 알고리즘과 Quad- Tree 기반 분할 알고리즘을 제안하였고, [3, 11]에서는 웨이블릿(wavelet) 기법을 이용한 히스토그램을 제안하였다. 그렇지만, 이들 기법들은 영역 객체를 포인트 객체로 변환하여 처리하므로, 변환에 필요한 시간 오버헤드를 가지게 된다.
또한, 우리는 서로 다른 질의 윈도우 크기에 대한 영향을 평가하기 위해 전체 영역의 5%, 10%, 15%, 20%의 질의 윈도우 20개를 임의로 생성하여 실험하였다.
임의의 20개질의에 대한 실험 결과들에 대한 평균을 구하여 에러율을 측정하였다. 먼저, 기존 누적밀도 히스토그램의 질의 윈도우에 대한 제약사항을 무시하고, 응용에 적용했을 때의 에러율과 일반화된 누적밀도 히스토그램의 에러율을 비교 평가 하였다.
영역 객체의 MBR에 의해 요약 정보를 구성하며, 그리드셀의 수와 같은 N개의 버켓을 사용하고, 각 버켓에는 Hu, Hr, Hui, Hjt 정보를 저장한다. 즉, 누적밀도 히스토그램 CDH 는 다음과 같이 나타낸다.
제안된 두 가지 확률 모델은 ① 질의 영역 비율을 고려한 확률모델과, ②교차 영역 정보를 고려한 확률모델이다. 우리는 실제 데이터셋 과 실험 데이터셋을 사용하여 제안된 기법을 실험하였다. 실험 결과는 이 논문에서 제안된 기법이 기존의 사각형 객체에 대한 선택율 추정기법보다 우수하다는 것을 입증하였다.
보인다. 이 절에서는 기존의 누적밀도 히스토그램에 각 셀과 교차되는 정보를 추가적으로 유지함으로써 교차하는 영역 정보를 기반으로 하는 확률모델을 이용하여 누적 밀도 히스토그램의 일반화를 수행한다.
이 절에서는 먼저 우리가 제안하는 누적밀도 히스토그램의 일반화를 수행하기 위해 사용되는 용어 및 파라메터들에 대해 기술하고, 다음으로 두 가지 확률모델을 이용한 누적밀도 히스토그램의 일반화를 제안한다.
이 절에서는 일반화된 누적밀도 히스토그램의 효율성을 평가하기 위해, 공간 범위 질의에 성능이 뛰어나다고 제안되고 있는 MinSkew 히스토그램, 웨이블릿 히스토그램과비교 평가한다.
(6)의 평균 상대적 에러율을 사용하였다. 임의의 20개질의에 대한 실험 결과들에 대한 평균을 구하여 에러율을 측정하였다. 먼저, 기존 누적밀도 히스토그램의 질의 윈도우에 대한 제약사항을 무시하고, 응용에 적용했을 때의 에러율과 일반화된 누적밀도 히스토그램의 에러율을 비교 평가 하였다.
제안된 기법의 성능 및 효율성을 평가하기 위해, 선택율추정 에러, 선택율 추정시간, 히스토그램 생성 시간 같은 메트릭을 고려하였다.
따라서, 이러한 문제점을 해결하기 위해 이 논문에서는 두 가지 확률모델을 기반으로 누적 밀도 히스토그램의 일반화를 수행하였다. 제안된 두 가지 확률 모델은 ① 질의 영역 비율을 고려한 확률모델과, ②교차 영역 정보를 고려한 확률모델이다. 우리는 실제 데이터셋 과 실험 데이터셋을 사용하여 제안된 기법을 실험하였다.
대상 데이터
에서 제안된 기법의 정확도를 측정하기 위해 512MB의 주 메모리, 40G 하드디스크를 가진 윈도우 2000 운영체제하의 Intel Pentium IV 2GHz PC에서 실험하였다. 실험 데이터 셋으로는 ①실제 서울 중구의 건물 10, 484개 (D1 데이터셋), ②TIGER/LINE의 캘리포니아 데이터셋 2, 249, 727개(D2 데이터셋), ③Sequioa 2000 벤치마크를 위한 22, 288개의 폴리곤 데이터셋(D3 데이터셋)을 대상으로 실험하였다. (그림 5)는 D1 데이터셋의 분포를 보여 주고있다.
이 논문.에서 제안된 기법의 정확도를 측정하기 위해 512MB의 주 메모리, 40G 하드디스크를 가진 윈도우 2000 운영체제하의 Intel Pentium IV 2GHz PC에서 실험하였다. 실험 데이터 셋으로는 ①실제 서울 중구의 건물 10, 484개 (D1 데이터셋), ②TIGER/LINE의 캘리포니아 데이터셋 2, 249, 727개(D2 데이터셋), ③Sequioa 2000 벤치마크를 위한 22, 288개의 폴리곤 데이터셋(D3 데이터셋)을 대상으로 실험하였다.
데이터처리
일반화된 히스토그램의 효율성을 평가하기 위해 기존에제안된 공간 질의 선택율 주정 기법중 그 성능이 우수하다고 제안되고 있는 MinSkew 히스토그램과 웨이블릿 히스토그램과 비교 평가하였다. (그림 7)은 세가지 데이터 셋에대한 그리드 레벨에 따른 평균 상대적 에러율을 보이고 있다.
이론/모형
제안된 기법에 의한 추정치의 정확도를 측정하기 위해 서식 (6)의 평균 상대적 에러율을 사용하였다. 임의의 20개질의에 대한 실험 결과들에 대한 평균을 구하여 에러율을 측정하였다.
성능/효과
(그림 7)은 세가지 데이터 셋에대한 그리드 레벨에 따른 평균 상대적 에러율을 보이고 있다. (그림 7)(a)에서 보여주듯이 이 논문에서 제안된 기법인질의 영역비율을 이용한 GCD 기법과, 교차 영역정보를 이용한 GICD 기법이 웨이블릿 보다는 약 80%, MinSkew보다는 약 24% 뛰어난 것으로 나타냈다. 특히, (그림 7)(b), (그림 7)(c)에서 보여주듯이 교차 영역 정보를 고려한 GICD 기법은 질의 영역을 고려한 GCD 기법보다 약 4%정도 뛰어난 성능을 보이는 것으로 평가되었다.
보였으며, (그림 8)(a), (그림 8)(b)의 실험결과에서는 GICD 기법의 경우, 질의 윈도우 크기가 20%일 경우에 5% 이하의 비교적 정확한 선택율을 추정함을 보여주었다.
(그림 7)(a)에서 보여주듯이 이 논문에서 제안된 기법인질의 영역비율을 이용한 GCD 기법과, 교차 영역정보를 이용한 GICD 기법이 웨이블릿 보다는 약 80%, MinSkew보다는 약 24% 뛰어난 것으로 나타냈다. 특히, (그림 7)(b), (그림 7)(c)에서 보여주듯이 교차 영역 정보를 고려한 GICD 기법은 질의 영역을 고려한 GCD 기법보다 약 4%정도 뛰어난 성능을 보이는 것으로 평가되었다.
이 실험은 D1 데이터셋을 기반으로 실험한 결과이다. 실험 결과는 웨이블릿 히스토그램의 경우 질의윈도우를 1차원 범위 질의로 변환하는 과정이 필요하므로 상당히 많은 시간 오버헤드를 초래한다는 것을 보여주고 있다.
우리는 실제 데이터셋 과 실험 데이터셋을 사용하여 제안된 기법을 실험하였다. 실험 결과는 이 논문에서 제안된 기법이 기존의 사각형 객체에 대한 선택율 추정기법보다 우수하다는 것을 입증하였다. 특히, ②를 기반으로 하는 히스토그램의 경우 기존의 MinSkew, 웨이블릿 히스토그램보다 생성시간, 추정시간, 정확도가 높게 평가 되었으며, ①을 고려하는 히스토그램과는 생성 시간(약 0.
첫번째는 기존의 MinSkew 히스토그램에서 적용하고 있는 확률모델로 데이터 영역과 질의 윈도우 교차 영역의 비율을 고려한 모델이며, 두번째는 데이터의 교차 영역 정보를 이용한 확률모델이다. 실험을 통해서 이 논문에서 제안한 교차 영역 정보를 이용한 선택율 추정기법이 적은 공간 오버헤드를 초래하지만, 기존에 제안된 다른 기법들에 비해 낮은 에러율을 보이고, 선택율 추정을 빠르게 한다는 사실을 보여주었다.
지금까지의 실험 결과 이 논문에서 제안된 기법은 기존의 다른 선택율 추정 기법보다 우수한 것으로 평가되었다. 특히, 교차 영역 정보를 기반으로 하는 GICD 히스토그램의경우 질의 영역을 고려하는 GCD 히스토그램보다는 약 0.
실험 결과는 이 논문에서 제안된 기법이 기존의 사각형 객체에 대한 선택율 추정기법보다 우수하다는 것을 입증하였다. 특히, ②를 기반으로 하는 히스토그램의 경우 기존의 MinSkew, 웨이블릿 히스토그램보다 생성시간, 추정시간, 정확도가 높게 평가 되었으며, ①을 고려하는 히스토그램과는 생성 시간(약 0.26초)이나 추정시간(0.0004초)에서 약간의 오버헤드는 있지만, 선택율 면에서는 약 4%정도 좋은 성능을 나타내었다.
평가되었다. 특히, 교차 영역 정보를 기반으로 하는 GICD 히스토그램의경우 질의 영역을 고려하는 GCD 히스토그램보다는 약 0.26 초의 생성시간에 대한 오버헤드를 가지지만, 선택율 추정면에서는 GCD보다 약 4%정도 뛰어난 것으로 평가되었다.
후속연구
향후의 연구에서는 선택율의 정확성을 높일 수 있는 다른 확률모델을 고려하여 성능을 향상시킬 것이며, 크기가 중가하는 히스토그램을 효율적으로 압축할 수 있는 기법에 관한 연구도 수행할 것이다.
참고문헌 (13)
Alberto Belussi, Christos Faloutsos, 'Estimating the Selectivity of Spatial Queries using the 'Correlation' Fractal Dimension,' InProc. 21st Int. Conf. Very Large Data Bases(VLDB), pp.299-310, Nov., 1995
Alberto Belussi, Christos Faloutsos, 'Self-Spatial Join Selectivity Estimation Using Fractal Concepts,' In Proc. ACM Symp. on Transactions on Information Systems, Vol. 16, No.2, pp.161-201, April, 1998
Yossi Matias, Jeffrey Scott Vitter, Min Wang, 'Wavelet-Based Histograms for Selectivity Estimation,' In Proc. ACM SIGMOD Int. Conf. on Management of Data, pp.448-459, 1998
Swarup Acharya, Viswanath Poosals, Sridhar Ramaswamy, 'Selectivity estimation in spatial databases,' In Proc. ACM SIGMOD Int. Conf. on Management of Data, pp.13-24, 1999
Vitter, Wang, 'Approximate Computation of Multidimensional Aggregates of Sparse Data using Wavelets,' In Proc. ACM SIGMOD Int. Conf. on Management of Data, pp.193-204, 1999
C. Faloutsos, B. Seeger, A. Traina, and Caetano Traina, 'Spatial Join Selectivity Using Power Laws,' In Proc. ACM SIGMOD Int. Conf. on Management of Data, pp.177-188, 2000
A. Aboulnaga, J. Naughton, 'Accurate estimation of the cost of spatial selections,' In Proceedings of the IEEE International Conference on Data Engineering(ICDE), pp.123-134, 2000
Yossi Matias, Jeffrey Scott Vitter, Min Wang, 'Dynamic Maintenance of Wavelet-Based Histograms,' The VLDB, Journal, pp.101-110, Journal , 2000
Jin, N. An, A. Sivasubramaniam, 'Analyzing Range Queries on Spatial Data,' In Proceedings of the IEEE International Conference on Data Engineering(ICDE), pp.525-534, 2000
L. Getoor, B. Taskar, D. Koller, 'Selectivity estimationusing probabilistic models,' In Proc. ACM SIGMOD Int. Conf. on Management of Data, pp.461-473, 2001
Min Wang, Jeffrey Scott Vitter, Lipyeow Lim, Sriram Padmanabhan, 'Wavelet-based cost Estimation for Spatial Queries,' In Proc. Int. Symp. on Spatial and Temporal Databases, pp.175-196, 2001
Ning An, Zhen-Yu Yang, Sivasubramaniam, A., 'Selectivity estimation for spatial joins,' In Proceedings of the IEEE International Conference on Data Engineering(ICDE), pp.368-375, 2001
C. Sun, D. Agrawal and A. El Abbadi, 'Exploring Spatial Datasets with Histograms,' In Proceedings of the IEEE International Conference on Data Engineering(ICDE), pp.93-102, 2002
※ AI-Helper는 부적절한 답변을 할 수 있습니다.