대표어
한국학술지인용색인(NRF)
권호기사보기
| 기사명 | 저자명 | 페이지 | 원문 | 기사목차 |
|---|
국회도서관 홈으로
정보검색
소장정보 검색
결과 내 검색
동의어 포함
목차보기
목차
CC-GiST : 임의의 캐시 인식 검색 트리를 효율적으로 구현하기 위한 일반화된 프레임워크 / 노웅기 ; 김원식 ; 한욱신 1
요약 1
ABSTRACT 1
1. 서론 1
2. 관련 연구 2
2.1. 캐시 인식 트리 2
2.2. 디스크 기반의 GiST 3
3. 캐시 인식하는 CC-GiST 3
3.1. CC-GiST 개념 3
3.2. 구조 및 특성 4
3.3. 포인터 메소드 5
3.4. 키 메소드 5
3.5. 트리 메소드 5
3.5.1. 검색 6
3.5.2. 삽입 6
3.5.3. 삭제 8
4. CC-GiST를 이용한 캐시 인식 트리의 구현 9
4.1. CSB+-트리의(이미지참조) 구현 9
4.2. pkB-트리의 구현 10
4.3. CR-트리의 구현 10
5. 성능 분석 11
6. 결론 13
참고문헌 13
[저자소개] 14
초록보기
최근 메인 메모리 가격이 하락하고 용량이 크게 증가함에 따라 메인 메모리 데이터베이스에 기반한 응용이 급격히 증가하고 있다. 캐시 미스(cache miss)는 CPU에서 액세스하고자 하는 데이터가 캐시에 존재하지 않아 메모리로부터 읽어 들이는 과정이며, 메인 메모리 데이터베이스의 성능 감소의 중요한 원인이다. 메인 메모리 데이터베이스에서의 캐시 미스를 줄이고 캐시를 최대한 활용하기 위하여 여러 가지 캐시 인식 트리들(cache conscious trees)이 제안되었다. 이러한 캐시 인식 트리들은 각각 특성이 다르므로 하나의 응용에서 둘 이상의 캐시 인식 트리들이 동시에 관리될 수 있다. 또한, 만약 기존의 캐시 인식 트리가 응용에서의 요구를 만족시키지 못하면 새로운 캐시 인식 트리를 구현하여야 한다.본 논문에서는 캐시 인식하는 일반화된 검색 트리(Cache-Conscious Generalized Search Tree, CC-GiST)를 제안한다. CC-GiST는 디스크 기반의 일반화된 검색 트리(Generalized Search Tree, GiST) [HNP95]를 캐시 인식하도록 확장한 것이며, 포인터 압축(pointer compression)과 키 압축(key compression) 기법을 비롯하여 임의의 캐시 인식 트리의 공통적인 기능 및 알고리즘들을 동시에 제공한다. CC-GiST를 기반으로 특정 캐시 인식 트리를 구현하려면 그 트리에 해당된 기능만을 구현하면 된다. 본 논문에서는 CC-GiST를 기반으로 기존의 대표적인 캐시 인식 트리인 CSB+-트리, pkB-트리, CR-트리를 구현하는 방법을 기술한다. CC-GiST를 이용함에 따라 메인 메모리 데이터베이스 응용에서 여러 개의 캐시 인식 트리를 관리하는 번거로움에서 벗어날 수 있고, 응용의 요구에 따른 새로운 캐시 인식 트리를 최소한의 노력으로 효율적으로 구현할 수 있다.
According to recent rapid price drop and capacity growth of main memory, the number of applications on main memory databases is dramatically increasing. Cache miss, which means a phenomenon that the data required by CPU is not resident in cache and is accessed from main memory, is one of the major causes of performance degradation of main memory databases. Several cache-conscious trees have been proposed for reducing cache miss and making the most use of cache in main memory databases. Since each cache-conscious tree has its own unique features, more than one cache-conscious tree can be used in a single application depending on the application’s requirement. Moreover, if there is no existing cache-conscious tree that satisfies the application’s requirement, we should implement a new cache-conscious tree only for the application’s sake.In this paper, we propose the cache-conscious generalized search tree (CC-GiST). The CC-GiST is an extension of the disk-based generalized search tree (GiST) [HNP95] to be cache-conscious, and provides the entire common features and algorithms in the existing cache-conscious trees including pointer compression and key compression techniques. For implementing a cache-conscious tree based on the CC-GiST proposed in this paper, one should implement only a few functions specific to the cache-conscious tree. We show how to implement the most representative cache-conscious trees such as the CSB+-tree, the pkB-tree, and the CR-tree based on the CC-GiST. The CC-GiST eliminates the troublesomeness caused by managing more than one cache-conscious tree in an application, and provides a framework for efficiently implementing arbitrary cache-conscious trees with new features.
According to recent rapid price drop and capacity growth of main memory, the number of applications on main memory databases is dramatically increasing. Cache miss, which means a phenomenon that the data required by CPU is not resident in cache and is accessed from main memory, is one of the major causes of performance degradation of main memory databases. Several cache-conscious trees have been proposed for reducing cache miss and making the most use of cache in main memory databases. Since each cache-conscious tree has its own unique features, more than one cache-conscious tree can be used in a single application depending on the application’s requirement. Moreover, if there is no existing cache-conscious tree that satisfies the application’s requirement, we should implement a new cache-conscious tree only for the application’s sake.In this paper, we propose the cache-conscious generalized search tree (CC-GiST). The CC-GiST is an extension of the disk-based generalized search tree (GiST) [HNP95] to be cache-conscious, and provides the entire common features and algorithms in the existing cache-conscious trees including pointer compression and key compression techniques. For implementing a cache-conscious tree based on the CC-GiST proposed in this paper, one should implement only a few functions specific to the cache-conscious tree. We show how to implement the most representative cache-conscious trees such as the CSB+-tree, the pkB-tree, and the CR-tree based on the CC-GiST. The CC-GiST eliminates the troublesomeness caused by managing more than one cache-conscious tree in an application, and provides a framework for efficiently implementing arbitrary cache-conscious trees with new features.
권호기사
참고문헌 (14건) : 자료제공( 네이버학술정보 )
| 번호 | 참고문헌 | 국회도서관 소장유무 |
|---|---|---|
| 1 | (1999) DBMS on a Modern Processor: Where Does Time Go, | 미소장 |
| 2 | (1998) The Asilomar Report on Database Research, | 미소장 |
| 3 | (2001) Main- Memory Index Structures with Fixed-Size Partial Keys, | 미소장 |
| 4 | (1999) Database Architecture Optimized for the New Bottleneck: Memory Access, | 미소장 |
| 5 | (1998) Cache-Conscious Data-Placement, | 미소장 |
| 6 | (1998) Improving Pointer Based Codes through Cache-Conscious Data Placement, | 미소장 |
| 7 | (2000) Making Pointer Based Data Structures Cache Conscious, | 미소장 |
| 8 | A Dynamic Index Structure For Spatial Searching ” In Proc Management of Data, | 미소장 |
| 9 | (1995) Generalized Search Trees for Database Systems, | 미소장 |
| 10 | (2001) Optimizing Multidimensional Index Trees for Main Memory Access, | 미소장 |
| 11 | (1986) “A Study of Index Structures for Main Memory Database Management Systems ” In Proc, | 미소장 |
| 12 | (1999) Cache conscious indexing for decision-support in main memory, | 미소장 |
| 13 | (2000) Making B+-trees Cache Conscious in Main Memory, | 미소장 |
| 14 | (1994) “Cache Conscious Algorithms for Relational Query Processing ” In Proc, | 미소장 |
MARC 보기
오류 데이터 정정요청
*표시는 필수 입력사항입니다.
알림톡 발송
| 전화번호 |
|---|
개인정보 수정 바로가기
연속간행물 권호 선택
우편복사 안내
- ◾ 도서관을 방문하지 못할 경우 인터넷, 팩스 등으로 자료 복사를 신청하고, 복사물을 우편·팩스 등으로 제공받는 서비스
- ◾ 대상자료: 일반도서, 연속간행물 및 학위논문
- ※ 고서, 고잡지, 훼손될 우려가 있는 자료, 마이크로폼 자료 및 신문 등 제외
- ◾ 신청 책수: 1인 5책 이하(1일 기준)
- ◾ 신청 절차: 자료 검색 → 우편복사 목록담기 → 복사 범위 입력 → 우편복사 주문서 입력 → 접수 및 확인
- ※ 저작권법에 의거하여 부분 복사(전체 페이지 수의 1/3 범위 이내)만 가능
- ◾ 복사 범위 입력 예시: (연속 페이지) 1-30, (부분 페이지) 25, 30-40
| 번호 | 발행일자 | 권호명 | 제본정보 | 자료실 | 원문 | 신청 페이지 |
|---|
도서위치안내(서울관)
도서위치안내: / 서가번호:
0
확인
우편복사 목록담기를 완료하였습니다.
내서재에 담기
새로운 서재
*표시는 필수 입력사항입니다.
저장
저장 되었습니다.