초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

범위 상위-k 질의는 질의 범위 내의 다차원 데이타 중 값 애트리뷰트를 기준으로 상위 k개의 레코드를 반환하는 질의로 공간 데이타베이스와 데이타 웨어하우스에서 분석을 위해 많이 사용되는 유용한 질의 형태이다. 이 논문에서는 계층 최대 R-트리의 선택적인 탐색을 통해 범위 상위-k 질의를 효과적으로 수행하는 기법을 제시한다. 질의 결과를 포함하지 않는 단말 노드를 접근하지 않고 질의를 수행할 수 있기 때문에 적은 노드 접근으로도 질의 수행이 가능하며, 질의 범위의 크기에 관계없이 거의 일정한 성능을 보인다. 두 개의 우선순위 큐를 사용하며 질의 수행 공간을 최소화 하며, In Sorted Node 기법을 통해 기존 R-트리와 같은 팬아웃을 보장할 수 있다.

범위 상위-k 질의는 질의 범위 내의 다차원 데이타 중 값 애트리뷰트를 기준으로 상위 k개의 레코드를 반환하는 질의로 공간 데이타베이스와 데이타 웨어하우스에서 분석을 위해 많이 사용되는 유용한 질의 형태이다. 이 논문에서는 계층 최대 R-트리의 선택적인 탐색을 통해 범위 상위-k 질의를 효과적으로 수행하는 기법을 제시한다. 질의 결과를 포함하지 않는 단말 노드를 접근하지 않고 질의를 수행할 수 있기 때문에 적은 노드 접근으로도 질의 수행이 가능하며, 질의 범위의 크기에 관계없이 거의 일정한 성능을 보인다. 두 개의 우선순위 큐를 사용하며 질의 수행 공간을 최소화 하며, In Sorted Node 기법을 통해 기존 R-트리와 같은 팬아웃을 보장할 수 있다.

AI 본문요약

엑셀 다운로드 AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

• 연구 주제
• 연구 방법
• 연구 결과

문제 정의

• 이 논문에서는 계충 최대 R-트리(Hierarchical Max R-Tree, HMR-트리)를 통해 다차원 데이타를 저장하고 범위 상위-K 질의를 효율적으로 수행하는 기법올 제시한다. HMR-트리는 R-트리[4]의 각 중간 노드마다 하위 노드의 최대값을 저장하는 구조이다.
• 이 논문에서는 다차원 데이타를 계층 최대 R-트리로 구성하여 범위 상위-K 질의를 효율적으로 처리하는 기법을 제시하였다. HMR-트리는 기존 R-트리의 각 중간 노드마다 하위 노드에 대한 최대값옽 저장하는 구조이며, 범위 상위-K 질의 알고리즘에서는 질의 범위 내의 모든 단말 노드를 접근하지 않고, 우선순위 큐를 퉁해 큰 값을 갖는 데이타를 포함한 단말 노드부터 순서대로 접근 하여 질의를 처리한다.
• 이 절에서는 HMR-트리를 기반으로 효율적으로 범위 상위-k 질의를 수행하는 알고리즘을 제시한다. 알고리즘은 우선순위 큐를 통해서 수행된다.

가설 설정

• · 위의 과정을 상위 k개의 결과가 나올 때까지 반복한다.

제안 방법

• 그림 6(b)는 HMR-트리에서 차원을 변화시켜가면서 질의를 수행한 결과이다. 10만개의 데이타에 댸해 질의 범위를 30%로 하여 상위 100개를 구하는 질의를 수행하였다. 차원을 증가시켜도 기존 R-트리에 비해 항상 적은 수의 노드 접근만으로 질의 수행이 가능한 것을 알 수 있다.
• 이 논문의 구성은 다음과 같다. 2절에서 범위 상위” 질의를 수행하기 위한 자료구조인 계충 최대 R-트리와 알고리즘을 소개한 후, 3절에서 질의 수행 공간과 노드의 효율적인 구성 기법에 대해 살펴본다. 4절에서 실험 결과를 분석하고, 5절에서 결론을 맺는다.
• 그림 4는 질의 범위의 코기를 변화시켜가면서 노드 접근 횟수를 측정한 결과이다. 2차원 데이타 300만개를 HMR-트리의 여러 기법과 R-트리로 구성하여 상위 100개롤 검색하는 질의를 수행하 였다. 기존 R~트리의 경유 질의 범위내의 모든 노드를 접근하여 질의 범위 내에 속하는 모든 데이타를 읽은 후 그 중 상위 k개를 선택해야 하는 반면, HMR-트리를 사용하면 값이 큰 노드부터 차례로 읽어낼 수 있으므로 질의 범위의 크기와 상관없이 일정한 노드 접근을 보인다.
• HMR-트리의 성능을 측정하기 위해 HMR-트리의 여러 기법과 기존 R-트리에 대해 범위 상위-k 질의를 수행하고 노드 접근 횟수률 측정하였다. 실험은 펜티엄TH 1GHz, 512MB의 주기억장치를 갖는 Linux 기계에서 2~5 차원의 데이타를 임의로 생성하여 수행하였으며, 두 개의 우선순위 큐를 사용하였다.
• 그림 6(a)는 HMR-트리에서 질의 결과 크기인 k를 변화해가며 질의를 수행한 결과이다. In Sorted Node 기법의 HMR-트리를 사용했으며, 100만개의 2차원 테이타에 대해 질의 범위를 10%로 하여 질의를 수행하였다. 역시 기존 R-트리가 k값에 상관없이 항상 큰 노드 접근 횟수를 보이는 반면, HMR-트리는 k값이 작은 경우는 적은 수의 노드 접근만으로 질의 수행이 가능하며 K걊이 커짐에 따라 노드 접근 횟수가 증가하게 된다.

