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

논문 상세정보

부분키 기법과 압축 기법을 혼용한 주기억장치 상주형 다차원 색인 구조
A Main Memory-resident Multi-dimensional Index Structure Employing Partial-key and Compression Schemes

심정민   (한국전자통신연구원 디지탈홈연구단CC0186800  ); 민영수   (충북대학교 정보통신공학UU0001309  ); 송석일   (충주대학교 컴퓨터공학UU0001317  ); 유재수   (충북대학교 전기전자컴퓨터공학부UU0001309  );
  • 초록

    최근 중앙처리장치와 주기억장치간의 병목 현상에 의한 성능 저하를 극복하기 위해 캐시를 고려한 색인 구조들이 제안되었다. 이런 색인 구조들의 궁극적인 목표는 엔트리 크기를 줄여 팬-아웃(fan-out)을 증가시키고, 캐시 접근 실패를 최소화하여 시스템의 성능을 높이는 것이다. 엔트리의 크기를 줄이는 기법에 따라 기존의 색인 구조들을 두 가지로 구분할 수 있다. 하나는 좌표 값을 고정된 비트로 양자화 함으로써, MBR 키를 압축하는 것이다. 또 다른 하나는 MBR들의 각 좌표 값 중에 그들의 부모 MBR과 같지 않은 좌표 값만을 저장하는 것이다. 우선, 본 논문에서는 두 기법의 특성들을 적절히 조합한 새로운 색인 구조를 제안하고, 기존에 제시된 두 접근법을 따르는 주기억장치 상주형 다차원 색인 구조를 다양한 환경에서 성능 평가한다. 또한, 기존의 색인 구조와 비교를 통해 제안하는 색인 구조의 우수성을 보인다.


    Recently, to relieve the performance degradation caused by the bottleneck between CPU and main memory, cache conscious multi-dimensional index structures have been proposed. The ultimate goal of them is to reduce the space for entries so as to widen index trees and minimize the number of cache misses. The existing index structures can be classified into two approaches according to their entry reduction methods. One approach is to compress MBR keys by quantizing coordinate values to the fixed number of bits. The other approach is to store only the sides of minimum bounding regions (MBRs) that are different from their parents partially. In this paper, we propose a new index structure that exploits the properties of the both techniques. Then, we investigate the existing multi-dimensional index structures for main memory database system through experiments under the various work loads. We perform various experiments to show that our approach outperforms others.


  • 주제어

    캐시 .   다차원 색인구조 .   주기억장치 상주형 데이타베이스 시스템.  

  • 참고문헌 (11)

    1. Scott T. Leutenegger, J, M. Edgington, Mario A. Lopez, 'STH: A Simple and Efficient Algorithm for R-Tree Packing,' Proceedings of ICDE, pp. 497-506, 1997 
    2. Scott T. Leutenegger, 'Multi Dimensional Data Sets,' http://www.cs.du.edu/~leut/MultiDimData.html 
    3. Anastassia Ailamaki, David J. DeWitt, Mark D Hill and David A. Wood, 'DBMSs on a Modem Processor: Where Does Time Go?,' Proceedings of VLDB, pp. 2&3-277, 1999 
    4. Stefan Manegold, Peter A. Boncz and Martin L. Kersten, 'Optimizing database architecture for the new bottleneck: memory access,' VLDB Journal Vol.9, No.3, pp. 231-246, 2000 
    5. Jun Rao and Kenneth A. Ross, 'Cache Conscious Indexing for Decision-Suppoert in Main Memory,' Proceedings of VLDB, pp. 78-79, 1999 
    6. Jun Rao and Kenneth A. Ross, 'Making B+-Trees Cache Conscious in Main Memory,' Proceedings of ACM SIGMOD, pp. 475-486, 2000 
    7. Philip Bohannon, Peter Mcilroy and Rajeev Rastogi, 'Main-Memory Index Structures with Fixed-Size Partial Keys,' Proceedings of ACM SIGMOD, pp. 163-174, 2001 
    8. Shimin Chen, Phillip B. Gibbons and Todd C. Mowry, 'Improving Index Performance through Prefetching,' Proceedings of ACM SlGMOD, pp. 235-246, 2001 
    9. Kihong Kim, Sang K. Cha and Keunjoo Kwon, 'Optimizing Multidimensional Index Trees for Main Memory Access,' Proceeding of ACM SIGMOD, pp. 139-150, 2001 
    10. I. Sitzmann and P.J. Stuckey, 'Compacting discriminator information for spatial trees,' Proceedings of the Thirteenth Australasian Database, pp. 167-176, 2002 
    11. Guttman, A., 'Rrtrees: a Dynamic Index Structure for Spatial Searching,' Proceedings of ACM SIGMOD, pp. 47-47, 1984 

 저자의 다른 논문

  • 심정민 (1)

    1. 2006 "네트워크 고장감내 소프트웨어 스트리밍 기술의 설계 및 구현" 한국콘텐츠학회논문지 = The Journal of the Korea Contents Association 6 (10): 126~133    
  • 민영수 (3)

  • 유재수 (179)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

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

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

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

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

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