본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

압축된 공간 히스토그램을 이용한 선택율 추정 기법
Selectivity Estimation Using Compressed Spatial Histogram

지정희   (충북대학교 대학원 전자계산학UU0001309  ); 이진열   (포인트 아이CC0012133  ); 김상호   (충북대학교 대학원 전자계산학UU0001309  ); 류근호   (충북대학교 전기전자 및 컴퓨터공학부UU0001309  );
  • 초록

    공간 질의에 대한 선택율 추정은 가장 효율적인 실행 계획을 찾는데 이용되는 매우 중요한 과정이다. 공간 도메인이 큰 경우, 기존 연구의 요약정보는 상대적으로 적은 정보로 선택율을 추정하기 때문에 좋은 선택율을 유지하기 어렵다. 따라서, 이 논문에서는 작은 저장공간에 공간요약정보를 압축하는 새로운 기법인 MW 히스토그램을 제안한다. 이 히스토그램은 MinSkew 분할 알고리즘과 웨이블릿 변환이 결합되어 적은 저장공간에서도 타당한 선택율과 압축효과를 얻을 수 있고, 동적 갱신에 대해 효율적으로 대처할 수 있는 구조를 가진다. 실험 결과를 통하여, 버켓 수가 0.3M/6인 MW 히스토그램이 5%-20% 질의에서 평균적으로 좋은 성능을 보이고 있어, MW 히스토그램이 적은 저장공간에서 더 좋은 선택율을 얻을 수 있음을 확인시켜주었다.


    Selectivity estimation for spatial query is very important process used in finding the most efficient execution plan. Many works have been performed to estimate accurate selectivity. Although they deal with some problems such as false-count, multi-count, they can not get such effects in little memory space. Therefore, we propose a new technique called MW Histogram which is able to compress summary data and get reasonable results and has a flexible structure to react dynamic update. Our method is based on two techniques : (a) MinSkew partitioning algorithm which deal with skewed spatial datasets efficiently (b) Wavelet transformation which compression effect is proven. The experimental results showed that the MW Histogram which the buckets and wavelet coefficients ratio is 0.3 is lower relative error than MinSkew Histogram about 5%-20% queries, demonstrates that MW histogram gets a good selectivity in little memory.


  • 주제어

    질의 처리 .   선택율 추정 .   압축 .   공간 히스토그램 .   웨이블릿.  

  • 참고문헌 (28)

    1. Jin Yul Lee, Jeong Hee Chi, Keun Ho Ryu, 'Spatial Selectivity Estimation Using Wavelet,' Proceddings of the 4th International Symposium on Advanced Intelligent Systems, ISSN 1738-0073, ISIS2003, pp.459-462, Sepmtember, 2003 
    2. Jeong Hee Chi, Jin Yul Lee and Keun Ho Ryu, 'Selectivity Estimation for Spatial Databases,' Asian Conference on Remote Sensing & International Symposium on Remote Sensing (ISRS), November, 2003 
    3. S. Muthukrishnan, Viswanath Poosala, Torsten Suel, 'On Rectangular Partitionings in Two Dimensions : Algorithms, Complexity, and Applications,' 7th International Conference on Database Theory, ICDT'99, 1999 
    4. E. Clementini and P. Di Felice, 'A Comparison of Methods for Representing Topological Relationships,' Information Sciences 3, pp.149-178, 1995 
    5. 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 
    6. Yannis E. Ioannidis, 'Query Optimization,' ACM survey, 1996 
    7. Kaushik C, Minos G., Rajeev R., Kyuseok S., 'Approximate query processing using wavelets,' The VLDB Journal, pp. 199-223, 2001 
    8. Minos G., Phillip B.G ., 'Wavelet Synopses with Error Guarantees,' ACM SIGMOD, Jine 4-5, Madison, Wisconsin, USA, 2002 
    9. Antonios Deligiannakis, Nick Roussopoulos., 'Extended Wavelets for Multiple Measures,' ACM SIGMOD 2003, pp. 229-240, June, 2003 
    10. Yong-Jin Choi, Chin-Wan Chung, 'Selectivity estimation for spatio-temporal queries to moving objects,' In Proc. ACM SIGMOD Int. Conf. on Management of Data, pp. 440-451, 2002 
    11. Tao, Y., Sun, J., Papadias, D., 'Selectivity Estimation for Predictive Spatio-Temporal Queries' In Proceedings of the IEEE International Conference on Data Engineering (ICDE), pp.417-428. 2003 
    12. Sun, C, Agrawal, D., El Abbadi, A., 'Exploring spatial datasets with histograms (full version),' Technical Report, Computer Science Department, University of California, santa Barbara, 2001 
    13. C. Sun, D. Agrawal, A. El Abbadi, 'Selectivity for spatial joins with geometric selections,' Proc. of EDBT, pp.609-626, 2002 
    14. 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 
    15. 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 
    16. L. Getoor, B. Taskar, D. Roller, 'Selectivity estimation using probabilistic models,' In Proc. ACM SIGMOD Int. Conf. on Management of Data, 2001 
    17. Nikos Mamoulis, Dimitris Papadias, 'Selectivity estimation of complex spatial queries,' In Proc. Int. Symp. on Spatial and Temporal Databases, pp.156-174, 2001 
    18. Yossi Matias, Jeffrey Scott Vitter, Min Wang, 'Dynamic Maintenance of Wavelet-Based Histograms,' The VLDB Journal, pp.101-110, 2000 
    19. 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 
    20. 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 
    21. 김홍연, 배해영, 다차원 히스토그램을 이용한 공간 위상 술어의 선택도 추정 기법, 정보처리논문지, 제6권 제4호,pp.841 850, April, 1999     
    22. Poosala et al., 'Improved Histograms for Selectivity Estimation of Range Predicates' In Proc. ACM SIGMOD Int. Conf. on Management of Data, pp.294-305, 1996 
    23. 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 
    24. Swarup Acharya, Viswanath Poosala, Sridhar Ramaswamy, 'Selectivity estimation in spatial databases' In Proc. ACM SIGMOD Int. Conf. on Management of Data, pp.13-24,1999 
    25. 문현수, 황환규, '공간 영역 질의의 선택율 추정을 위한 향상된 면적 균등 분할 방법', Journal of Telecommunications and Information, Vol. 4, 2000 
    26. 정지훈, 홍석진, 배진욱, 안성준, 송병호, 이석호, '다차원 히스토그램에서 범위 질의의 선택도에 대한 오차 추정', 정보과학회 2001년 추계학술대회, Vo1.28, No.2, pp.211-213     
    27. 엄정옥, 조숙경, 배해영, '시간적 제약을 갖는 공간 질의 처리를 위한 실시간 연산 후배치 기법', 정보과학회논문지 : 컴퓨팅의 실재, 제7권 제3호, pp.l93-21O, June, 2001 
    28. 조문증, '데이터베이스 시스템에서 웨이블릿 변환에 기반한 통합 요약정보의 관리', 전자전산학과 전산학전공, 한국과학기술원 박사논문, 2001 
  • 이 논문을 인용한 문헌 (2)

    1. Chi, Jeong-Hee ; Lee, Jin-Yul ; Kim, Sang-Ho ; Ryu, Keun-Ho 2004. "Selectivity Estimation Using Compressed Spatial Histogram" 정보처리학회논문지. The KIPS transactions. Part D. Part D, d11(2): 281~292     
    2. Chi, Jeong-Hee ; Jeong, Jae-Hyuk ; Ryu, Keun-Ho 2005. "Spatial Selectivity Estimation using Cumulative Wavelet Histograms" 정보과학회논문지. Journal of KIISE. 데이타베이스, 32(5): 547~557     

 저자의 다른 논문

  • Chi, Jeong-Hee (10)

    1. 2002 "OGC 기반의 위상관계 연산 알고리즘" 데이타베이스 연구 = Database research 18 (1): 29~40    
    2. 2003 "불확실한 시공간 객체에 관한 위상 관계 알고리즘" 정보처리학회논문지. The KIPS transactions. Part D. Part D d10 (6): 873~884    
    3. 2004 "CORBA 서비스의 성능 향상을 위한 인터페이스 설계" 정보처리학회논문지. The KIPS transactions. Part D. Part D d11 (1): 203~210    
    4. 2004 "일반화된 누적밀도 히스토그램을 이용한 공간 선택율 추정" 정보처리학회논문지. The KIPS transactions. Part D. Part D d11 (4): 983~990    
    5. 2004 "이동객체의 궤적에 대한 연속 최근접 질의 처리" 정보과학회논문지. Journal of KIISE. 데이타베이스 31 (5): 492~504    
    6. 2005 "4차원 시공간 데이터를 위한 OpenGIS 모델의 확장" 정보처리학회논문지. The KIPS transactions. Part D. Part D d12 (3): 375~384    
    7. 2005 "누적밀도 웨이블릿 히스토그램을 이용한 공간 선택율 추정" 정보과학회논문지. Journal of KIISE. 데이타베이스 32 (5): 547~557    
    8. 2005 "수치지도를 위한 피처 기반 공간자료 관리 시스템 설계" 한국공간정보시스템학회 논문지 = Journal of Korea Spatial Information System Society 7 (3): 107~118    
    9. 2005 "데이타 분석을 위한 시공간 집계 함수의 확장" 정보과학회논문지. Journal of KIISE. 데이타베이스 32 (1): 43~55    
    10. 2006 "이동객체를 위한 현재 질의 선택율 추정 기법" 韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information 11 (1): 87~96    
  • Kim, Sang-Ho (13)

  • 류근호 (178)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기