초록

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

최근에는 물류 및 수송 관리, 교통 정보 서비스 등과 같은 위치 기반 서비스의 요구가 증대되고 있다. 위치 기반 서비스에서 클라이언트들의 빈번한 보고 데이터를 처리하기 위해서는 서버에서 메인 메모리 DBMS를 유지하는 것이 필요하다. 그러나 기존 연구에서는 이러한 이동체 데이터베이스를 위한 메인 메모리 색인이 없으므로 이에 적합한 색인이 필요하다. 다차원 색인으로 영역 질의에 뛰어난 성능을 보이는 색인으로 R-tree가 있는데, 이는 디스크 환경을 고려하여 설계되었기 때문에 메인 메모리에서는 효율을 보장하지 못한다. 이 논문에서는 R-tree를 변형하여 이동체 데이터베이스를 위한 메인 메모리 색인을 제시한다. 이 논문에서 새로 제시한 성장 노드 구조와 동적 재구성 및 큰 영역을 가진 노드 분할 정책은 영역 질의의 성능을 향상시킨다. 실험은 제안한 색인이 이동체 데이터베이스를 위한 적합한 메인 메모리 구조임을 보여준다.

최근에는 물류 및 수송 관리, 교통 정보 서비스 등과 같은 위치 기반 서비스의 요구가 증대되고 있다. 위치 기반 서비스에서 클라이언트들의 빈번한 보고 데이터를 처리하기 위해서는 서버에서 메인 메모리 DBMS를 유지하는 것이 필요하다. 그러나 기존 연구에서는 이러한 이동체 데이터베이스를 위한 메인 메모리 색인이 없으므로 이에 적합한 색인이 필요하다. 다차원 색인으로 영역 질의에 뛰어난 성능을 보이는 색인으로 R-tree가 있는데, 이는 디스크 환경을 고려하여 설계되었기 때문에 메인 메모리에서는 효율을 보장하지 못한다. 이 논문에서는 R-tree를 변형하여 이동체 데이터베이스를 위한 메인 메모리 색인을 제시한다. 이 논문에서 새로 제시한 성장 노드 구조와 동적 재구성 및 큰 영역을 가진 노드 분할 정책은 영역 질의의 성능을 향상시킨다. 실험은 제안한 색인이 이동체 데이터베이스를 위한 적합한 메인 메모리 구조임을 보여준다.

AI 본문요약

엑셀 다운로드 AI-Helper

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

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

문제 정의

• 문제 정의에서 언급했듯이, 기존의 R-tree는 노드 간의 중 첩이 심하기 때문에 이는 검색 성능올 저하시킨다. 따라서 이 논문에서는 노드 간의 중첩올 감소시키기 위해서 동적 재구성 정책을 제안한다.
• 문제 정의에서 언급했듯이, 메인 메모리 기반에서는 노드의 크기에 제약이 없기 때문에, 이 논문에서는 단말(Leaf) 노드 레벨에서 성장 노드(Growing Node)를 제안한다. 성장 노드란 노드의 용량이 가득 찼을 때, 해당 노드가 분할할 이유가 없다면, 분할하지 않고 계속 성장하는 노드를 말한다.
• 이 논문에서는 메인 메모리의 특성을 이용하여 분할 연기로 인한 삽입 성능의 향상을 위하여 성장 노드를 제안하고, 노드 간의 중첩을 줄이기 위한 방법으로 동적 재구성 정책과 사장 공간올 줄이기 위한 방법으로 큰 영역을 가진 노드 분할 정책을 제안한다. 제안 방법은 이동체 데이터베이스 환경에서 뼈■른 영역 질의를 제공한다.
• 이 논문에서는 이동체 데이터베이스를 위한 메인 메모리 색인을 제안하였다. 제안된 색인은 메인 메모리에 적채한 기존의 R-tree와 실험을 통해서 비교하였다.
• 이 논문에서는 이러한 큰 영역을 가진 노드를 분할함으로써 사장 공간올 줄이고자 한다. 큰 영역을 가친 노드 분할 정책은 중첩이 EOR이하 일 때, 그리고 영역의 크기가 EA R이상 알 때 수행된다.
• 서버에서는 클라이언트의 위치 정보를 저장하고, 클라이언트에서 질의 요청이 오면, 저장하고 있는 위치 정보를 이용하여 응답하는 환경을 대상으로 하고 있다. 이 논문에서는 질의 중에서 가장 일반적인 영역 질의(Range Query)의 성능 향상을 목적으로 하고 있다.

제안 방법

