시간의 흐름에 따라 누적되는 대용량의 과거 위치를 관리하는 이동 객체 데이타베이스에서 이동 객체의 과거 위치를 효율적으로 검색하기 위해서는 이동 객체의 특성을 고려한 색인 구조가 필요하다. 그러나, 영역 질의 성능이 우수한 다차원 색인인 KDB-tree를 이동 객체 데이타베이스에 적용할 경우 시간 도메인이 증가하는 이동 객체 데이타베이스의 특성으로 인해 공간 도메인 가중 분할이 발생한다. 공간 도메인 가중 분할은 하나의 노드가 차지하는 MBR의 공간 영역이 분할 횟수에 반비례하게 감소되어 시공 간 영역 질의 처리시 색인의 검색 비용을 증가시키는 문제가 있다. 이 논문에서는 이동 객체 데이타베이스에서 시공간 영역 질의를 효율적으로 처리하기 위한 KDB-tree의 동적 분할 정책을 제안한다. 동적 분할 정책은 공간 우선 분할 방법을 적용하는 분할 도메인 선정 방법과 포인터 페이지에서 공간 활용도를 최대화시킬 수 있는 최근 시간 분할 정책, 영역 페이지에서 적용되는 최후 시간 분할 정책으로 구성된다. 제안한 동적 분할 정책의 성능을 평가하기 위해 3DR-tree, MV3R-tree, KDB-tree와의 성능을 비교한다. 영역 질의를 위한 성능 평가에서 동적 분할 정책을 적용한 MKDB-tree는 기존 색인에 비해 평균 30% 이상의 노드 접근 회수를 감소시킨다.
시간의 흐름에 따라 누적되는 대용량의 과거 위치를 관리하는 이동 객체 데이타베이스에서 이동 객체의 과거 위치를 효율적으로 검색하기 위해서는 이동 객체의 특성을 고려한 색인 구조가 필요하다. 그러나, 영역 질의 성능이 우수한 다차원 색인인 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. Altho...
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.
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.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
이 논문에서는 시공간에서의 이동 객체의 과거 위치 데이타를 검색하기 위해 KDB-tr沃를 사용할 경우 이동 객체의 특성으로 인하여 발생하는 KDB-tree의 문제점을 기술하고, 이를 해결하여 색인의 검색 성능을 향상시 키기 위해 변경된 분할 정책들을 제안하였다. 우선 포인 트페이지 분할 방식의 문제를 해결하기 위해 포인트페 이지의 분할 도메인 선정 방법을 분류하고 시공간에서 이동 객체 색인에 효과적인 공간 우선 분할 기법과 분 할 시점 선정 방법을 제안하였다.
이 논문에서는 이동 객체의 과거 위치 검색을 효율적으로 처리하기 위해 시공간에서 이동 객체의 각 도메인 특성을 고려한 분할 방법을 제안한다. 이를 위해 분할 도메인 선정 방법을 순환적 방법, 시간 도메인 가중 분 할 방법, 긴 도메인 분할 방법, 공간 우선 분할 방법으로 분류하고, 시공간에서 이동 객체 색인에 적합한 공간 우선 분할 기법과 최근 시간 분할 기법을 제안한다.
이 논문에서 이동 객체의 위치는 보고시점 t에서 시공간 위치정보(x, y, t)로 서 모델링된다. 이동 객체는 일정 시간 간격(주기 T)내에 평균적으로 주기당 보고 횟수(T泡叫腿)만큼의 위치를 보고한다. 이와 같은 이동 객체 모델링에서 이동 객체의 과거 위치를 시공간의한 점으로 저장하기 때문에 점과 점사이의 이동 경로의 표현은 선형 보간법에 의해 표현 된다고 가정한다.
가설 설정
이동 객체는 일정 시간 간격(주기 T)내에 평균적으로 주기당 보고 횟수(T泡叫腿)만큼의 위치를 보고한다. 이와 같은 이동 객체 모델링에서 이동 객체의 과거 위치를 시공간의한 점으로 저장하기 때문에 점과 점사이의 이동 경로의 표현은 선형 보간법에 의해 표현 된다고 가정한다.
제안 방법
공간 우선 분할 기법에서 분할시점을 선정하기 위해 밀집 지역 밀도에 따른 성능을 분석한다. 그림 14는 이동 객체의 수(1000, 2000, 5000, 10000)에 따른 4가지 데 이타셑에 대한 밀집 지역 밀도(DRD)에 따른 영역 질의 성능을 비교한 그래프이다.
그림 14는 이동 객체의 수(1000, 2000, 5000, 10000)에 따른 4가지 데 이타셑에 대한 밀집 지역 밀도(DRD)에 따른 영역 질의 성능을 비교한 그래프이다. 그리고 노드의 크기를 512, 1024, 2048Byte로 달리하면서 실험을 하였다. 그 결과 밀집 지역 밀도가 작을수록 좋은 성능을 보이고 있다.
시공간 영역 질의(Spatio-temporal range Query)의 성능을 비교하기 위해 3가지 종류의 질의 영역을 이용하여 실험한다. 시공간 영역 질의는 시간 차원을 공간의 다른 차원으로 간주하여 처리한다[11, 12].
이동 객체의 대표적인 질의로서 특정 시간이나 특정 지역 안에 있는 이동 객체를 검색하기 위한 시공간 영역 질의가 있다. 시공간 영역 질의를 처리하기 위해 이 논문에서는 이동 객체의 위치데이타를 시공간 상에서의 점으로 모델링하고, 두 점사이의 이동 객체 검색은 연속 된 두 점 사이의 선형 보간법을 이용하여 색인 하는 방법을 기반으로 한다[2, 3]. 점으로 모델링된 데이타를 효 율적으로 검색하기 위해서는 SAM(Spatial Access Method)보다는 PAM(Point Access Method)을 사용하여 색인 하는 방법이 효율적이다[4, 5].
그리고 포인트페이지 의 분할 시 공간 도메인인 X, y도메인으로 분할 할 경우에는 기존의 방법을 사용하고 시간 도메인으로 분할 을 할 경우에는 분할로 인해 생성되는 결과 포인트페이 지를 시간 도메인 값이 가장 큰 데이타와 나머지 데이 타들로 분할하여 과거의 영역이 되는 포인트페이지의 엔트리 수가 M이 되게 하는 최근 시간 분할 기법을 사 용한다. 영역페이지 분할 정책으로 공간 분할 시에는 FD분할을 사용하고 시간 분할을 할 때는 이 논문에서 제안한 LD분할을 사용하여 시공간에서의 시간 도메인 을 고려한 영역페이지 분할 정책을 제안하였다.
이 논문에서는 시공간에서의 이동 객체의 과거 위치 데이타를 검색하기 위해 KDB-tr沃를 사용할 경우 이동 객체의 특성으로 인하여 발생하는 KDB-tree의 문제점을 기술하고, 이를 해결하여 색인의 검색 성능을 향상시 키기 위해 변경된 분할 정책들을 제안하였다. 우선 포인 트페이지 분할 방식의 문제를 해결하기 위해 포인트페 이지의 분할 도메인 선정 방법을 분류하고 시공간에서 이동 객체 색인에 효과적인 공간 우선 분할 기법과 분 할 시점 선정 방법을 제안하였다. 그리고 포인트페이지 의 분할 시 공간 도메인인 X, y도메인으로 분할 할 경우에는 기존의 방법을 사용하고 시간 도메인으로 분할 을 할 경우에는 분할로 인해 생성되는 결과 포인트페이 지를 시간 도메인 값이 가장 큰 데이타와 나머지 데이 타들로 분할하여 과거의 영역이 되는 포인트페이지의 엔트리 수가 M이 되게 하는 최근 시간 분할 기법을 사 용한다.
이 논문에서는 3차원 시공간을 대상으로 한 이동 객 체 데이타를 색인 하는데 있어서 MV3R-tree, 3D- Rtree, 기존의 분할 정책을 사용하는 KDB-tree와 이 논문에서 제안하는 분할 정책을 사용하는 변경된 K①B-tree(MK①B-tree)의 색인 구축 성능과 질의 처리 성능을 평가한다. 실험 환경으로는 1.
영역 페이지의 분할 정책에서 분할될 영역 페이지 가 공간 축으로 분할된 엔트리를 가질 경우 FD분할이 효율적이지만, 시간 축 엔트리로 구성될 경우 FD분할은 성능 저하를 초래한다. 이 논문에서는 영역 페이지 분할 시 공간 우선 분할 기법에서 공간 도메인으로 분할 할 경우 기존의 FD 분할을 사용하고 시간 도메인으로 분 할 할 경우에는 LD분할을 사용한다.
포인트페이지에서 시간 도메인 t로 분할 할 경우 균 등 분할 방법을 적용하면 분할된 아래 영역(t 도메인올 기준으로에는 추가적인 데이타의 삽입이 발생하지 않아 공간활용도가 떨어져 색인의 크기를 증가시키는 단점이 있다. 이 문제를 해결하는 방법으로 이 논문에서는 포인 트페이지 분할시 시공간 도메인 중에서 t도메인으로 분 할 할 때 가장 최근 시간을 가진 데이타와 나머지 데이 타들로 분할하는 최근 시간 분할 기법을 제안한다.
이 실험에서는 이동 객체의 데이타의 삽입에 따른 색 인 성능 비교 평가를 위해 구축된 색인의 공간활용도 및 생성된 노드 수를 비교한다. 노드 크기는 1024byte 이고, 4가지 색인의 비단말노드 (MBB:24byte, RRN: 4byte)의 엔트리 수는 36, 단말 노드의 경우 3DR-tree 는 MBB, Line ID 로 구성되므로 엔트리수가 36, KDB-tree, MKDB-tree, MV3R-tree는 Point, Point ID로 구성되므로 엔트리수가 64이다.
이 절에서는 3차원 시공간의 X, y, t도메인에서 이동 객체의 위치 정보가 삽입되어 분할이 발생하는 경우 분 할 도메인 선정시 시간 도메인의 선형적인 증가를 고려한 분할 도메인 선정 방법을 분류하고 기존 방법에서의 문제점을 분석한다.
이 논문에서는 이동 객체의 과거 위치 검색을 효율적으로 처리하기 위해 시공간에서 이동 객체의 각 도메인 특성을 고려한 분할 방법을 제안한다. 이를 위해 분할 도메인 선정 방법을 순환적 방법, 시간 도메인 가중 분 할 방법, 긴 도메인 분할 방법, 공간 우선 분할 방법으로 분류하고, 시공간에서 이동 객체 색인에 적합한 공간 우선 분할 기법과 최근 시간 분할 기법을 제안한다. 이 논문의 구성은 다음과 같다.
이동 객체가 주기적 패턴을 가질 경우 주기 T동안 이동한 위치를 공간 평면으로 투영한 뒤 공간 평면에서 분할할 경우 분할된 영역이 공간적으로 너무 작아지는 단점이 있다. 이를 해결하기 위해 이 논문에서는 한 주기 동안 보고된 위치의 평균 공간 영역을 정의하고 평균 공간 영역의 비율에 따라 분할 시점을 선정하는 방법을 사용 한다.
대상 데이터
따라서 실험에서 질의 영역은 데이타 세트의 전체 시공간 도메인을 정규화하여 전체 시공간 영역의 5%, 10%, 20% 크기의 질의 집합을 구성한다. 각 질의 집합의 개수는 1000개이다. 검색 성능은 각 질의 집합의 검색 시 노드 접근 회 수를 누적하여 비교한다.
이 논문에서는 3차원 시공간을 대상으로 한 이동 객 체 데이타를 색인 하는데 있어서 MV3R-tree, 3D- Rtree, 기존의 분할 정책을 사용하는 KDB-tree와 이 논문에서 제안하는 분할 정책을 사용하는 변경된 K①B-tree(MK①B-tree)의 색인 구축 성능과 질의 처리 성능을 평가한다. 실험 환경으로는 1.7GMHZ의 CPU와 512Mbyte의 메모리를 가진 Linux 환경의 Personal Computer를 사용한다.
이론/모형
검색 성능은 각 질의 집합의 검색 시 노드 접근 회 수를 누적하여 비교한다. 검색 질의의 경우 3DR-tree에서 검색한 결과와 동일한 결과를 얻기 위해 데이타세트 생성시 이동 객체의 최대 이동 범위를 이용하여 버퍼 질의 모델을 이용한다.
색인의 성능 평가에서 사용될 데이타의 집합은 GSTD 알고리즘[11]을 기반으로 생성한다. KDB-tree와 의 성능 비교를 위하여 데이타셑은 0과 1사이의 정규화 된 데이타로 변환한다.
점 데이타는 각 차원(1차원, 2차원, …)상에서 공간적 영역을 점유하 지 않는 한 점으로 표현이 가능한 반면 SAM 방식은 공간적 영역을 점유하는 데이타(예를 들어 2차원에서 사각형, 3차원에서 구)를 효율적으로 검색하기 위해 사용되는 데이타 접근 방식이다[4]. 이 논문에서는 이동 객체의 과거 위치를 점으로 모델링하여 점으로 구성된 데이타베이스를 기반으로 하기 때문에 PAM방식의 색 인 방법을 사용한다.
따라서, 질의 결과의 일관성을 위하여 이동 객체 c의 검색 방법이 필요하다. 이 논문에서는 이동 객체의 최대 이동 범위 Vmax X Tmterval) 를 이용하여 질의 영역을 버퍼링 시킨 버퍼 질의 R'을 이용한다. 버 퍼 질의는 이동 객체의 위치를 점으로 표현할 경우 연 속된 두 점 사이의 위치 검색시 검색이 되지 않는 단점 을 보완한 방법으로 최대 이동 범위만큼 질의 영역을 버퍼링 시켜 질의 영역을 확대한 형태의 기법으로 query window extension(3)에 기반한다.
성능/효과
그리고 노드의 크기를 512, 1024, 2048Byte로 달리하면서 실험을 하였다. 그 결과 밀집 지역 밀도가 작을수록 좋은 성능을 보이고 있다. 그러나, 밀집 지역 밀도가 전체 영역에 대한 평균 면적의 비율 이하일 경우에는 동일한 성능을 나타내고, 추가적 으로 평균 면적의 크기를 감소시킨 실험에서는 평균 면 적의 크기와 성능이 반비례하였기 때문에 이후 실험에서 는 분할 시점을 밀집 지역 밀도가 0.
그림 15에서 MKDB-tree의 공간활용도가 다른 3개의 색인에 비해서 월둥함을 볼 수 있다. 기존의 분할 정책 을 사용하는 KDB-tree에 비해 20%~30%의 성능 향상 이 된 결과를 보이는데 이것은 시간 도메인의 특성을 고려하여 시간 분할 시에 균등 분할을 하지 않고 최근 시간 분할을 수행함으로써 이동 객체와 시간 도메인의 특성을 반영해준 결과라고 볼 수 있다.
둘째, KDB-tree의 포인트페이지 분할 방식인 균둥 분할 방식에서 시간 도메인으로 분할이 될 경우, 공간활 용도를 저하시키는 문제를 발생시킨다. 시공간에서 균둥 분할 방식은 공간 도메인으로 분할 할 때는 적합하지만, 시간 도메인으로 분할 할 때는 분할 후 과거 영역이 되는 포인트페이지의 공간활용도가 저하되는 문제를 발생 시킨다.
첫째, 데이타의 입력에 따라 분할 시점을 공간 도메인 분할에서 시간 도메인 분할로 전환 되는 전환점을 찾는 것이 필요하다. 둘째, 시간 도메인 으로 분할 할 경우 기존의 균등 분할 방식으로 분할할 경우 과거 영역이 되는 포인트페이지의 공간활용도가 낮아지는 단점이 있다.
시공간 영역 질의는 시간 차원을 공간의 다른 차원으로 간주하여 처리한다[11, 12]. 따라서 실험에서 질의 영역은 데이타 세트의 전체 시공간 도메인을 정규화하여 전체 시공간 영역의 5%, 10%, 20% 크기의 질의 집합을 구성한다. 각 질의 집합의 개수는 1000개이다.
특히 질의의 영역이 커질 경우 높은 공간 활용도로 인해 모든 데이타셑에서 성능 향상 비율이 유사함을 알 수 있다. 또한 시공간 질의에 우수한 MV3R-tree의 경우에도 K①B-tree와 3DR-tree에 비해 우수한 성능을 보이고 있지만, MKDB-tree는 이동 객체 데이타의 시간적 특성을 이용한 최근 시간 분 할 기법의 적용으로 MV3R-tree보다 28~35% 향상된 성능을 보이고 있다.
[6]에서는 KDB-tree의 영역페이지 분할 정책이 강제적으로 하위 영역에 전파된다고 하여 FS분할(Forced Splitting)과 영역페이지가 처음으로 분할되었던 분할 축에 의해 영 역페이지가 분할 하는 방식을 FD분할(First Division Splitting)이라 정의하고, 두 분할 정책에 관한 성능 비 교를 하였다. 성능 비교의 결과 FD분할이 강제로 영역 페이지의 하위 영역까지 분할이 전파되는 문제가 발생하는 FS분할 보다 포인트페이지의 공간활용도를 높이 고, 검색 성능도 향상 시킴을 보였다.
시공간에서의 이동객체 색인을 위해 시간도메인을 고려한 KDB-tree의 분할정책들을 구현하고 성능 평가 실험을 실시하여 시간도메인을 고려한 분할 정책을 사용한 K①B-tree의 성능이 기존의 K①B-tree의 성능보다 우수한 것을 알 수 있었다. 이 논문에서 제시한 분할 정책을 사용한 KDB-tree의 경우 색인의 구축비용이나 영역 질의에 대한 검색 비용에서 향상된 성능을 보였으며 특히 이동객체를 위한 시공간색인인 MV3R-tree 와 SAM 방식인 3D-Rtree와 Buffer질의를 사용한 영역질의에 대한 검색 성능 비교에서도 우수한 것을 볼 수 있었다.
그림 17, 그림 18, 그림 19에서는 질의 크기에 따른 검색 성능을 보이고 있다. 영역 질의 결과 단말 노드에 MBB를 저장하는 3DR-tree의 검색 성능은 점을 저장 하는 KDB-tree°l] 비해 작은 크기의 데이타 세트에서는 색인의 높이의 차이로 인해 검색 성능이 3배 이상 차이를 나타내지만, 데이타 세트 크기가 증가함에 따라 K①B-tree의 검색 성능은 3DR-tr既에 비해 평균 30% 의 성능 향상을 나타낸다. 이것은 색인의 높이가 차이가 적은 데이타 세트일 경우 버퍼 질의로 인한 노드 접근 회수가 증가하기 때문에 성능 향상 비율이 낮아진다.
시공간에서의 이동객체 색인을 위해 시간도메인을 고려한 KDB-tree의 분할정책들을 구현하고 성능 평가 실험을 실시하여 시간도메인을 고려한 분할 정책을 사용한 K①B-tree의 성능이 기존의 K①B-tree의 성능보다 우수한 것을 알 수 있었다. 이 논문에서 제시한 분할 정책을 사용한 KDB-tree의 경우 색인의 구축비용이나 영역 질의에 대한 검색 비용에서 향상된 성능을 보였으며 특히 이동객체를 위한 시공간색인인 MV3R-tree 와 SAM 방식인 3D-Rtree와 Buffer질의를 사용한 영역질의에 대한 검색 성능 비교에서도 우수한 것을 볼 수 있었다.
반대로 영역 페이지 R1의 분할 시점에서 LD분할을 사용하게 되면 과거의 영역이 되는 영역페이지에 pi, P5, P8을 삽입하고 새로운 영역페이지에 마지막 분할에 의해 발생한 포 인트페이지 P9를 삽입하게 된다. 즉 시간 분할 이후의 영역페이지 분할에서는 첫번째 분리된 분리 평면 보다 는 마지막으로 분리된 분리 평면으로 분할하는 것이 데 이타의 삽입에 의해 계속적으로 시간 도메인 t로 분할이 발생한다고 했을 때 더 효과적이다,
후속연구
마지막으로, KDB-tree의 영역페이지 분할 정책에 있어서 시공간의 이동 객체를 색인하기 위해서는 새로운 영역페이지 분할 정책이 필요하다. 기존의 FS(Forced Splitting)분할의 연쇄적 분할 전파 문제와 심각한 공간 활용도 저하 문제를 해결한 FD(First Division) 분할 정책[6]의 경우 시간 도메인으로의 분할 시 포인트 페이 지 분할의 문제와 같이 영역페이지의 공간활용도를 저 하시키고 색인의 깊이를 증가 시키게 된다.
참고문헌 (12)
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
G.Kollios, D. Gunopulos, and V. J. Tsotras, 'On Indexing Mobile Objects,' Int. conf. PODS, pp. 261-272, 1999
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
Y.Tao, D.Papadias, 'MV3R-tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries,' Int. conf. VLDB, pp. 431-440, 2001
Ratko Orlandic, Byunggu Yu, 'Implementing KDB trees to Support High-Dimensional Data,' Int. conf. IDEAS, pp. 58-67, 2001
J,T. Robinson, 'The K-D-B Tree: A Search Structure For Large Multidimensional Dynamic Indexes,' Int. Conf. ACM SIGMOD, pp. 10-18, 1981
M. Freeston, 'A General Solution of the N-dimensional B tree Problem,' Int. Conf. ACM SIGMOD, pp. 80-91, 1995
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
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
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
D.Pfoser, C. S.Jensen, Y. Theodoridis, 'Novel Approaches in Query Processing for Moving Object Trajectories,' Int. conf. VLDB, pp. 395-406, 2000
※ AI-Helper는 부적절한 답변을 할 수 있습니다.