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

논문 상세정보

다차원 대용량 저밀도 데이타 큐브에 대한 고밀도 서브 큐브 추출 알고리즘
Dense Sub-Cube Extraction Algorithm for a Multidimensional Large Sparse Data Cube

이석룡   (한국외국어대학교 산업정보시스템공학부UU0001411  ); 전석주   (서울대학교 컴퓨터교육학과UU0000691  ); 정진완   (한국과학기술원 전자전산학과 및 Image Information Research CenterUU0001375  );
  • 초록

    데이타 웨어하우스는 기업이나 사회 전반에서 사용되는 방대한 데이타를 저장하고, 효율적인 분석을 가능하게 하는 데이타 저장소로써, 점점 그 활용도가 증가하고 있다. 본 연구에서는 이러한 데이타 웨어하우스 구축 기술의 핵심이 되는 다차원 데이타 큐브 (multidimensional data cube) 기술을 연구하는 데 목적이 있다. 고차원 데이타 큐브에는 필연적으로 내재하는 데이타의 희소성 (sparsity)에 의한 검색 오버헤드가 있다. 본 연구에서는 이러한 오버헤드를 현격하게 감소시키는 알고리즘을 제시함으로써, 데이타 웨어하우스의 효율을 높이는 데 기여한다. 즉, 고차원의 희소 데이타 큐브에서 데이타가 조밀하게 밀집된 영역들을 찾아 그 영역을 중심으로 서브 큐브를 구축하여, 데이타 검색 시에 전체의 데이타 큐브를 대상으로 하지 않고 해당 서브 큐브만으로 검색 대상을 제한시킴으로써 검색 효율을 높이는 알고리즘이다. 본 논문에서는 다 차원 대용량의 희소 데이타 큐브로부터 밀도가 높은 서브 큐브를 찾기 위하여 비트맵과 히스토그램에 기반한 알고리즘을 제안하며, 실험을 통하여 제안한 알고리즘의 효용성을 보여준다.


    A data warehouse is a data repository that enables users to store large volume of data and to analyze it effectively. In this research, we investigate an algorithm to establish a multidimensional data cube which is a powerful analysis tool for the contents of data warehouses and databases. There exists an inevitable retrieval overhead in a multidimensional data cube due to the sparsity of the cube. In this paper, we propose a dense sub-cube extraction algorithm that identifies dense regions from a large sparse data cube and constructs the sub-cubes based on the dense regions found. It reduces the retrieval overhead remarkably by retrieving those small dense sub-cubes instead of scanning a large sparse cube. The algorithm utilizes the bitmap and histogram based techniques to extract dense sub-cubes from the data cube, and its effectiveness is demonstrated via an experiment.


  • 주제어

    데이타 큐브 .   데이타웨어하우스.  

  • 참고문헌 (8)

    1. S. J. Chun, C. W. Chung, J. H. Lee and S. L. Lee, Dynamic Update Cube for Range-Sum Queries, Proceedings of Int'l Conference on Very Large Data Bases, Italy, 2001, pp. 521-530 
    2. C. Y. Chan and Y. E. Ioannidis, Hierarchical cubes for range-sum queries, Proceedings of Int'l Conference on Very Large Data Bases, Scotland, 1999, pp. 675-686 
    3. D.W. Cheung, B. Zhou, B. Kao, H. Kan and S.D. Lee, Towards the building of a Dense-Region Based OLAP System, Data and Knowledge Engineering, Elsevier Science, V36, 1-27, 2001 
    4. S. Geffner, D. Agrawal, and A. El Abbadi, The Dynamic Data Cube, Proceedings of Int'l Conference on Extending Database Technology, Germany, 2000, pp. 237-253 
    5. S. Geffner, D. Agrawal, and A. El Abbadi, T. Smith, Relative prefix sums: an efficient approach for quering dynamic OLAP Data Cubes, Proceedings of Int'l Conference on Data Engineering, Australia, 1999, pp, 328-335 
    6. C. Ho, R. Agrawal, N. Megido, and R. Srikant, Range queries in OLAP Data Cubes, Proceedings of ACM SIGMOD Int'l Conference on Management of Data, 1997, pp, 73-88 
    7. U. S. Census Bureau, Census bureau databases, The online data are available on the web at http://www.census.gov/ 
    8. J. S. Vitter and M. Wang, Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets, Proceedings of ACM SIGMOD Int'l Conference on Management of Data, Pennsylvania, 1999, pp. 193-204 

 저자의 다른 논문

  • 이석룡 (15)

    1. 2002 "VDCluster : 대용량 비디오 시퀀스를 위한 비디오 세그멘테이션 및 클러스터링 알고리즘" 정보과학회논문지. Journal of KIISE. 데이타베이스 29 (3): 168~179    
    2. 2003 "의미 정보를 이용한 다차원 데이터 시퀀스의 유사성 척도 연구" 정보처리학회논문지. The KIPS transactions. Part D. Part D d10 (2): 283~292    
    3. 2003 "웹상의 이질적 이미지 데이터베이스를 선택하기 위한 복합 추정 방법" 정보과학회논문지. Journal of KIISE. 데이타베이스 30 (5): 464~475    
    4. 2004 "비디오 데이터 세트의 하이퍼 사각형 표현에 기초한 비디오 유사성 검색 알고리즘" 정보처리학회논문지. The KIPS transactions. Part D. Part D d11 (4): 823~834    
    5. 2006 "비디오 검색 시스템을 위한 데이터 시퀀스 패턴 유사성 검색" 정보처리학회논문지. The KIPS transactions. Part D. Part D d13 (3): 347~356    
    6. 2006 "가변적인 길이의 특성 정보를 지원하는 특성 가중치 조정 기법" 정보과학회논문지. Journal of KIISE. 데이타베이스 33 (4): 372~383    
    7. 2006 "지형/지물 이미지 데이타베이스를 위한 형태 특징 추출 방법" 정보과학회논문지. Journal of KIISE. 데이타베이스 33 (4): 384~395    
    8. 2008 "윤곽선 이미지 피라미드와 관심영역 검출을 이용한 SIFT 기반 이미지 유사성 검색" 정보과학회논문지. Journal of KIISE. 데이타베이스 35 (4): 345~355    
    9. 2008 "SIFT를 이용한 유사 위성 영상 검색" 정보과학회논문지. Journal of KIISE. 데이타베이스 35 (5): 379~390    
    10. 2009 "위성영상 검색에서 사용자 관심영역을 이용한 적합성 피드백" 정보과학회논문지. Journal of KIISE. 데이타베이스 36 (6): 434~445    
  • 정진완 (49)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

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

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

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

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

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