$\require{mediawiki-texvc}$
  • 검색어에 아래의 연산자를 사용하시면 더 정확한 검색결과를 얻을 수 있습니다.
  • 검색연산자
검색연산자 기능 검색시 예
() 우선순위가 가장 높은 연산자 예1) (나노 (기계 | machine))
공백 두 개의 검색어(식)을 모두 포함하고 있는 문서 검색 예1) (나노 기계)
예2) 나노 장영실
| 두 개의 검색어(식) 중 하나 이상 포함하고 있는 문서 검색 예1) (줄기세포 | 면역)
예2) 줄기세포 | 장영실
! NOT 이후에 있는 검색어가 포함된 문서는 제외 예1) (황금 !백금)
예2) !image
* 검색어의 *란에 0개 이상의 임의의 문자가 포함된 문서 검색 예) semi*
"" 따옴표 내의 구문과 완전히 일치하는 문서만 검색 예) "Transform and Quantization"
쳇봇 이모티콘
안녕하세요!
ScienceON 챗봇입니다.
궁금한 것은 저에게 물어봐주세요.

논문 상세정보

이동 객체 데이타베이스에서 KDB-tree의 동적 분할 정책

The Dynamic Split Policy of the KDB-Tree in Moving Objects Databases

초록

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

Abstract

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 

이 논문을 인용한 문헌 (0)

  1. 이 논문을 인용한 문헌 없음

원문보기

원문 PDF 다운로드

  • ScienceON :

원문 URL 링크

원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다. (원문복사서비스 안내 바로 가기)

상세조회 0건 원문조회 0건

DOI 인용 스타일