지도 데이터베이스 관리

지도 데이터베이스 관리 시스템은 공간 정보를 효율적으로 저장하고 호출할 수 있도록 설계된 소프트웨어 프로그램이다. 국산화 및 내비게이션, 특히 자동차 용도에 널리 사용된다. 게다가, 그들은 위치 기반 서비스, 능동적인 안전 기능 및 첨단 운전자 지원 시스템의 신흥 영역에서 점점 더 중요한 역할을 하고 있다. 이러한 기능에 공통적인 것은 도로망을 기술하는 정보를 포함하는 온보드 맵 데이터베이스의 요구 사항이다.

잘 설계된 지도 데이터베이스는 대량의 지리적 데이터를 신속하게 색인화하고 조회할 수 있게 한다.

지도 데이터베이스의 내용

지도는 그래프로 저장되거나 위치와 범주의 속성을 가진 2차원 객체 배열로 저장되며, 여기에는 공원, 도로, 도시 등이 포함된다.

지도 데이터베이스는 관련 기능과 함께 도로망을 나타낸다. 지도 제공자는 데이터베이스를 구축하기 위한 기초로 도로망의 다양한 모델을 선택할 수 있다. 일반적으로 이러한 모델은 도로망의 기본 요소(노드, 링크 및 영역)와 그러한 요소들의 특성(위치 좌표, 형태, 주소, 도로 등급, 속도 범위 등)으로 구성된다. 기본 요소는 특징이라고 하고 속성은 속성이라고 한다. 관심 지점, 건물 모양, 정치적 경계 등 도로망과 관련된 다른 정보도 포함된다. 이것은 인접한 이미지에 도식적으로 표시된다. GDF(^[1]Geographic Data Files)는 그러한 모델에 대한 표준화된 설명이다.

지도 그래프 내의 각 노드는 지구 표면의 점 위치를 나타내며 경도(lon)와 위도(lat) 좌표로 표시된다. 각 링크는 두 노드 사이의 도로 확장을 나타내며, 링크를 따라 중간 지점(형상점이라 함)으로 일반적으로 설명되는 모양을 가진 선 세그먼트(도로의 직선 구간에 대응) 또는 곡선으로 표현된다. 그러나 곡선은 또한 곡선의 경계를 정의하기 위해 반지름을 가진 중심(점 또는 노드)과 극 좌표의 조합으로 나타낼 수 있다. 형상점은 노드처럼 외톨이 lat 좌표로 표시되지만 형상점은 노드처럼 링크 연결 목적을 제공하지 않는다. 영역은 공원, 도시, 블록과 같은 것들을 나타내는 2차원적 형상으로 그 경계로 정의된다. 이것들은 보통 닫힌 다각형에 의해 형성되는데, 이것은 지도 위에 있는 물체가 경계선을 가져야 한다는 것을 나타내는 형상으로서, 첫 번째 다각형은 마지막 다각형과 같아야 한다는 것을 의미한다. (예를 들어, 지도에 사각형 물체를 그리기 위해 다각형은 1,2,3,4,1이다.)

데이터에 대한 유효성 검사를 위한 또 다른 지점은 폴리곤의 점으로, 폴리곤 외부에 놓여 있는 점을 찾는 데 도움이 된다. 예를 들어, 도시의 특정 외톨이 좌표에 대해, 점이 홀수 숫자로 폴리곤과 교차하는 경우, 폴리곤 내부와 유효점, 그렇지 않은 경우 폴리곤 외부에 있고 유효하지 않다.

교환 형식

