R-tree는 일반적으로 트리 노드의 크기를 디스크 페이지의 크기와 같게 함으로써 I/O 성능이 최적화 되도록 구현한다. 최근에는 주메모리 환경에서 CPU 캐시 성능을 최적화하는 R-tree의 변형이 개발되었다. 이는 노드의 크기를 캐시 라인 크기의 수 배로 하고 MBR에 저장되는 키를 압축하여 노드 하나에 더 많은 엔트리를 저장함으로써 성능을 높였다. 그러나, 디스크 최적 R-tree와 캐시 최적 R-tree의 노드 크기 사이에는 수십-수백 바이트와 수-수십 킬로바이트라는 큰 차이가 있으므로, I/O 최적 R-tree는 캐시 성능이 나쁘고 캐시 최적 R-tree는 디스크 I/O 성능이 나쁜 문제점을 가지고 있다. 이 논문에서는 CPU 캐시와 디스크 I/O에 모두 최적인 R-tree, PR-tree를 제안한다. 캐시 성능을 위해 PR-tree 노드의 크기를 캐시 라인 크기보다 크게 만든 다음 CPU의 선반입(prefetch) 명령어를 이용하여 캐시 실패 횟수를 줄이고, 트리 노드를 디스크 페이지에 낭비가 적도록 배치함으로써 디스크 I/O 성능도 향상시킨다. 또한, 이 논문에서는 PR-tree에서 검색 연산을 수행하는데 드는 캐시 실패 비용을 계산하는 분석 방법을 제시하고, 최적의 캐시와 I/O 성능을 보이는 PR-tree를 구성하기 위해, 가능한 크기의 내부 단말 노드, 중간 노드를 갖는 PR-tree 생성하여 성능을 비교하였다. PR-tree는 디스크 최적 R-tree보다 삽입 연산은 3.5에서 15.1배, 삭제 연산은 6.5에서 15.1배, 범위 질의는 1.3에서 1.9배, k-최근접 질의는 2.7에서 9.7배의 캐시 성능 향상이 있었다. 모든 실험에서 매우 작은 I/O 성능 저하만을 보였다.
R-tree는 일반적으로 트리 노드의 크기를 디스크 페이지의 크기와 같게 함으로써 I/O 성능이 최적화 되도록 구현한다. 최근에는 주메모리 환경에서 CPU 캐시 성능을 최적화하는 R-tree의 변형이 개발되었다. 이는 노드의 크기를 캐시 라인 크기의 수 배로 하고 MBR에 저장되는 키를 압축하여 노드 하나에 더 많은 엔트리를 저장함으로써 성능을 높였다. 그러나, 디스크 최적 R-tree와 캐시 최적 R-tree의 노드 크기 사이에는 수십-수백 바이트와 수-수십 킬로바이트라는 큰 차이가 있으므로, I/O 최적 R-tree는 캐시 성능이 나쁘고 캐시 최적 R-tree는 디스크 I/O 성능이 나쁜 문제점을 가지고 있다. 이 논문에서는 CPU 캐시와 디스크 I/O에 모두 최적인 R-tree, PR-tree를 제안한다. 캐시 성능을 위해 PR-tree 노드의 크기를 캐시 라인 크기보다 크게 만든 다음 CPU의 선반입(prefetch) 명령어를 이용하여 캐시 실패 횟수를 줄이고, 트리 노드를 디스크 페이지에 낭비가 적도록 배치함으로써 디스크 I/O 성능도 향상시킨다. 또한, 이 논문에서는 PR-tree에서 검색 연산을 수행하는데 드는 캐시 실패 비용을 계산하는 분석 방법을 제시하고, 최적의 캐시와 I/O 성능을 보이는 PR-tree를 구성하기 위해, 가능한 크기의 내부 단말 노드, 중간 노드를 갖는 PR-tree 생성하여 성능을 비교하였다. PR-tree는 디스크 최적 R-tree보다 삽입 연산은 3.5에서 15.1배, 삭제 연산은 6.5에서 15.1배, 범위 질의는 1.3에서 1.9배, k-최근접 질의는 2.7에서 9.7배의 캐시 성능 향상이 있었다. 모든 실험에서 매우 작은 I/O 성능 저하만을 보였다.
R-trees have been traditionally optimized for the I/O performance with the disk page as the tree node. Recently, researchers have proposed cache-conscious variations of R-trees optimized for the CPU cache performance in main memory environments, where the node size is several cache lines wide and mo...
R-trees have been traditionally optimized for the I/O performance with the disk page as the tree node. Recently, researchers have proposed cache-conscious variations of R-trees optimized for the CPU cache performance in main memory environments, where the node size is several cache lines wide and more entries are packed in a node by compressing MBR keys. However, because there is a big difference between the node sizes of two types of R-trees, disk-optimized R-trees show poor cache performance while cache-optimized R-trees exhibit poor disk performance. In this paper, we propose a cache and disk optimized R-tree, called the PR-tree (Prefetching R-tree). For the cache performance, the node size of the PR-tree is wider than a cache line, and the prefetch instruction is used to reduce the number of cache misses. For the I/O performance, the nodes of the PR-tree are fitted into one disk page. We represent the detailed analysis of cache misses for range queries, and enumerate all the reasonable in-page leaf and nonleaf node sizes, and heights of in-page trees to figure out tree parameters for best cache and I/O performance. The PR-tree that we propose achieves better cache performance than the disk-optimized R-tree: a factor of 3.5-15.1 improvement for one-by-one insertions, 6.5-15.1 improvement for deletions, 1.3-1.9 improvement for range queries, and 2.7-9.7 improvement for k-nearest neighbor queries. All experimental results do not show notable declines of the I/O performance.
R-trees have been traditionally optimized for the I/O performance with the disk page as the tree node. Recently, researchers have proposed cache-conscious variations of R-trees optimized for the CPU cache performance in main memory environments, where the node size is several cache lines wide and more entries are packed in a node by compressing MBR keys. However, because there is a big difference between the node sizes of two types of R-trees, disk-optimized R-trees show poor cache performance while cache-optimized R-trees exhibit poor disk performance. In this paper, we propose a cache and disk optimized R-tree, called the PR-tree (Prefetching R-tree). For the cache performance, the node size of the PR-tree is wider than a cache line, and the prefetch instruction is used to reduce the number of cache misses. For the I/O performance, the nodes of the PR-tree are fitted into one disk page. We represent the detailed analysis of cache misses for range queries, and enumerate all the reasonable in-page leaf and nonleaf node sizes, and heights of in-page trees to figure out tree parameters for best cache and I/O performance. The PR-tree that we propose achieves better cache performance than the disk-optimized R-tree: a factor of 3.5-15.1 improvement for one-by-one insertions, 6.5-15.1 improvement for deletions, 1.3-1.9 improvement for range queries, and 2.7-9.7 improvement for k-nearest neighbor queries. All experimental results do not show notable declines of the I/O performance.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
이 모델의 목적은 R-tree를 이용하여 범위 질의를 수행할 때 발생하는 디스크 접근 횟수를 분석하는 것이다[11]. Md를 PR-tree가 차지하고 있는 총 페이지 수, Q를 지금까지 수행한 질의의 수, 鸟를 높이 九인 노드 하나가 주어진 질의 사각형과 겹칠 확률이라 하자. Q*는 버퍼를 채울 때까지 필요한 질의의 수의 기대값이라 흐卜자.
여기에서 우리의 목표는 캐시와 디스크 I/O 성능을 최적 화하는 것이다. 캐시 성능을 최적화하기 위해 수식 1의 캐 시 실패 비용을 최소화 하면 되고, 디스크 I/O 성능을 최적 화 하려면 수식 2의 디스크 VO 비용을 최소화 하면 된다.
디스크 I/O에 최적인 R-tree와 CPU 캐시에 최적인 R-tree는 노드의 크기에서 수십-수백 바이트와 수-수십 킬 로바이트라는 큰 차이가 있으므로, 디스크 최적인 경우 CPU 캐시 성능이 떨어지고 CPU 캐시 최적인 경우 디스크 I/O 성능이 좋지 않다. 이 논문에서는 CPU 캐시와 디스크 I/O에 모두 효율적인 PR-tree를 제안하였다. PR-tree는 캐시 성능을 높이기 위해 노드 크기를 캐시 라인보다 크게 하고, 노드에 접근하기 전에 선반입 연산으로 캐시에 노드 데이타를 미리 적재하여 캐시 실패 비용을 줄였고, I/O 성능을 높이기 위해 디스크 페이지에 노드를 최적으로 배치하였다.
이 논문은 캐시와 디스크 모두에 효율적인 R-tree, PR-tree (Prefetching R-tree)를 제안한다. PR-tree는 캐시 성능을 향상시키기 위해 노드의 크기를 캐시라인 크기보다 크게 만들고 최근의 프로세서에서 지원하는 캐시 선반 입 명령어를 이용하여 메모리에 있는 노드데이타를 CPU 캐시에 미리 읽어들임으로써 캐시 실패 비용을 최적화한다.
PR-tree의 디스크 I/O 비용을 분석하기 위해 여기에서 Leutenegger와 Lopez가 제안한 버퍼 모델을 사용한다. 이 모델의 목적은 R-tree를 이용하여 범위 질의를 수행할 때 발생하는 디스크 접근 횟수를 분석하는 것이다[11]. Md를 PR-tree가 차지하고 있는 총 페이지 수, Q를 지금까지 수행한 질의의 수, 鸟를 높이 九인 노드 하나가 주어진 질의 사각형과 겹칠 확률이라 하자.
QRMBR 기법은 자식 노드의 MBR이 부모 노드의 MBR에 포함되는 R-tree의 특성을 이용하여 자식 노드의 MBR을 부모 노드의 MBR에 상대적인 좌표로 바꾸고 일정한 데이타 크기를 갖도록 양자화하는 것이다. 이 연구는 노드 크기에 따라 다양한 종류의 R-tree 변형에 대해 성능을 실험하고 있다. [6].
이 절에서는 범위 질의 성능에 내부 중간, 단말 노드의 크기가 미치는 영향에 대해 분석하겠다. 이를 위해 4.
본 논문의 의의는 다음과 같다. 첫째, 본 논문은 캐시와 디스크에 모두 효율적인 PR-tree를 제안하였다. R-tree를 개선한 새로운 인덱스인 PR-tree를 제시하고, 대량적재, 삽입, 삭제, 범위 질의, k-최근접 질의 등을 효율적으로 처리하는 새로운 알고리즘을 상세한 예와 함께 보였다.
가설 설정
九를 노드의 높이 또는 레벨이라 하고 단말 노드의 높이는 1이라고 가정한다. n을 디스크 페이지의 높이라 하고, 丑o는 루트 디스크 페이지의 높이이다.
각 데이타 객체가 각 차원에 대해[0, 1]인도 메인에 균등분포 (uniform distribution) 되어 있는 점이라고 가정하면 각질의 MBRe hyper cube가 된다. 그리고 같은 높이의 각 노드는 대략 같은 크기를 갖는다고 가정한다.
제안 방법
(그림 20)에서 PR-tree의 검색 연산에 대한 I/O 성능을 보이고 있다. I/O 성능은 질의 당 버퍼 풀에 대해 실패하는 VO 페이지 읽기 요청의 수를 측정하였다. PR-tree와 R-tree 모두 4KB, 8KB, 16KB, 32KB의 페이지 크기에 대해 100만 개의 2차원 균등 분포 점 객체를 대량적재한 후 두 가지 질 의를 수행하였다.
CPU 캐시 성능을 측정하기 위해서, 검색이나 갱신 연산을 수행하기 전에 버퍼 풀에 트리의 모든 페이지를 적재하였다. I/O 성능을 측정하기 위해서는, 첫 질의를 수행하기 전에 모든 버퍼 풀을 비우고 버퍼 풀에 대해 실패하는 I/O 페이지 읽기 횟수를 기록하였다.
이 논문에서는 CPU 캐시와 디스크 I/O에 모두 효율적인 PR-tree를 제안하였다. PR-tree는 캐시 성능을 높이기 위해 노드 크기를 캐시 라인보다 크게 하고, 노드에 접근하기 전에 선반입 연산으로 캐시에 노드 데이타를 미리 적재하여 캐시 실패 비용을 줄였고, I/O 성능을 높이기 위해 디스크 페이지에 노드를 최적으로 배치하였다. 그리고 범위 질의를 수행할 때 드는 캐시 실패 비용을 분석 하였으며, 최적인 성능을 보이는 노드 크기를 결정하기 해 다양한 디스크 크기에 대해 가능한 노드 크기의 PR-tree 를 구현하여 실험하였다.
I/O 성능은 질의 당 버퍼 풀에 대해 실패하는 VO 페이지 읽기 요청의 수를 측정하였다. PR-tree와 R-tree 모두 4KB, 8KB, 16KB, 32KB의 페이지 크기에 대해 100만 개의 2차원 균등 분포 점 객체를 대량적재한 후 두 가지 질 의를 수행하였다. (그림 20)(a)는 크기가 0.
PR-tree와 R-tree의 범위 질의 성능을 비교하기 위해 실험을 하였다. 실험은 페이지 크기와 객체의 수를 변화시켜 가면서 수행하였다.
PR-tree는 캐시 성능을 높이기 위해 노드 크기를 캐시 라인보다 크게 하고, 노드에 접근하기 전에 선반입 연산으로 캐시에 노드 데이타를 미리 적재하여 캐시 실패 비용을 줄였고, I/O 성능을 높이기 위해 디스크 페이지에 노드를 최적으로 배치하였다. 그리고 범위 질의를 수행할 때 드는 캐시 실패 비용을 분석 하였으며, 최적인 성능을 보이는 노드 크기를 결정하기 해 다양한 디스크 크기에 대해 가능한 노드 크기의 PR-tree 를 구현하여 실험하였다. 실험에 의하면 PR-tree는 하나씩 삽입, 삭제, 범위 질의, k-최근접 질의에서 더 좋은 캐시 성능을 보였다.
이 실험 역시 삽입과 삭제 연산을 수행하기 전에 트 리의 모든 페이지를 버퍼 풀에 적재하였고, 삽입과 삭제는 연속적으로 수행하였다. 그리고 삽입과 삭제에 따라 변화되는 페이지를 디스크에 저장하는 시간은 측정된 시간에서 제 외하였으며 삽입을 위해 충분한 버퍼를 미리 확보하여 디스 크 접근을 하지 않도록 했다. (그림 18)(a)는 100만개의 객체를 대량적재한 트리에 10만개의 객체를 하나씩 삽입하는데 걸리는 시간을 보여준다.
여기에서 단말노드를 선택하는 방법은 R-tree의 ChooseLeaf 알고리즘과 같다 [8]. 그리고, InsertEntry 알고리즘을 호출하여 엔트리 E를 노드 N 에 삽입한 다음, 삽입의 결과로 변경된 노드N과 노드분할 이 발생한 경우 새로 생성된 노드N'을 매개 변수로 AdjustTree 알고리즘을 호출한다. AdjustTree 알고리즘은 자식 노드의 변경을 상위 노드로 전파하는 역할을 한다.
삽입 알고리즘은 삽입에 의해 발생하는 트리 구조의 변화에 대해 페이지 분할을 최소화함으로써 페이지와 노드공간을 최적으로 이용한다. 둘째, PR-tree에 대한 범위 질의를 수행하는 데 소요되는 캐시와 I/O 비용을 분석하고, 비용을 계산하는 방법과 수식을 제시하였다. 셋째, 다양한 페이지 크기와 페이지 내부 중간, 단말노드 크기를 갖는 PR-tree를 구현하고 삽입, 삭제, 범위 질의, k-최근접 질의에 대해 실험함으로써 기존의 디스크 기반 R-tree보다 더 나은 성능을 가짐을 보였다.
N에 E를 삽입할 수 없지만, N이 포함된 페이지 안의 다른 노드에 빈 슬롯이 있다. 따라서 노드N과 빈 슬롯이 있는 노드를 포함하는 수직 슬라이스S를 구하고, S와 삽입할 엔트리E에 대해 재구성 알고리즘을 호출한다.
그리고 노드를 디스 크 페이지에 공간의 낭비 없이 배치함으로써 디스크 입출력 성능도 향상시킨다. 또한, 이 논문은 범위 질의를 수행하는 데 발생하는 캐시 실패 비용을 수식으로 표현하여 내부 중간 노드와 단말노드의 크기, 내부 트리의 높이를 정하는 방법을 제시하고, 가능한 페이지 크기와 노드 크기에 대해 그 수식의 값을 최소화함으로써 최적의 PR-tree를 구성하는 방법을 보인다. PR-tree는 디스크 최적 R-tree보다 삽입 연 산은 3.
노드 수준에서는, 각 페이지로 분할된 엔트리를 동일한 대량적재 알고리즘을 이용하여 페이지 내부 트리로 구성한다. 본 논문에서 제안하는 대량적재 알고리즘은 STR 알고리즘 기반으로, 객체를 PR-tree 에 대량적재할 때 공간을 효율적으로 이용하도록 개선하였다 [7]. (그림 4)에서 대량적재 알고리즘을 보인다.
[5]. 본 논문은 fpB*-tree의 기본 구조를 R-tree에 적용하지만, R-tree의 특성에 맞도록 노드구조를 개선하고, 캐시와 VO 성능을 최적화하기 위한 대량적재, 삽입, 재구성 알고리즘을 제안하며, 본 논문에서 제안한 PR-tree가 범위 질의를 수행하는 데 소요되는 캐시와 I/O 비용을 분석하고 최적의 트리 구성 방법을 제시한다.
3절에서 제시한 방법에 의해 설정된 노드 크기를 갖는 PR-tree의 범위 질의 성능을 비교하였다. 실험은 0.1의 크기를 갖는 1000개의 범위 질의를 균등하게 생성하여, 4KB, 8KB, 16KB, 32KB의 페이지 크기에 대해 각각 10만개의 2차원 점 객체를 대량 적재한 PR-tree에 질의하였다.
PR-tree와 R-tree의 범위 질의 성능을 비교하기 위해 실험을 하였다. 실험은 페이지 크기와 객체의 수를 변화시켜 가면서 수행하였다. (그림 15)의 모든 실험은 점 객체를 대량적재한 트리에 질의 크기가 0.
여기에서는 PR-tree와 R-tree의 범위 질의와 k-최근접 질의에 대한 캐시 성능을 비교한다. (그림 17)은 페이지 크기를 변화시켜가면서 100만개의 객체를 대량적재한 PR-tree 와 R-tree에서 질의 크기가 0.
이 절에서 PR-tree와 R-tree의 삽입과 삭제 성능을 비교 한다. 이 실험 역시 삽입과 삭제 연산을 수행하기 전에 트 리의 모든 페이지를 버퍼 풀에 적재하였고, 삽입과 삭제는 연속적으로 수행하였다. 그리고 삽입과 삭제에 따라 변화되는 페이지를 디스크에 저장하는 시간은 측정된 시간에서 제 외하였으며 삽입을 위해 충분한 버퍼를 미리 확보하여 디스 크 접근을 하지 않도록 했다.
이 절에서는 PR-tree와 R-tree의 페이지 크기와 객체 수를 변화시켜 가면서 k-최근접 질의의 성능을 비교하였다. 모든 실험은 k 값이 5인 k-최근접 질의 1000개를 수행할 때 소요 되는 시간을 측정하였다.
이 절에서는 PR-tree의 캐시와 I/O 성능을 측정하기 위해 PR-tree와 디스크 기반 R-tree을 구현하고 비교하였다. 주 메모리 R-tree가 아닌 디스크 기반 R-tree와 비교하는 것은 PR-tree가 디스크 기반 인덱스 구조이기 때문이다.
이 절에서는 범위 질의 성능에 내부 중간, 단말 노드의 크기가 미치는 영향에 대해 분석하겠다. 이를 위해 4.3절에서 제시한 방법에 의해 설정된 노드 크기를 갖는 PR-tree의 범위 질의 성능을 비교하였다. 실험은 0.
하지만, 이와 같은 두 개의 목표는 동시에 달성할 수 없 으므로, 수식 1에서 계산한 캐시 실패 비용이 최적의 5% 안 에 들어오는 내부 단말, 중간 노드 크기 조합에 대해 최대 의 디스크 공간 이용률을 보이는 것을 선택한다. 이를 위해, 디스크 페이지 크기가 4KB, 8KB, 16KB, 32KB인 경우, L> 2, w> l, x > 1이고, 한 페이지 내의 공간을 가장 많이 이용하는 조건을 만족하는 가능한 모든 叫 H의 조합 에 대해 캐시 실패 비용을 계산하였다. (그림 14)는 4KB 페 이지에 대해 캐시 실패 비용 분석 결과를 그래프로 표시하였다.
01 인 범위 질의 1000개를 준 후 수행 시간을 측정하였다. 첫 검색 전에 버퍼 풀에 트 리의 모든 페이지를 적재하였고, 각 질의는 연속적으로 수행하였다. PR-tree의 노드 크기는<표 3>에 페이지별로 지정된 것을 사용하였다.
01 인 범위 질의 1000개를 준 후 수행 시간을 측정하였다. 첫 검색 전에 버퍼 풀에 트 리의 모든 페이지를 적재하였고, 각 질의는 연속적으로 수행하였다. PR-tree의 노드 크기는<표 3>에 페이지별로 지정된 것을 사용하였다.
페이지 크기 4KB, 8KB, 16KB, 32KB에 대해 에 표시된 내부 중간, 단말 노드 크기를 갖는 PR-tree를 구현하여 실험하였다.
대상 데이터
실험은 페이지 크기와 객체의 수를 변화시켜 가면서 수행하였다. (그림 15)의 모든 실험은 점 객체를 대량적재한 트리에 질의 크기가 0.01 인 범위 질의 1000개를 준 후 수행 시간을 측정하였다. 첫 검색 전에 버퍼 풀에 트 리의 모든 페이지를 적재하였고, 각 질의는 연속적으로 수행하였다.
페이지 교체 전략으로는 현재 페이지와 루트 페이지 에 이르는 페이지에 잠금을 하는 기능을 추가한 LRU 알고리즘을 사용하였다. MBR의 크기는 2차원 점 객체에 대해 16바이트이고, 내부 단말 노드 엔트리는 4바이트의 페이지 ID를 자식 포인터로 사용하고, 내부 중간 노드 엔트리는 2 바이트의 페이지 내부 옵셋을 사용하였다. 실험에 사용된 CPU는 Intel Pentium Ⅲ 1GHz이고 LI과 L2 캐시 라인 크기는 모두 32바이트이다.
이 절에서는 PR-tree와 R-tree의 페이지 크기와 객체 수를 변화시켜 가면서 k-최근접 질의의 성능을 비교하였다. 모든 실험은 k 값이 5인 k-최근접 질의 1000개를 수행할 때 소요 되는 시간을 측정하였다. 첫 검색 전에 버퍼 풀에 트리의 모든 페이지를 적재하였고, 각 질의는 연속적으로 수행하였다.
MBR의 크기는 2차원 점 객체에 대해 16바이트이고, 내부 단말 노드 엔트리는 4바이트의 페이지 ID를 자식 포인터로 사용하고, 내부 중간 노드 엔트리는 2 바이트의 페이지 내부 옵셋을 사용하였다. 실험에 사용된 CPU는 Intel Pentium Ⅲ 1GHz이고 LI과 L2 캐시 라인 크기는 모두 32바이트이다. 하드디스크는 5400 rpm 속도의 40GB, 주 메모리는 768MB이고 Redhat Linux가 설치되어 있다.
1 로 최적화 없이 컴파일 하였다. 실험에 사용한 데이타는 [0, 1]의 도메인을 갖는 2차 원 점 객체이며 균등 분포(uniform distributionX 갖는다. CPU 캐시 성능을 측정하기 위해서, 검색이나 갱신 연산을 수행하기 전에 버퍼 풀에 트리의 모든 페이지를 적재하였다.
이론/모형
PR-tree의 디스크 I/O 비용을 분석하기 위해 여기에서 Leutenegger와 Lopez가 제안한 버퍼 모델을 사용한다. 이 모델의 목적은 R-tree를 이용하여 범위 질의를 수행할 때 발생하는 디스크 접근 횟수를 분석하는 것이다[11].
하드디스크는 5400 rpm 속도의 40GB, 주 메모리는 768MB이고 Redhat Linux가 설치되어 있다. 시간 측정에는 wall-clock 시간을 사용하였다. 페이지 크기 4KB, 8KB, 16KB, 32KB에 대해 <표 3>에 표시된 내부 중간, 단말 노드 크기를 갖는 PR-tree를 구현하여 실험하였다.
이 논문에서는 k-최근접 질의를 처리하기 위해 branch and bound 알고리즘을 사용한다. [9].
여기에서는 노드 크기가 커짐에 따라 B-Tree의 높이가 낮아지고 따라서 검색할 때 캐시 실패 비용이 감소하게 되어 성능을 향상시킬 수 있다. 이 연구에서는 범위스캔의 성능을 높이기 위해 점프 포인터 배열 (jump-pointer array) 구조를 이용하였다 [4]. fpB*-tree는 pB*-tree 를 디스크 I/O 에 최적화한 인덱스 구조이다.
R-tree는 Berchtold가 구현한 R*-tree를 수정하여 구현하였 다[12]. 페이지 교체 전략으로는 현재 페이지와 루트 페이지 에 이르는 페이지에 잠금을 하는 기능을 추가한 LRU 알고리즘을 사용하였다. MBR의 크기는 2차원 점 객체에 대해 16바이트이고, 내부 단말 노드 엔트리는 4바이트의 페이지 ID를 자식 포인터로 사용하고, 내부 중간 노드 엔트리는 2 바이트의 페이지 내부 옵셋을 사용하였다.
성능/효과
또한, 이 논문은 범위 질의를 수행하는 데 발생하는 캐시 실패 비용을 수식으로 표현하여 내부 중간 노드와 단말노드의 크기, 내부 트리의 높이를 정하는 방법을 제시하고, 가능한 페이지 크기와 노드 크기에 대해 그 수식의 값을 최소화함으로써 최적의 PR-tree를 구성하는 방법을 보인다. PR-tree는 디스크 최적 R-tree보다 삽입 연 산은 3.5에서 15.1 배, 삭제 연산은 6.5에서 15.1 배, 범위 질의는 1.3에서 1.9배, k-최근접 질의는 2.7에서 9.7배의 성능 향상이 있었다. PR-tree는 모든 실험에서 매우 작은!/。성능 저하만을 보였다.
둘째, PR-tree에 대한 범위 질의를 수행하는 데 소요되는 캐시와 I/O 비용을 분석하고, 비용을 계산하는 방법과 수식을 제시하였다. 셋째, 다양한 페이지 크기와 페이지 내부 중간, 단말노드 크기를 갖는 PR-tree를 구현하고 삽입, 삭제, 범위 질의, k-최근접 질의에 대해 실험함으로써 기존의 디스크 기반 R-tree보다 더 나은 성능을 가짐을 보였다.
그리고 범위 질의를 수행할 때 드는 캐시 실패 비용을 분석 하였으며, 최적인 성능을 보이는 노드 크기를 결정하기 해 다양한 디스크 크기에 대해 가능한 노드 크기의 PR-tree 를 구현하여 실험하였다. 실험에 의하면 PR-tree는 하나씩 삽입, 삭제, 범위 질의, k-최근접 질의에서 더 좋은 캐시 성능을 보였다.
3절에서 설명한 대로 선택하였다. 즉, 각 페이지에 대해 질의 수행 시간이 최고의 5% 안에 들어오는 노드 크기 중에서 가장 좋은 페이지 이용률을 보이는 것을 선택하였다. 표 3에서 구한 최적의 노드 크기는 캐시 실패 비용 분석에서 얻는<표 2>와 매우 유사한 값을 보이는데, 이것은 4.
후속연구
[6]. CR-tree는 주메모리 환경에서 사용할 수 있는 인덱스 구조이므로 본 논문이 가정한 환경인 디스크 기반 환경에서 사용할 수 없는 한계가 있다.
참고문헌 (13)
Boncz, P. A., Manegold, S. and Kersten, M. L., 'Database Architecture Optimized for the New Bottleneck: Memory Access,' In Proceedings of the 25th VLDB, pp.54-65, 1999
Rao, J. and Ross, K A., 'Cache Conscious Indexing for Decision-Support in Main Memory,' In Proceedings of 25th International Conference on Very Large Data Bases, pp.78-89, 1999
Rao, J. and Ross, K. A., 'Making B+- Trees Cache Conscious in Main Memory,' In Proceedings of the 2000 ACM SIGMOD International Conference, pp.475-486, 2000
Chen, S., Gibbons, P. B. and Mowry, T. C., 'Improving Index Performance through Prefetching,' In Proceedings of the 2001 ACM SIGMOD International Conference, pp.235-246, 2001
Chen, S., Gibbons, P. B., Mowry, T. C. and Valentin, G., 'Fractal Prefetching B+- Trees: Optimizing Both Cache and Disk Performance,' In Proceedings of the 2002 ACM SIGMOD International Conference, pp.157-168, 2002
Kim, K., Cha, S. and Kwon, K., 'Optimizing Multi-dimensional Index Trees for Main Memory Access,' In Proceedings of the 2001 ACM SIGMOD International Conference, pp.139-150, 2001
Leutenegger, S. T, Edgington, J. M. and Lopez, M. A., 'STR: A Simple and Efficient Algorithm for R-Tree Packing,' In Proceedings of the Thirteenth International Conference on Data Engineering, pp.497-506, 1997
Guttman, A., 'R-Trees: A Dynamic Index Structure for Spatial Searching,' SIGMOD'84, Proceedings of Annual Meeting, pp.47-57, 1984
Roussopoulos, N., Kelley, S. and Vincent, F., 'Nearest Neighbor Queries,' In Proceedings of the 1995 ACM SIGMOD, pp.71-79, 1995
Kamel, I. and Faloutsos, C., 'On Packing R-trees,' in Proceedings of the 1993 ACM CIKM Conference, pp.490-499, 1993
Leutenegger, S. T. and Lopez, M. A., 'The Effect of Buffering on the Performance of R-Trees,' In Proceedings of the 14th International Conference on Data Engineering, pp.164-171, 1998
Beckmann, N., Kriegel, H.-P., Schneider, R. and Seeger, B., 'The R*-Tree; An Efficient and Robust Access Method for Points and Rectangles,' In Proceedings of the 1990 ACM SIGMOD, pp.322-331, 1990
Dongarra, J., London, K., Moore, S., Mucci, P. and Terpstra, D., 'Using PAPI for Hardware Performance Monitoring on Linux Systems,' In Proceedings of the 2nd LCI International Conference on Linux Clusters: The HPC Revolution 2001
※ AI-Helper는 부적절한 답변을 할 수 있습니다.