지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 저널정보
- Korean Institute of Information Scientists and Engineers 정보과학회논문지 : 데이타베이스 정보과학회논문지 : 데이타베이스 제30권 제6호
- 발행연도
- 2003.12
- 수록면
- 651 - 665 (15page)
이용수
초록· 키워드
오류제보하기
매년 CPU 속도가 60% 정도 증가되고, 메모리 속도가 10% 증가되는 현실에서, 캐쉬 미스(Cache miss)를 얼마나 줄이느냐 하는 문제가 현재의 주기억 데이타베이스 환경에서 가장 중요한 문제로 대두되었다. 최근 연구들에서는 R-트리의 변형 모델인 CR-트리와 같은 인덱스 구조들이 제시되었으나, 이는 손실 발생 가능한 압축 기법을 사용함으로써 검색 기능이 더 나빠질 수 있다는 문제점이 있다.
본 논문에서는 MR-트리라고 이름 붙여진 캐쉬 동작에 민감한 R-트리의 새로운 변형 모델을 제시한다. MR-트리는 리프가 아닌 중간 노드 엔트리들을 100%에 가깝게 사용하여 결과적으로 트리의 높이와 중간 노드 엔트리의 MBR을 줄여주는 효과를 준다. 이를 위해 노드 분할 발생시 입력 경로 상에 하나 이상의 빈 엔트리를 지니는 중간 노드가 존재할 경우에만, 노드 분할을 상위로 전송하고, 존재하지 않을 경우 새롭게 생성된 노드는 분할된 노드의 자식 노드가 된다. MR-트리는 이와 같은 동작으로 인해 발생 가능한 트리 불균형 문제를 높이 균형화(HeightBalance) 알고리즘을 수행함으로써 해결한다. 한편, 본 논문에서는 MR-트리를 캐쉬 동작에 더욱 민감한 트리형태로 만들기 위해 CCMR-트리를 제안한다. 본 논문의 실험과 분석 결과, 2차원의 MR-트리는 약간의 개선된 수정 속도와 비슷한 메모리 사용량을 기록하며, 기존의 R-트리에 비해 2.4배 이상의 빠른 검색 속도를 나타냈다.
본 논문에서는 MR-트리라고 이름 붙여진 캐쉬 동작에 민감한 R-트리의 새로운 변형 모델을 제시한다. MR-트리는 리프가 아닌 중간 노드 엔트리들을 100%에 가깝게 사용하여 결과적으로 트리의 높이와 중간 노드 엔트리의 MBR을 줄여주는 효과를 준다. 이를 위해 노드 분할 발생시 입력 경로 상에 하나 이상의 빈 엔트리를 지니는 중간 노드가 존재할 경우에만, 노드 분할을 상위로 전송하고, 존재하지 않을 경우 새롭게 생성된 노드는 분할된 노드의 자식 노드가 된다. MR-트리는 이와 같은 동작으로 인해 발생 가능한 트리 불균형 문제를 높이 균형화(HeightBalance) 알고리즘을 수행함으로써 해결한다. 한편, 본 논문에서는 MR-트리를 캐쉬 동작에 더욱 민감한 트리형태로 만들기 위해 CCMR-트리를 제안한다. 본 논문의 실험과 분석 결과, 2차원의 MR-트리는 약간의 개선된 수정 속도와 비슷한 메모리 사용량을 기록하며, 기존의 R-트리에 비해 2.4배 이상의 빠른 검색 속도를 나타냈다.
목차
요약
Abstract
1. 서론
2. 관련연구
3. MR-트리
4. 분석
5. 실험
6. 결론
참고문헌
저자소개
참고문헌 (0)
참고문헌 신청함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
트리의 노드 - 위치배정 알고리즘의 분석
한국정보과학회 학술발표논문집
1993 .04
-
공간 객체를 위한 색인 방법의 설계 및 성능 평가
(구)정보과학회논문지
1991 .10
-
트리구조의 배전계통 데이타베이스 구성과 트리탐색기법
대한전기학회 학술대회 논문집
1992 .07
-
캐시를 고려한 T - 트리 인덱스 구조
정보과학회논문지 : 데이타베이스
2005 .02
-
신속한 공간 검색을 위한 파티션 매핑 기반 R-tree
대한공간정보학회 학술대회
2009 .09
-
제한된 분지수를 가지는 최소지름 신장트리
정보과학회논문지 : 시스템 및 이론
2004 .02
-
압축 지역성 수준에 기반한 캐쉬 인식 압축 색인
멀티미디어학회논문지
2010 .07
-
특징공간을 사선 분할하는 퍼지 결정트리 유도
정보과학회논문지 : 소프트웨어 및 응용
2002 .04
-
일반 트리를 미적으로 도시하기 위한 분할-정복 알고리즘
정보과학회논문지(A)
1999 .01
-
Performance of Spatial Join Operations using Multi-Attribute Access Methods
한국GIS학회지
1999 .10
-
트리 기반 멀티캐스팅 프로토콜의 트리 구성에 관한 성능 평가 연구
한국통신학회 학술대회논문집
2000 .11
-
메시지 다이제스트를 이용한 구조화된 문서의 변화 탐지
한국정보과학회 학술발표논문집
2002 .10
-
(2,4)-트리를 이용한 그룹키 관리
정보보호학회논문지
2001 .08
-
영상 처리 방법을 이용한 트리 길이와 열화면적 계측
조명·전기설비
1994 .02
-
일반 트리 도시 알고리즘
한국정보과학회 학술발표논문집
2000 .04
-
최소신장트리를 위한 크루스칼 알고리즘의 효율적인 구현
한국컴퓨터정보학회논문지
2014 .07
-
3D 게임 공간 분할 트리에서 트리 빌드 휴리스틱
한국게임학회 논문지
2013 .08
이 논문의 저자 정보
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2009-569-017860478