일반적으로 지도 제공자들은 정보 교환을 위해 특별히 고안된 잘 정의되고 문서화된 파일 형식(예: Navteq는 SIF(^[2]Standard Interchange Format)와 GDF를 사용하는 반면 Tele Atlas는 GDF의 독점적 형식을 사용한다.^[3] 보통은 그것을 다룰 여러 당사자들이 쉽게 구문 분석하여 해석하는 분야로 구성된 평문형(ASCII)으로 되어 있다. 휴대용 포맷은 간단한 텍스트 편집 프로그램에 의해 추가, 삭제 및 수정을 쉽게 수행할 수 있다.

다양한 유형의 데이터를 나타내기 위해 적은 수의 기록 유형이 사용된다. 각 레코드 유형은 고정된 길이 또는 쉼표와 같은 구두점 문자로 구분되는 일련의 필드로 구성된다. 예를 들어 연결실체는 다음과 같은 형식의 기록으로 나타낼 수 있다.

유형1,210,node1,z1,node2,z2,class, 쉐이프 포인트 수,차선 수,속도

여기서 type1은 이를 링크 레코드 유형으로 정의하고 라벨은 이 링크를 다른 모든 링크와 구별하기 위한 식별자 역할을 한다. z1과 z2 필드는 해당 노드 1과 노드2를 공유하는 다른 노드와 이 링크의 수직 분리를 결정한다. 따라서 예를 들어 링크에 대한 고가도로는 링크에 연결되지 않은 것으로 나타낼 수 있다. 기타 기록 유형은 주소 정보, 링크의 형상점, 도시 및 상태, 관심 지점(POI) 등을 나타내기 위해 사용된다.

지도 데이터베이스의 교환 형식은 런타임 동안 항법 장치가 사용할 수 있도록 잘 구성되지 않는다. 기록은 임의의 순서로 되어 있어 검색이 어렵고 거리명, 조정값 등 데이터가 기록에서 기록으로 반복된다. 따라서 데이터베이스 콘텐츠는 런타임 운영에 보다 적합한 이진 형태로 재구성된다.

런타임 형식

런타임 형식은 일반적으로 독점적이어서 서로 다른 항법 시스템 간의 지도 상호작용을 방지한다. 그러나 NDS(Navigation Data Standard)라는 새로운 이니셔티브는 자동차 제조업체, 내비게이션 시스템 공급업체 및 지도 데이터 공급업체로 구성된 산업군이며, 자동차 내비게이션 시스템에 사용되는 데이터 형식의 표준화를 목표로 하고 있다.^[4] 관련 기업으로는 톰톰, BMW, 폭스바겐, 다임러, 르노, ADIT, 알파인전자, 네비던, 보쉬, 덴소, 미쓰비시, 하만베커, 파나소닉, PTV, 컨티넨탈 AG, 나브텍, 젠린 등이 있다.

데이터베이스는 적어도 다음의 5단계를 포함하는 컴파일 프로세스를 통해 네비게이션 제공자에^[5][6][7] 의해 재구성된다.

1. 네트워크 일관성을 확인하십시오. 예를 들어 링크로 연결해야 하는 모든 노드 쌍에 이러한 링크가 있는지 확인하고 반대로 연결되지 않아야 하는 모든 노드 쌍에는 연결 링크가 없는지 확인하십시오.
2. 식별자(ID)를 모든 엔티티에 체계적으로 할당한다.
3. 예상된 방법으로 데이터베이스를 쉽게 검색할 수 있도록 여러 개의 인덱스 세트를 엔티티에 적용하십시오.
4. 데이터 항목(거리 이름, 좌표 등)의 여러 발생을 인덱스에 의해 해당 항목의 단일 복사본을 포함하는 표로 대체한다.
5. 데이터베이스의 전체 크기를 줄이려면 다른 압축 기술을 적용하십시오.

1단계의 일관성 검사는 보통 매우 상호작용적이고 반복적인 과정으로 완료하는 데 몇 주가 걸릴 수 있다. 이 시간 동안 불일치를 탐지, 조사 및 해결해야 한다.

2단계에서 ID는 일반적으로 각 유형의 엔티티가 만나는 대로 순차적으로 할당된다. 입력 데이터베이스를 한 버전에서 다른 버전으로 변경하면 모든 엔티티에 대한 ID 할당에 영향을 줄 것이다. 따라서 버전 간 할당에서는 연속성이 거의 기대할 수 없다.

3단계에서 각 적용된 색인은 데이터베이스를 특정 방식으로 신속하게 검색할 수 있도록 한다. 링크에 적용된 하나의 인덱스 세트는 링크의 거리 이름의 알파벳 순서로 정렬할 수 있다. 링크에 적용되는 또 다른 인덱스 세트는 경로 계획을 용이하게 하기 위해 연결된 노드에 따라 정렬할 수 있다. 그러나 노드에 적용되는 또 다른 인덱스 세트는 도로를 따라 나타나는 순서에 따라 정렬할 수 있다. 이러한 경우 전체 검색 대신 바이너리 검색을 수행할 수 있으며, 경우에 따라 검색 프로세스를 간단한 테이블 검색으로 대체할 수 있다.

증분 업데이트

대부분의 항법 기능의 경우 차량에 최신 지도 데이터베이스를 두는 것이 중요하며, 일부 기능의 경우 특히 능동적 안전과 관련된 데이터베이스는 매우 중요하다. 일반적인 전략은 무선 채널을 통해 업데이트 정보를 이용할 수 있게 될 때마다 차량에 전송하는 것이다. 무선 채널은 Wi-Fi 및 휴대 전화와 같은 양방향, 위성 라디오, FM 하위 캐리어 또는 ATSC 데이터 캐스팅과 같은 브로드캐스트 또는 둘 모두의 조합일 수 있다. 어떤 경우에도 기존 버전을 대체하기 위해 새 데이터베이스 전체를 전송하는 것은 비실용적이거나 극도로 비효율적일 것이다. 왜냐하면 그것은 크기가 수 기가바이트가 될 가능성이 높기 때문이다.

대신 기존 데이터베이스의 변경사항과 관련된 정보만 전송하는 것이 바람직하다. 주요한 어려움은 일반적으로 지도 데이터베이스 내용에 대한 변경으로 인해 편집 과정에서 할당된 모든 개체 ID와 할당된 모든 지수에 변경이 발생한다는 것이다. 이러한 새로운 ID와 인덱스는 컴파일된 데이터베이스 전체에 침투하여 증분 수집이 데이터베이스의 대부분을 구성하게 된다. 이 어려움을 극복하기 위해 세 가지 접근법을 취했는데, 그것은 간단히 1) 온보드 컴파일러 2) look-aside store 3) 지리적 타일이다.

