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

논문 상세정보

공간 질의 최적화를 위한 힐버트 공간 순서화에 따른 공간 분할
Spatial Partitioning using filbert Space Filling Curve for Spatial Query Optimization

황환규   (강원대학교 전기전자정보통신공학부UU0000037  ); 김현국   (강원대학교 대학원 정보통신공학과UU0000037  );
  • 초록

    공간 질의 크기에 대한 근사치를 구하기 위해서는 입력 데이터 공간을 분할한 후 분할된 영역에 대하여 질의 결과 크기를 추정한다. 본 논문에서는 데이터 편재가 심한 공간 데이터에 대한 질의 크기 추정의 문제를 논의한다. 공간을 분할하는 기법으로 관계 데이터베이스에서 많이 사용되는 너비 균등, 높이 균등 히스토그램에 해당되는 면적 균등, 개수 균등 분할에 대한 방법을 검토하고 공간 인덱싱에 기초한 공간 분할방법에 대해서 알아본다. 본 논문에서는 공간 순서화 기법인 힐버트 공간 채움 곡선을 이용한 공간 분할을 제안한다. 제안한 방법과 기존의 방법을 실제 데이터와 인위 데이터를 사용하여 편재된 공간 데이터에 대한 질의 결과 크기의 추정에 대한 정확도를 비교한다. 본 실험에서 힐버트 채움 곡선에 의한 공간 분할이 공간 질의 크기 버켓 수의 변화, 데이터 위치 편재도의 변화, 데이터 크기의 변화에 대해서 기존의 분할 방법보다 질의 결과 크기 추정에 대해서 우수한 성능을 보였다.


    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)

    1. Piatetsky-Shapiro,G. and C.Connell, 'Accurate Estimation of the Number of Tuples Satisfying a Condition,' Proc. SIGMOD Intl. Conf. on Management of Data, 1984 
    2. Tiger/line files(tm), 1992 Technical Documentation, Technical Report, U.S. Bureau of the Census, 1992 
    3. Zipf, G. K., 'Human behavior and the principle of least effort,' Addison-Wesley, 1949 
    4. Beckman,N., H.P.Kriegel, R.Schneider and B.Seeger, 'The $R^*$-Trees : An Efficient and Robust Access Method for Points and Rectangles,' Proc. SIGMOD Intl. Conf. on Management of Data, pp.322-331, 1990 
    5. Poosala,V. and Y.Ioannidis, 'Selectivity Estimation without the Attribute Value Independence Assumption,' Proc. SIGMOD Intl. Conf. on Management of Data, 1997 
    6. Faloutsos,C. and S.Roseman, 'Fractals for Secondary Key Retrieval,' Proc. SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp.247-252, 1989 
    7. Lipton, R.J., J.F.Naughton and D.A.Schneider, 'Practical Selectivity Estimation through Adaptive Sampling,' Proc. SIGMOD Intl. Conf. on Management of Data, pp.1-11, 1990 
    8. Chen,C.M. and N.Roussopoulos, 'Adaptive Selectivity Estimation using Query Feedback,' Proc. SIGMOD Intl. Conf. on Management of Data, pp.161-172, 1994 
    9. Acharya,S., V.Poosala and S.Ramaswamy, 'Selectivity Estimation in Spatial Databases,' Proc. SIGMOD Intl. Conf. on Management of Data, 1999 
    10. Ubell,M., 'The Mantage Extensible Datablade Architecture,' Proc. SIGMOD Intl. Conf. on Management of Data, 1994 
    11. Selinger,P., M.M.Astrahan, D.D.Chamberin, R.A.Lorie, T.G.Price, 'Access Path Selection in a Relational Database Mangement System,' Proc. SIGMOD Intl. Conf. on Management of Data, pp.23-34, 1979 
    12. Poosala,V., Y.Ioannidis, P.Haas and E.Shekida, 'Improved Histogram for Selectivity Estimation of Range Predicates,' Proc. SIGMOD Intl. Conf. on Management of Data, pp.294-305, 1996 
    13. Guting,R.H., 'An Introduction to Spatial Database Systems,' The VLDB Journal, Vol.3, No.4, pp.357-400, October, 1994 
    14. ARC/INFO, 'ARC/INFO,Understaning GIS - the ARC/INFO Method,' ARC/INFO, 1993 

 저자의 다른 논문

  • 황환규 (8)

    1. 1996 "계층 그리드 화일을 이용한 선택률 추정에서 발생되는 오차 분석" 電子工學會論文誌. Journal of the Korea institute of telematics and electronics. B b33 (9): 24~36    
    2. 1998 "분할 시그너춰 화일을 위한 효율적인 디렉토리 관리 기법" 電子工學會論文誌. Journal of the Korean Institute of Telematics and Electronics. C c35 (3): 32~45    
    3. 2000 "공간 데이터베이스를 위한 새로운 위상 관계 유도 알고리즘" 電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. CI, 컴퓨터 37 (2): 11~20    
    4. 2004 "공간 데이터베이스에서 질의 결과 크기 추정을 위한 공간 분할" 電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. CI, 컴퓨터 41 (2): 23~32    
    5. 2006 "점진적인 순차 패턴 갱신 알고리즘" 電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. CI, 컴퓨터 43 (5): 17~28    
    6. 2008 "영역기반 이미지 검색을 위한 칼라 이미지 세그멘테이션" 電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. CI, 컴퓨터 45 (1): 11~24    
    7. 2017 "동적 및 정적 관심점을 이용하는 사람 계수 기법" 방송공학회논문지 = Journal of broadcast engineering 22 (1): 70~77    
    8. 2017 "운동 히스토리 영상을 활용한 CamShift 기반 손 추적 기법" 방송공학회논문지 = Journal of broadcast engineering 22 (2): 182~192    
  • 김현국 (0)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

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

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

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

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

이 논문과 함께 이용한 콘텐츠
이 논문과 함께 출판된 논문 + 더보기