본문 바로가기
KERD
논문KCI 등재

압축된 공간 히스토그램을 이용한 선택율 추정 기법

Selectivity Estimation Using Compressed Spatial Histogram

김상호|류근호|이진열|지정희
한국정보처리학회|2004.04|정보처리학회논문지D (The KIPS Transactions : Part D)|제11권 제2호|pp. 281-292

1

조회

0

다운로드

0

인용

0

참고문헌

키워드

질의 처리(Query Processing)선택율 추정(Selectivity Estimation)압축(Compression)공간 히스토그램(Spatial Histogram)웨이블릿(Wavelet)
주제분류공학

초록

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

Abstract

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. "데이터베이스 시스템에서 웨이블릿 변환에 기반한 통합 요약정보의 관리" (2001), 한국과학 기술원
  2. "시간적 제약을 갖는 공간 질의 처리를 위한 실시간 연산 후배치 기법", 7(3호), pp.193~210 (2001)
  3. "공간 영역 질의의 선택율 추정을 위한 향상된 면적 균등 분할 방법", Vol.4 (2000)
  4. "다차원 히스토그램에서 범위 질의의 선택도에 대한 오차 추정", 28(2), pp.211~213
  5. "다차원 히스토그램을 이용한 공간 위상 술어의 선택도 추정 기법", 제6권(제4호^), pp.841~850 (1999)
  6. "Improved Histograms for Selectivity Estimation of Range Predicates", pp.294~305 (1996)
  7. "Wavelet-Based Histograms for Selectivity Estimation", pp.448~459 (1998)
  8. "Selectivity estimation in spatial databases", pp.13~24 (1999)
  9. "Approximate Computation of Multidimensional Aggregates of Sparse Data using Wavelets", pp.193~204 (1999)
  10. "Accurate estimation of the cost of spatial selections In Proceedings of the IEEE International Conference on Data Engineering", pp.123~134 (2000)
  11. "Dynamic Maintenance of Wavelet-Based Histograms", pp.101~110 (2000)
  12. "In Proc. ACM SIGMOD Int. Conf. on Management of Data" (2001)
  13. "Selectivity estimation of complex spatial queries", pp.156~174 (2001)
  14. "Wavelet-based cost Estimation for Spatial Queries", p, pp.p.175-~196 (2001)
  15. "Selectivity estimation for spatial joins", pp.368~375 (2001)
  16. "Selectivity for spatial joins with geometric selections", pp.609~626 (2002)
  17. "Selectivity estimation for spatio-temporal queries to moving objects", pp.440~451 (2002)
  18. "Selectivity Estimation for Predictive Spatio-Temporal Queries", pp.417~428 (2003)
  19. "Exploring spatial datasets with histograms University of California" (2001), Computer Science Department, University of California
  20. "Extended Wavelets for Multiple Measures", pp.pp. 229-~240 (2003)
  21. "Approximate query processing using wavelets", pp.pp. 199-~223 (2001)
  22. "Wavelet Synopses with Error Guarantees", pp.~5 (2002)
  23. "Query Optimization" (1996)
  24. "A Comparison of Methods for Representing Topological Relationships", pp.149~178 (1995)
  25. "Analyzing Range Queries on Spatial Data", pp.525~534 (2000)
  26. "On Rectangular Partitionings in Two Dimensions：" (1999)
  27. "Spatial Selectivity Estimation Using Wavelet", pp.459~462 (2003)
  28. "Selectivity Estimation for Spatial Databases" (2003)

관련 논문AI추천

시공간 데이터베이스를 위한 히스토그램 기반 선택도 추정 기법신병철, 이종연한국정보처리학회 · 정보처리학회논문지D2005 · 제12권 제1호일반화된 누적밀도 히스토그램을 이용한 공간 선택율 추정김상호, 류근호, 지정희한국정보처리학회 · 정보처리학회논문지D2004 · 제11권 제4호고차원에서 선택율 추정을 위한 블록 히스토그램 압축방법박선, 이주홍, 전석주한국정보처리학회 · 정보처리학회논문지D2003 · 제10권 제6호공간 질의 최적화를 위한 힐버트 공간 순서화에 따른 공간 분할김현국, 황환규한국정보처리학회 · 정보처리학회논문지D2004 · 제11권 제1호개선된 공간 해쉬 조인 알고리즘을 이용한 편중 데이터 처리 기법심영복, 이종연한국정보처리학회 · 정보처리학회논문지D2005 · 제12권 제2호다이나믹 데이터 웨어하우스 환경에서 OLAP 영역-합 질의의 효율적인 처리 방법이주홍, 전석주한국정보처리학회 · 정보처리학회논문지D2003 · 제10권 제3호

이 간행물의 다른 논문 (24건)

이동 객체의 유사 부분궤적 검색을 위한 시그니쳐-기반 색인 기법심춘보, 장재우pp. 247-258OGIS OLE DB 기반의 공간관련성을 가진 분산 공간객체의 변경 프로토콜김동현, 홍봉희, 문상호pp. 259-268고차원 데이터의 효율적인 최근접 객체 검색 기법박영배, 김진호pp. 269-280실체뷰 캐쉬 기법을 이용한 XML 질의 처리 시스템의 구현박정기, 강현철, 문찬호pp. 293-304객체-관계형 데이터베이스를 이용한 XML 문서 저장 기법이월영, 용환승pp. 305-316
원문 보기