온보드 컴파일러

이 경우 데이터베이스의 교환 형식에 대한 기본적인 변경사항은 차량에 전송된다. 그러한 변경은 추가, 삭제 및 대체로 구성된 거래 형태로 표현된다. 이러한 변경사항은 교환 형식으로 기존 온보드 데이터베이스에 적용된다. 온보드 데이터베이스의 교환 형식은 별도로 저장하거나 런타임 형식을 "비축"하여 필요에 따라 생성할 수 있다. 그런 다음 통합 데이터베이스를 컴파일하는데, 여기에는 ID 할당과 인덱스 적용이 포함된다.

이 선내 컴파일은 계산적으로 집약적이며 상당한 메모리가 필요할 것이다. 그러나 일관성 확인과 해결이 이미 수행되었으므로 오프보드 컴파일처럼 상호적이고 반복적일 필요는 없다. 또한, 선상 컴파일은 백그라운드에서 수행될 수 있으므로 계산 시간은 중요하지 않다.

Look-aside 스토어

이 경우 기본적인 변경사항도 차량으로 전송되지만 룩애사이드 스토어라고 하는 별도의 메모리 위치에 배치된다. 변경사항도 트랜잭션 형식으로 표시되지만, 반드시 교환 또는 런타임일 필요는 없는 편리한 형식으로 표시될 수 있다. 항법 장치 작동 중에는 메인 데이터베이스에 접근할 때마다 보기 저장소를 검색한다. 액세스한 데이터와 관련된 모든 트랜잭션(변경사항)이 적용된다.

각 데이터베이스 액세스에 대한 변경사항 적용과 룩애즈 스토어의 필요성은 물론 탐색 알고리즘을 복잡하게 만들고 계산 시간을 연장한다. 그러나 이는 온보드 컴파일러의 필요성을 회피한다.

지리적 타일

이 접근법에서 지도 데이터베이스는 지도를 테셀링하는 비교적 작은 직사각형 영역(타일)으로 세분된다. 타일 사이즈는 측면 1km의 순서로 되어 있다. 이러한 타일은 별도로 컴파일되므로 모든 ID와 인덱스는 해당 타일이 적용되는 특정 타일에 의해 조건화된다. 기본 엔티티나 데이터베이스에 대한 속성 변경으로 인해 변경된 타일은 차량에 전송되며, 여기서 해당 기존 타일을 대체한다.

