본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

R-tree에서 Seeded 클러스터링을 이용한 다량 삽입
Bulk Insertion Method for R-tree using Seeded Clustering

이태원   (서울대학교 전기컴퓨터공학부UU0000691  ); 문봉기   (아리조나주립대학 컴퓨터학  ); 이석호   (서울대학교 전기컴퓨터공학부UU0000691  );
  • 초록

    지구 관측 시스템(EOSDIS)나 많은 수의 클라이언트를 추적하는 이동전화 서비스 등 많은 응용에서는 지속적으로 생겨나는 대량의 복잡한 데이타들을 보관하고 인덱싱하는 것이 매우 어려운 일이다. 다차원 데이타를 효과적으로 관리하기 위해 R-tree에 기반 한 인덱스 구조가 널리 사용되어 왔다. 본 논문에서는 빠른 데이타 생성 속도를 따라잡으면서 대량 삽입을 통해 R-tree를 관리할 수 있는 seeded clustering이라는 확장성 있는 기법을 제안한다. 이 기법에서는 삽입할 대상 R-tree의 상위 k레벨의 구조를 활용하여 시드 트리를 만들어 삽입 데이타를 분류해 클러스터를 생성한다. 그리고 각 클러스터로부터 삽입 R-tree를 생성하고 이를 대상 R-tree에 한 번에 하나씩 삽입한다. 논문에서는 자세한 알고리즘과 함에 다양한 실험 결과를 보여준다. 실험 결과를 통해 seeded clustering을 이용한 대량 삽입이 기존의 대량 삽입 기법들과 비교해 삽입이나 질의 처리 모두에서 우수함을 알 수 있다.


    In many scientific and commercial applications such as Earth Observation System (EOSDIS) and mobile Phone services tracking a large number of clients, it is a daunting task to archive and index ever increasing volume of complex data that are continuously added to databases. To efficiently manage multidimensional data in scientific and data warehousing environments, R-tree based index structures have been widely used. In this paper, we propose a scalable technique called seeded clustering that allows us to maintain R-tree indexes by bulk insertion while keeping pace with high data arrival rates. Our approach uses a seed tree, which is copied from the top k levels of a target R-tree, to classify input data objects into clusters. We then build an R-tree for each of the clusters and insert the input R-trees into the target R-tree in bulk one at a time. We present detailed algorithms for the seeded clustering and bulk insertion as well as the results from our extensive experimental study. The experimental results show that the bulk insertion by seeded clustering outperforms the previously known methods in terms of insertion cost and the quality of target R-trees measured by their query performance.


  • 주제어

    대량 삽입 .   대량 연산.  

  • 참고문헌 (10)

    1. TPC-H, Transaction Processing Performance Council, accessible via URL, http://www.tpc.org/tpch/ 
    2. TIGER/Line Files, 2000 Technical Documentation U.S. Bureau of Census, Washington DC, accessible via URL http://www.census.gov/geo/www/tiger/tigerua/ua_tgr2k.html 
    3. N. Beckmann, H. P. Kriegel, R. Schneider and B. Seeger, 'The R*-tree:an efficient and robust access method for points and rectangles,' ACM SIGMOD, pp. 322-331, 1990 
    4. S. T. Leutenegger, J. M. Edgington and M. A. Lopez, 'STR:A Simple and Efficient Algorithm for R-Tree Packing,' ICDE, pp. 497-506, 1997 
    5. I. Kamel and Chrisots Faloutsos, 'On packing R-trees,' CIKM, pp. 490-499, 1993 
    6. A. Guttman, 'R-trees: a dynamic index structure for spatial searching,' ACM SIGMOD, pp. 47-57, 1984 
    7. L. Arge, K. H. Hinrichs, J. Vahrenhold and J. S. Vitter, 'Efficient Bulk Operations on Dynamic R-Trees,' Algorithmica, Vol. 33, No. 1, pp. 104-128, 2002 
    8. I. Kamel, M. Khalil and V. Kouramaijan, 'Bulk insertion in dynamic R-trees,' SDH '96, pp. 3B.31-3B.42, 1996 
    9. R. Choubey, L. Chen and E. A. Rundersteiner, 'GBI: A Generalized R-tree Bulk-Insertion Strategy,' Advances in Spatial Databases, pp. 91-108, 1997 
    10. L. Chen, R. Choubey and E. A. Rundensteiner, 'Bulkinsertions into R-trees using the small-tree-large tree approach,' ACM GIS, pp. 161-162, 1998 

 저자의 다른 논문

  • 이태원 (3)

    1. 2000 "주문형 오디오 시스템을 위한 웹 캐시 구조의 설계 및 평가" 정보과학회논문지. Journal of KIISE. 데이타베이스 27 (2): 209~215    
  • 이석호 (35)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기