대상 데이터

• HMR-트리의 성능을 측정하기 위해 HMR-트리의 여러 기법과 기존 R-트리에 대해 범위 상위-k 질의를 수행하고 노드 접근 횟수률 측정하였다. 실험은 펜티엄TH 1GHz, 512MB의 주기억장치를 갖는 Linux 기계에서 2~5 차원의 데이타를 임의로 생성하여 수행하였으며, 두 개의 우선순위 큐를 사용하였다.

이론/모형

• 이 논문에서는 범위 상위-K 질의를 효율적으로 수행하기 위한 자료구조로 계층 최대 R-트리(Hierarchical Max R-Tree, HMR- 트리)를 사용한다. HMR-트리는 R-트리의 중간 노드마다 하위 노 드들에 대한 최대값을 저장한 자료구조이다.
• HMR-트리는 기존 R-트리의 각 중간 노드마다 하위 노드에 대한 최대값옽 저장하는 구조이며, 범위 상위-K 질의 알고리즘에서는 질의 범위 내의 모든 단말 노드를 접근하지 않고, 우선순위 큐를 퉁해 큰 값을 갖는 데이타를 포함한 단말 노드부터 순서대로 접근 하여 질의를 처리한다. 질의 수행 공간올 줄이기 위해 두 개의 우선순위 큐를 사용하였으며, In Sorted Node 기법을 통해 기존 R- 트리와 같은 팬아웃을 보장할 수 있다.

성능/효과

• 따라서 In Sorted Node 기법으로 구성한 HMR-트리는 기존 R-트리와 비슷한 팬아옷을 보이는 In Node 기법의 장점과, 더 적 온 수의 노드 접근으로 질의 수행이 가능한 In Entry 기법의 장점 을 절충한 기법이라 할 수 있다.
• 2차원 트리에 대해 노드 크기롤 1024 byte로 고정하였을 경우 R-트리와 HMR-트리의 In Node 기법, In Node Sorted 기법은 노드 내 각 엔트리의 크기가 20 byte인 반면, In Entry 기법은 엔트리마다 최대값을 저장해야 하므로 24 byte 만큼 이 공간이 필요하다. 따라서 기존 R-트리와 HMR-트리의 다론 기법들이 노드 내 엔트리의 수가 50개인 반면 In Entry 기법은 42개로 줄어들며, 이로 인해 예를 들어 300만개의 데이타롤 저장할 경우 기존 R-트리와 HMR-트리의 다론 기법의 높이가 4인 반면, In Entry기법은 높이가 5로 늘어나게 된다.
• 만일 모든 엔트리가 질의 범위에 완전히 포함된다면 우선순위 큐의 상위 k개의 엔트리에는 적어도 k개 이상의 결과가 포함되어 있다는 것을 보장할 수 있다. 큐에서 하나의 엔트리를 뽑는 경우를 생각해보자.
• 실험에 따르면 제안한 기법이 기존 R-트리를 사용하여 범위 상위-K 질의를 수행하는 경우에 비해 항상 좋은 성능을 보였으며, 질의 범위의 크기에 관계없이 노드 접근 횟수가 거의 일정하였다. k 값이 작은 경우에는 기존 R-트리예 비해 15%정도의 노드 접근 만으로 질의를 처리할 수 있었으며, k 값이 큰 경우에도 R-트리와 비슷한 성능을 유지하였다.
• HMR-트리는 각 기법예 따라 노드 접근 횟수의 차이가 있다. 여러 기법 중에서 In Entry 기법과 In Node Sorted 기법이 거의 비숫하게 좋은 성능을 보이며, In Node 기법온 두 기법보다는 전반적으로 많은 노드 접근 횟수를 보안다. 이는 In Node 기법의 경우 자식 노드의 최대값을 얻기 위햬 자식 노드룔 방문하여야 하기 때문이다.

후속연구

• 따라서 질의 범위에 완전히 포함되는 엔트리와 질의 범위에 일 부만 겹치는 엔트리를 위한 우선순위 큐를 각각 따로 유지한다면, 질의 범위에 완전히 포함되는 엔트리를 위한 큐는 그 크기를 k로 제한할 수 있올 것이다. 질의 범위에 겹치는 엔트리 중, 질의 범위 에 일부만 겹치는 엔트리들은 질의 범위의 가장자리에 있는 노드 뿐이며, 대부분의 엔트리가 질의 범위 내에 완전히 포함되므로 질의 수행 공간을 크게 줄일 수 있다.

본문요약 정보가 도움이 되었나요? 예 아니오 제출

이 논문을 인용한 문헌

더보기