타일을 교체하는 것은 선상 컴파일이나 겉모양 스토어를 사용하는 것보다 훨씬 간단하다. 그러나 전송에는 효율적이지 않을 수 있다. 범위에 관계없이 엔티티와 속성에 대한 국지적 변경은 포함된 전체 타일의 전송을 요구한다. 더욱이 하나의 타일 내의 실체 변화가 이웃 타일의 실체에 영향을 미치는 가장자리 효과가 있다. 적은 수의 엔티티 변경으로 거의 모든 타일의 전송이 필요하게 되어 증분 업데이트의 목적을 저해할 가능성이 상당히 있다. 이러한 문제는 타일 크기와 업데이트 빈도를 선택하여 해결할 수 있다.

보조 데이터 첨부

능동적 안전, 운전자 지원 및 위치 기반 서비스를 포함하는 다양한 항법 기능에는 지도 데이터베이스의 일부로 간주되지 않으며 지도 제공자의 그것 이외의 벤더가 제공할 가능성이 있는 데이터가 필요하다. 이러한 데이터는 주 데이터베이스의 엔티티 및 속성과 상호 참조되어야 한다. 그러나 보조자료는 반드시 주 데이터베이스와 함께 컴파일되지 않으므로 상호 참조를 설정하기 위한 다른 수단이 필요하며, 이를 보조자료 첨부라고 한다. 두 가지 일반적인 접근방식은 기능별 참조표와 일반 참조다.

기능별 참조 표

기능별 참조 표는 모든 참여 공급자가 생산한 지도 데이터 베이스에 기능별 데이터를 부착하는 수단을 제공한다. 이러한 표는 위치 기반 서비스, 능동 안전 또는 첨단 운전자 지원을 포함하는 특정 기능 또는 기능 클래스를 지원하기 위해 협력적으로 제작된다. 일반적으로 특정 유형의 지도 요소 목록(예: 링크, 교차로, 관심 지점 위치 등)과 함께 속성(예: 도로명, 경도/위도 좌표 등)으로 구성된다. 또한 표의 각 항목에는 고유 식별자가 할당된다. 표의 항목 집합은 일반적으로 모든 이해 당사자의 합의를 통해 선택된다. 실제적인 문제로서, 결과는 지도 데이터베이스에서 사용할 수 있는 주어진 유형의 요소의 작은 부분집합을 나타낼 것이며, 적용 영역에 더 중요한 요소들로 구성될 것이다. 표를 공식화한 후에는 각 참여 공급업체가 표 항목에 해당하는 지도-데이터베이스의 요소를 결정하고 상호 참조하는 것이 과제다.

널리 사용되는 예는 교통 데이터를 참조하기 위한 위치 코드 테이블에 대한 TMC 표준이다. 교통 메시지 채널을 뜻하는 TMC는 상용 FM 방송 신호의 서브캐리어 변조(sub-carrier modulation)로 구현되는 라디오 데이터 시스템(RDS)의 일부다.^[8] TMC 표는 주로 다른 도로와의 교차로에 해당하는 주요 도로를 따라 지점 위치에 대한 참조를 제공한다. 표 항목은 상황별 정보(예: 지역, 도로 및 도로 구간, 교차로 이름)와 대략적인 경도/위도 좌표 모두를 사용하여 점 위치를 식별한다.

표의 항목에 할당된 식별자는 16비트 정수이므로 값이 65536이다. 이것은 세계를 커버하기에는 너무 적기 때문에, 한 나라의 각 나라 또는 지역에 대해 별도의 테이블이 만들어진다. 특정 대도시 지역의 경우 고속도로, 동맥 및 일부 주요 도로를 따라 교차하는 교차로만 포함된다. 이것은 디트로이트 메트로 지역의 다음 그림에 설명되어 있다. 이 커버리지는 이용률이 높은 도로에 대한 교통 자문 정보를 제공하기 위한 것이다. 반면, 교통 기반 노선 계획은 모든 또는 거의 모든 주요 도로의 커버리지가 필요하며, 따라서 TMC 위치 코드 표는 현재 수립되어 있는 것처럼 적절하게 지지되지 않는다.

일반 참조