• 미리 수행해 본 실험에서의 결과를 토대로 EOR이 0.4 이상일 때를 노드 간의 중첩이 심하다고 판단하는 기준으로 삼았고, 노드 간의 중첩이 심하지 않을 때, EAR이 3 이상인 노드를, 큰 영역을 가진 노드라고 판단하는 기준으로 삼았다.
• 제안 색인을 평가하기 위해서 다음과 같은 삽입과 검색 데이터를 사용하여 검색 시간과 검색 시 비교하는 엔트리 수를 측정하였다. 삽입은 50만 개(1000*500: 1000개의 이동체가 500번 보고)의 데이터를 가지고 수행하였고 검색은 전체 영역의 5%, 10%, 20%의 크기를 가진 1000개의 영역 질의 (Range Query'를 수행하였다.
• 이 논문에서는 이동체가 주기적으로 자신의 위치 정보와 필요시에 질의 정보를 서버로 전송한다. 서버에서는 클라이언트의 위치 정보를 저장하고, 클라이언트에서 질의 요청이 오면, 저장하고 있는 위치 정보를 이용하여 응답하는 환경을 대상으로 하고 있다.
• 이 논문에서는 메인 메모리의 특성을 이용하여 분할 연기로 인한 삽입 성능의 향상을 위하여 성장 노드를 제안하고, 노드 간의 중첩을 줄이기 위한 방법으로 동적 재구성 정책과 사장 공간올 줄이기 위한 방법으로 큰 영역을 가진 노드 분할 정책을 제안한다. 제안 방법은 이동체 데이터베이스 환경에서 뼈■른 영역 질의를 제공한다.
• 제안 색인을 평가하기 위해서 다음과 같은 삽입과 검색 데이터를 사용하여 검색 시간과 검색 시 비교하는 엔트리 수를 측정하였다. 삽입은 50만 개(1000*500: 1000개의 이동체가 500번 보고)의 데이터를 가지고 수행하였고 검색은 전체 영역의 5%, 10%, 20%의 크기를 가진 1000개의 영역 질의 (Range Query'를 수행하였다.

데이터처리

• 이 논문에서는 이동체 데이터베이스를 위한 메인 메모리 색인을 제안하였다. 제안된 색인은 메인 메모리에 적채한 기존의 R-tree와 실험을 통해서 비교하였다. 실험에서, 제안된 색인은 기존 색인에 비해 삽입 성능을 유지하는 반면에 영역 질의 시에 검색 성능의 향상을 가져왔다.

성능/효과

• 같은 레벨 노드들의 평균 크기의 2배, 3배, 4배, 5배, 10배로 바꾸어 가면서 실험한 결과 3배, 즉 EAR이 3일 때, 가장 좋은 성능이 나타났다.
• 넷째, 영역의 크기가 같은 레벨에 있는 다른 노드들에 비해서 아주 큰 노드는 검색 성능을 저하시키는 요인이 된다. 아주 큰 크기를 가진 노드들은 많은 사장 공간(dead space)을 유발할 가능성이 크기 때문에 영역 질의 시에 많이 접근됨으로써 성능 저하의 요인이 된다.
• 노드 간의 중첩 비율을 30%, 40%, 50%, 60%로 바꾸어 가면서 실험한 결과 EORo] 40%, 즉 0.4일 때 가장 좋은 성능이 나타났다.
• 둘째, R-tree는 삽입 순서(insertion order)에 의해 영향을 받기 때문에, 색인의 성능이 나빠지는 결과를 초래할 수 있다. 기존의 R*-tree에서는 재삽입 전략을 사용하지만, CPU Cycle에 따른 전체 수행 시간을 줄이자는 메인 메모리 구조의 목표에는 R*-tree는 적합하지 않다.
• 따라서 성장 노드는 단말 노드에서만 사용한다. 성장 노드를 사용하으로써, 분할 연기와 비단말(Non-Leaf) 노드에서의 엔트리 수 감소로 인한 삽입 성능의 향상을 가져온다.
• 셋째, 노드 간의 심한 중첩(overlap)은 색인의 검색 성능에 영향을 준다. 즉 노드 간의 심한 중첩은 색인의 검색 성능을 저하시키는 데 결정적인 요인으로 작용한다.
• 그림 3, 4에서 보는 바와 같이, 검색 시간과 검색 시 비교하는 엔트리 수가 전체적으로 5%~20% 정도 감소하는 것을 알 수 있다. 실험 결과에서 보듯이, 제안한 동적 재구성 정 책으로 인한 노드 간의 중첩 감소와 큰 영역을 가진 노드 분할 정책으로 인한 사장 공간의 감소로 인하여 검색 성능의 향상올 가져온다.
• 제안된 색인은 메인 메모리에 적채한 기존의 R-tree와 실험을 통해서 비교하였다. 실험에서, 제안된 색인은 기존 색인에 비해 삽입 성능을 유지하는 반면에 영역 질의 시에 검색 성능의 향상을 가져왔다.
• 첫째, R-tree를 메인 메모리 기반 색인 구조로 사용할 때, 노드를 분할하는 기준이 메인 메모리의 특성을 고려하지 않고 있다. 디스크 기반 색인의 경우에는 디스크 I/O 회수의 최소화를 위해 노드의 크기를 맞추기 위해 분할하지만, 메인 메모리 기반에서는 노드의 크기에 아무런 제약이 없다.

후속연구

• 실험에서 본 바와 같이 검색 성능을 향상시키기 위해서는 노드 간의 중첩올 줄이고, 딶은 사장 공간을 유발할 가능성이 높은, 아주 큰 영역을 가진 노드의 크기를 줄이는 방법이 필요하다.

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

이 논문을 인용한 문헌

더보기