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

논문 상세정보

이동 객체 데이타베이스에서 KDB-tree의 동적 분할 정책
The Dynamic Split Policy of the KDB-Tree in Moving Objects Databases

임덕성   (영진전문대학 컴퓨터정보계열UU0000978  ); 이창헌   (부산정보과학고등학교  ); 홍봉희   (부산대학교 공과대학 컴퓨터공학과UU0000613  );
  • 초록

    시간의 흐름에 따라 누적되는 대용량의 과거 위치를 관리하는 이동 객체 데이타베이스에서 이동 객체의 과거 위치를 효율적으로 검색하기 위해서는 이동 객체의 특성을 고려한 색인 구조가 필요하다. 그러나, 영역 질의 성능이 우수한 다차원 색인인 KDB-tree를 이동 객체 데이타베이스에 적용할 경우 시간 도메인이 증가하는 이동 객체 데이타베이스의 특성으로 인해 공간 도메인 가중 분할이 발생한다. 공간 도메인 가중 분할은 하나의 노드가 차지하는 MBR의 공간 영역이 분할 횟수에 반비례하게 감소되어 시공 간 영역 질의 처리시 색인의 검색 비용을 증가시키는 문제가 있다. 이 논문에서는 이동 객체 데이타베이스에서 시공간 영역 질의를 효율적으로 처리하기 위한 KDB-tree의 동적 분할 정책을 제안한다. 동적 분할 정책은 공간 우선 분할 방법을 적용하는 분할 도메인 선정 방법과 포인터 페이지에서 공간 활용도를 최대화시킬 수 있는 최근 시간 분할 정책, 영역 페이지에서 적용되는 최후 시간 분할 정책으로 구성된다. 제안한 동적 분할 정책의 성능을 평가하기 위해 3DR-tree, MV3R-tree, KDB-tree와의 성능을 비교한다. 영역 질의를 위한 성능 평가에서 동적 분할 정책을 적용한 MKDB-tree는 기존 색인에 비해 평균 30% 이상의 노드 접근 회수를 감소시킨다.


    Moving object databases manage a large amount of past location data which are accumulated as the time goes. To retrieve fast the past location of moving objects, we need index structures which consider features of moving objects. The KDB-tree has a good performance in processing range queries. Although we use the KDB-tree as an index structure for moving object databases, there has an over-split problem in the spatial domain since the feature of moving object databases is to increase the time domain. Because the over-split problem reduces spatial regions in the MBR of nodes inverse proportion to the number of splits, there has a problem that the cost for processing spatial-temporal range queries is increased. In this paper, we propose the dynamic split strategy of the KDB-tree to process efficiently the spatial-temporal range queries. The dynamic split strategy uses the space priority splitting method for choosing the split domain, the recent time splitting policy for splitting a point page to maximize the space utilization, and the last division policy for splitting a region page. We compare the performance of proposed dynamic split strategy with the 3DR-tree, the MV3R-tree, and the KDB-tree. In our performance study for range queries, the number of node access in the MKDB-tree is average 30% less than compared index structures.


  • 주제어

    이동 객체 데이터베이스 .   이동 객체 색인 .   동적 분할.  

  • 참고문헌 (12)

    1. S. Saltenis, C.S.Jensen, S.T.Leutenegger, and M.A. Lopez, 'Indexing the Positions of Continuously Moving Objects,' Int. Conf. ACM SIGMOD, pp. 331-342, 2000 
    2. G.Kollios, D. Gunopulos, and V. J. Tsotras, 'On Indexing Mobile Objects,' Int. conf. PODS, pp. 261-272, 1999 
    3. E.Stefanakis, Y.Theodoridis, Timos Sellis, 'Point Representation of Spatial Objects and Query Window Extension: A New Technique for Spatial Access Methods,' International Journal of Geographical Information Science vol.11, no.6, pp. 529-554, 1997 
    4. Volker Gaede, Oliver Gunther, 'Multidimensional Access Methods,' ACM Computer Survey, vol. 30, no. 2, pp. 170-231, 1998 
    5. Y.Tao, D.Papadias, 'MV3R-tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries,' Int. conf. VLDB, pp. 431-440, 2001 
    6. Ratko Orlandic, Byunggu Yu, 'Implementing KDB trees to Support High-Dimensional Data,' Int. conf. IDEAS, pp. 58-67, 2001 
    7. J,T. Robinson, 'The K-D-B Tree: A Search Structure For Large Multidimensional Dynamic Indexes,' Int. Conf. ACM SIGMOD, pp. 10-18, 1981 
    8. M. Freeston, 'A General Solution of the N-dimensional B tree Problem,' Int. Conf. ACM SIGMOD, pp. 80-91, 1995 
    9. A. Henrich, H.-S. Six and P. Widmayer, 'The LSD Tree: Spatial Access to Multidimensional Point and Non-Point Objects,' Int. conf. VLDB, pp. 45-53, 1989 
    10. B. Seeger and H.P. Kriegel, 'The Buddy tree: An Efficient and Robust Access Method for Spatial Data Base Systems,' Int. conf. VLDB, pp. 590-601, 1990 
    11. Y.Theodoridis, J,R.O. Silva, and M.A. Nascimento, 'On the Generation of Spatio-Temporal Datasets,' Int. conf. SSD, LNCS 1651, Springer, pp. 147-164, 1999 
    12. D.Pfoser, C. S.Jensen, Y. Theodoridis, 'Novel Approaches in Query Processing for Moving Object Trajectories,' Int. conf. VLDB, pp. 395-406, 2000 

 저자의 다른 논문

  • 홍봉희 (67)

    1. 1995 "수출입 컨테이너 장치장 배정을 위한 소프트웨어의 개발" 經營 科學 = Korean management science review 12 (3): 1~15    
    2. 1995 "객체 지향 규칙 기반 지형 질의어의 설계 및 구현" 정보과학회지 = Communications of the Korean Institute of Information Scientists and Engineers 13 (3): 30~47    
    3. 1998 "DBMS Independent GIS 기본 소프트웨어 기술 개발과제" 정보과학회지 = Communications of the Korean Institute of Information Scientists and Engineers 16 (3): 16~22    
    4. 1999 "상호운용을 지원하는 코바 기반 공간 데이터 제공자의 설계 및 구현" 개방형GIS연구회 논문지 = Journal of the Korea open geographic information systems research society 1 (2): 33~46    
    5. 1999 "CORBA를 이용한 OpenGIS 기반 미들웨어 구현" 개방형GIS연구회 논문지 = Journal of the Korea open geographic information systems research society 1 (1): 19~28    
    6. 1999 "벡터 사분트리를 이용한 병렬 공간 조인" 정보과학회논문지. Journal of KISS (b):software and applications. B 26 (1): 25~39    
    7. 1999 "객체지향 공간 뷰의 설계 및 구현" 정보과학회논문지. Journal of KISS (b):software and applications. B 26 (2): 306~320    
    8. 1999 "단일/다중할당 공간 색인에서 병렬 공간 조인의 성능평가" 정보과학회논문지. Journal of KISS (b):software and applications. B 26 (6): 763~779    
    9. 1999 "분산된 지리정보시스템에서 새로운 잠금기법을 이용한 중복된 공간 데이터의 변경 전파" 정보과학회논문지. Journal of KISS (b):software and applications. B 26 (9): 1061~1072    
    10. 2000 "타일-기반 수치지도를 이용한 동시 합병 처리기 설계 및 구현" 개방형GIS연구회 논문지 = Journal of the Korea open geographic information systems research society 2 (1): 17~27    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

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

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

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

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

이 논문과 함께 이용한 콘텐츠
이 논문과 함께 출판된 논문 + 더보기