제네릭 참조는 지도 매칭의 형태를 통해 참조 정보를 발견함으로써 모든 지도 데이터베이스에 데이터를 첨부하려는 시도다. 기능별 데이터 항목은 특정 지도 데이터베이스의 해당 지도 요소와 근사할 가능성이 있는 지점, 링크 또는 영역과 같은 요소에 할당된다. 지도 데이터베이스를 검색하면 가장 적합하다. 검색 프로세스를 강화하기 위해 각 주어진 요소에 인접 요소를 전략적으로 추가하여 각 사례에서 올바른 해결책을 찾을 수 있도록 한다. 예를 들어, 지도 요소가 두 개의 교차로를 연결하는 링크인 경우, 검색을 위해 한 개 또는 두 개의 교차로를 추가할 수 있다. 바라건대, 이것이 잘못된 일치를 가능성이 없게 만들기를 바란다. 비록 그 절차가 상당히 휴리스틱하지만, 아고라라고 불리는 제안된 표준은 덧붙일 이웃 요소들을 선택하는 전략을 간략하게 설명하고 있다.

유럽 컨소시엄 ActMAP

액트맵(ActMAP)^[9]이라는 유럽 컨소시엄은 (그들의 말로) "기존 지도 데이터베이스 콘텐츠를 업데이트하고 디지털 차량 내 지도에 동적으로 정보를 첨부할 수 있도록 표준화된 메커니즘을 개발한다"는 것이다. 액트맵 컨소시엄은 ERTICO(코디네이터), BMW, CRF 피아트 연구센터, 다임러크라이슬러, 네비던, 나브텍, 텔레 아틀라스, 지멘스 VDO 오토모티브로 구성된다. 그들은 대부분의 작업을 끝내고 표준화 기구 위원회 TC204 WG3에 제출된 다수의 보고서를 발표했다. 그들의 보고서는 이 프로젝트 작업의 좋은 출발점과 참고자료로 작용한다. 그들의 보고서가 다루는 중요한 문제는 독점적 형식을 사용하는 다중 지도 공급자와 다중 데이터 공급자의 복잡성 및 차량 내 지도의 다중 버전을 다루는 것이다. 그들은 XML로 표현된 개방형 중간 지도 형식을 사용하고 ISO 표준 GDF 4.0의 개념을 기반으로 하여 이를 해결한다. 공급자의 데이터베이스에 대한 모든 수정사항은 먼저 이 중간 형식으로 변환되어 서버에 저장한 다음 개별 차량 내에서 사용되는 각 형식으로 변환된다. 그들은 각 자동차가 지도 공급자의 "기본" 지도를 가지고 있고 이 기준선이 업데이트될 대부분의 기능에 대한 참조 식별자(예: 지도 세그먼트 ID)를 정의한다고 가정한다. 기준선에 기준 식별자가 없는 형상의 경우, 그들은 AGORA라는 제안된 표준에 의해 기술된 지도 일치를 사용하여 발견되는 "일반적인" 참조를 사용할 것을 제안한다.

ActMAP에서 직접적으로 다루지 않는 주요 문제는 공급자의 지도 데이터베이스의 새로운 버전 각각에 대해 모든 참조 ID는 보통 컴파일 프로세스에 의해 재할당되며, 이는 이전 버전의 ID와의 모든 통신을 파괴한다는 것이다. 이는 이전 버전에서 새로운 버전의 지도 데이터베이스를 생성하기 위해 증분 업데이트를 사용하는 기능에 심각한 지장을 준다. ActMAP에 의해 해결되지 않은 또 다른 문제는 도로 세그먼트(예: 곡선, 언덕, 기동 차선 등)의 하위 구역을 갱신하기 위해 참조하고 특성화할 수 없다는 것이다.

참고 항목

• 자동차 항법 시스템
• 최단 경로 문제, 문제 클래스 및 지도 데이터베이스에서 탐색 경로를 얻기 위해 사용되는 알고리즘.
• 지리적 데이터베이스
• 지리정보시스템
• 글로벌 내비게이션 위성 시스템
• 지능형 교통 시스템
• 지도
• 나브텍
• 관심장소
• 객체 관계 데이터베이스
• 오픈 지리공간 컨소시엄
• 로보틱 매핑
• 텔레 아틀라스
• 텔레매틱스

참조