일반기술

엠비알 압축 방법 및 이를 이용한 색인 구축 방법

본 발명은 MBR 압축 방법 및 이를 이용한 색인 구축 방법이다. 캐시의 활용도를 높이기 위해 노드의 크기를 캐시의 배수로 고정시키고, 고정된 노드 내 팬 아웃을 늘리기 위해 MBR을 보다 효과적으로 압축시키고, 이에 따라 색인을 동적 구성함으로써 이동객체의 위치에 대한 보다 빠른 검색 및 갱신을 가능토록 한다. 이를 위해 MBR 압축 기법으로 부모 노드에 상대적으로 표현된 RMBR을 변환함수를 통해 TRMBR로 압축하여 압축시 일어나는 오차를 최소화하고, 계산된 TRMBR의 크기에 따라 노드 내 엔트리를 동적으로 할당하여 상위 노드로 갈수록 키 비교 횟수를 줄이고, 하위 노드로 갈수록 캐시 미스를 줄여 이동 객체의 검색 및 갱신의 실시간 처리를 하도록 한 기술이다. 기존의 특허는 R-tree의 키로 사용되는 MBR을 부모 노드의 상대적인 값으로 표현된 RMBR을 16단계로 양자화 함으로써 MBR을 압축하였다. 그러나 본 발명에서 사용한 MBR압축기법은 부모 노드의 상대적인 값으로 표현된 RMBR을 변환 함수를 통하여 루트노드부터 단말노드까지 2, 4, 8 바이트로 압축하는 기법이며, 압축된 MBR의 크기를 기준으로 노드 내 엔트리를 할당함으로써 검색 및 검생 성능의 향상을 가져 온다. CR-tree에서는 부모 노드의 MBR에 상대적으로 표현된 MBR을 RMBR이라고 하고, RMBR을 일정한 비트를 사용하여 저장하도록 양자화한 것을 QRMBR이라 정의하였다. 그러나 CR-tree에서 소개된 QRMBR을 이용한 MBR 압축 방법은 실제 좌표를 QRMBR의 좌표로 변환하는 과정에서 오차가 나타나게 되며, 넓은 영역을 포함하는 상위 노드로 갈수록 이러한 오차는 더 커지게 되는 문제점을 해결한 특징이 있다. 본 발명은 MBR 압축 방법 및 이를 이용한 색인 구축 방법은 엔트리에 MBR 대신 TRMBR을 저장함으로써, 검색의 성능을 높이고, 노드 내 엔트리를 TRMBR의 크기와 동일하게 동적 할당함으로써, 상위 노드에서는 키 비교 횟수를 줄일 수 있고, 하위 노드로 갈수록 캐시 미스를 줄일 수 있어, 전체적인 검색 및 갱신 성능의 향상을 이루고, 이로써 이동객체의 검색 및 갱신 질의의 실시간 처리를 가능하게 하는 효과가 있다.위치를 알려주는 대표적인 기술인 차량항법장치 시장 규모의 성장이 2005년부터 급속히 확대되고 있으며, 전년대비 성장률도 빠르게 성장하고 있다. 차량항법장치 도입 초기에는 텔레매틱스처럼 자동차 제조업체의 시장 주도로 인해 임베디드 형태의 in-Vehicle 항법장치 시장이 성장을 주도해 왔으나, 장기적으로는 휴대형 차량항법장치가 시장을 주도할 것으로 전망된다.