- 버킷 정렬을 이용한 향상된 R-tree 대량적재 기법
- ㆍ 저자명
- 김남우,이미영,Kim. Nam-Woo,Lee. Mi-Young
- ㆍ 간행물명
- 정보과학회논문지. Journal of KIISE. 데이타베이스
- ㆍ 권/호정보
- 2012년|39권 1호|pp.72-77 (6 pages)
- ㆍ 발행정보
- 한국정보과학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
위치 기반의 모바일 서비스, GPS(Global Positioning System), RFID(Radio Frequency IDentification) 등의 사용이 폭발적으로 증가하여, 위치 및 공간 데이터가 기하급수적으로 늘어나고 있다. 대규모 공간 데이터를 빠르게 검색하기 위해 대표적으로 R-tree 기반의 인덱스 구조를 사용한다. 대량의 공간 데이터로부터 효율적으로 R-tree 인덱스를 생성하기 위한 방법으로 STR(Sort-Tile-Recursive) 기법이 널리 알려져 있다. STR 기법은 공간 데이터를 정렬하는 부분에서 대부분의 시간을 소모한다. 정렬 시간 단축을 위해 본 논문에서는 버킷 정렬 기법을 이용하여 공간 데이터를 정렬하고, R-tree 기반의 인덱스를 생성하는 기법을 제안한다. 제안 기법은 STR 기법의 Sort-Tile 부분을 버킷 정렬로 변경하여 인덱스 생성 시간을 단축한다. 실험결과를 통해 제안 기법이 STR 기법보다 7배 향상되었고, 이를 그래픽 처리 장치에서 병렬화하여 19배 가량 향상되었음을 확인하였다.
Due to the explosive growth in use of LBS based mobile services, Global Positioning System (GPS) and Radio Frequency IDentification (RFID), the location and spatial data are growing exponentially. The index structure based on R tree is typically used in order to retrieve a large spatial data quickly. The Sort-Tile-Recursive (STR) method that is an efficient way to create R-tree index from large amounts of spatial data is widely known. The most time consuming part of STR method is to sort spatial data. To reduce sorting time, this paper proposes a method for creating an R-tree index which uses a bucket sort method to sort spatial data. The proposed method replaces a Sort Tile to a bucket sort to reduce indexing time. Experimental results show that the proposed method enhances the performance more than 7 times compared to STR method and it enhances the performance more than 19 times by using Graphic Processing Unit (GPU).