데이터베이스 R-tree의 종류별 개요, 기능, 특성분석 및 활용도 조사

데이터베이스 R-tree의 종류별 개요, 기능, 특성분석 및 활용도 조사

[데이터베이스] R-tree의 종류별 개요, 기능, 특성분석 및 활용도 조사.doc

목차 기본 R-tree 1. R-tree 1) Introduction 2) Definition 3) Operation 4) Discussion 2. R+-tree 3. R*-tree 기본 R-tree의 활용도 R-tree를 기반으로 시공간 색인에 쓰이는 tree 4. HR-tree, HR+-tree 5. MV3R-tree 6. TIR-tree R-tree를 기반으로 시공간 색인에 쓰이는 tree의 활용도 R-tree를 기반으로 궤적색인에 쓰이는 tree 7. STR-tree 8. TPR-tree 9. MPR-tree R-tree를 기반으로 궤적색인에 쓰이는 tree의 활용도 참고문헌 본문 * 각 chapter별 세부사항은 1. R-tree의 세부사항 순서와 동일 기본 R-tree 1. R-tree 1) Introduction Spatial data를 효율적으로 처리하기 위해 Database System은 공간 위치에 따라 data items을 신속하게 가져오는 것을 도와줄 index mechanism이 필요하다. 그러나 기존의 indexing methods는 다차원 공간에 위치하는 non-zero size의 data object에 적합하지 않다. 이러한 필요를 충족시켜 줄 수 있는 것이 R-tree라고 불리는 dynamic index structure (삽입과 삭제가 탐색과 함께 서로 사용되고 주기적인 재구성이 필요하지 않은 구조) 이다. B+ tree를 2차원이상으로 확장한 tree이며, 각 node와 객체는 MBR(Minimum Bounding Region) 또는 MBB(Minimum Bounding Box)에 의해 표현된다. tree는 MBR들간의 포함관계로 표현된다. 최대X, * 참고 : MBR이란? 최대Y 선들과 기하학적으로 인코드된 불규칙 다각형들은 X Y평면 최소X, 에서 객체의 끝점에 닿기 위해 직교 사각형으로 나타낸다. 최소Y 2) Definition Multi-dimensional point data를 처리하기 위해 R-tree구조는 non-zero size Nodes를 가 진 spatial data object들을 indexing하는데 유용하다. 참고문헌 A. Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 dblp Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 Beckmann, N., Kriegel H., Schneider, R. and Seeger, B., 1990, The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. ACM SIGMOND, 322-331. 조형주, 정진완, 시공간 질의를 위한 인덱싱 기법, 한국정보과학회 2002 한국데이터베이스 학술대회 논문집, 2002년 5월 18권 2호, pp.93-100. 최미나, 문정욱, 이기준, STR-Tree : 계층 공간 분할을 이용한 다차원 정적 데이터 색인 , 한국정보과학회 춘계학술발표대회, 29권 1호, pp64-66, April 2002 전봉기, 홍봉희. "연속적으로 이동하는 이동체의 색인을 위한 시간 기반 R-tree의 설계 및 구현" 데이터베이스 연구회지, 18권 4호, 2002년 12월 전봉기, 임덕성, 홍보희. "이동체 데이터 베이스를 위한 색인 기법" 데이터베이스 연구회지, 18권 4호, 2002년 12월 http://210.115.167.72/www/cgi-bin/data/spatialDB2003/5 http://210.115.167.72/www/cgi-bin/data/spatialDB2003/R-TREE%28chapter6%29.ppt http://www.cebt.re.kr/results/ChinWanChung/kdbc03a.doc http://www.nca.or.kr/homepage/main/data/journal.nsf/0/027de63127d462bac9256dc10016d2e0/$FILE/_q60o5u4dolo8rlp0hmfmh3ede508sfk8hm7h13geo54oj4chp_.pdf http://dblab.chungbuk.ac.kr/spatialDB2003/db/ http://210.115.167.72/www/cgi-bin/data/spatialDB2003_A/ http://pike.ewha.ac.kr/main/download/seminars/ 키워드 특성분석, 개요, 기능, 분석, 조사, 종류별