지도 데이터베이스 관리

**지도 데이터베이스 관리**() 시스템은 항법 애플리케이션을 위한 공간 정보를 저장하고 호출하도록 설계된 소프트웨어 프로그램이며, 따라서 지리 정보 시스템의 한 형태이다. 이 시스템은 위치 측정 및 내비게이션, 특히 자동차 애플리케이션에서 널리 사용된다. 더욱이, 위치 기반 서비스, 능동 안전 기능 및 첨단 운전자 보조 시스템과 같은 신흥 분야에서 점점 더 중요한 역할을 하고 있다. 이러한 기능들의 공통점은 도로망을 설명하는 정보를 포함하는 차량 탑재용 지도 데이터베이스를 필요로 한다는 것이다.

잘 설계된 지도 데이터베이스는 방대한 양의 지리 데이터를 신속하게 인덱싱하고 조회할 수 있게 한다.

## 지도 데이터베이스의 내용

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

지도 데이터베이스는 도로망과 관련 피처(feature)를 나타낸다. 지도 제공업체는 데이터베이스를 구축하기 위한 기초로 도로망의 다양한 모델을 선택할 수 있다. 일반적으로 이러한 모델은 도로망의 기본 요소(노드, 링크, 영역)와 해당 요소의 속성(위치 좌표, 형상, 주소, 도로 등급, 속도 범위 등)으로 구성된다. 기본 요소는 피처라고 불리며 속성은 어트리뷰트(attribute)라고 불린다. 관심 지점(POI), 건물 형상, 행정 구역 경계 등 도로망과 관련된 기타 정보도 포함된다. 이는 인접한 이미지에 도식적으로 표시되어 있다. 지리 정보 데이터 파일(GDF)은 이러한 모델의 표준화된 설명이다.

지도 그래프 내의 각 노드는 지구 표면의 지점 위치를 나타내며 경도(lon)와 위도(lat) 좌표 쌍으로 표현된다. 각 링크는 두 노드 사이의 도로 구간을 나타내며, 직선 도로 구간에 해당하는 선분이나 일반적으로 링크를 따라 중간점(형상점 또는 쉐이프 포인트라고 함)에 의해 설명되는 곡선으로 표현된다. 그러나 곡선은 중심점(지점 또는 노드), 반경, 곡선의 경계를 정의하는 극좌표의 조합으로 표현될 수도 있다. 형상점은 노드와 마찬가지로 경위도 좌표로 표현되지만, 노드와 달리 링크를 연결하는 목적으로는 사용되지 않는다. 영역은 공원, 도시, 블록 등을 나타내는 2차원 형상이며 그 경계에 의해 정의된다. 이들은 보통 폐쇄된 다각형(polygon)으로 형성되는데, 이는 지도상의 객체가 닫힌 경계를 가져야 함을 나타내며, 즉 첫 번째 정점이 마지막 정점과 같아야 함을 의미한다. (예를 들어, 지도에 정사각형 객체를 그리려면 다각형의 정점 번호는 1, 2, 3, 4, 1 순서가 된다.)

데이터 유효성 검사를 위한 또 다른 점은 다각형 내부의 점(point in polygon) 판별로, 이는 다각형 외부에 있는 점을 찾는 데 도움이 된다. 예를 들어, 도시 내의 특정 경위도 좌표에 대해, 그 점이 다각형과 홀수 번 교차하면 다각형 내부의 유효한 점이고, 그렇지 않으면 다각형 외부의 유효하지 않은 점이다.

## 교환 형식

지도 제공업체는 일반적으로 정보 교환을 위해 특별히 고안되고 잘 정의된 파일 형식으로 데이터를 수집, 집계 및 공급한다. 예를 들어 나브텍(Navteq)은 표준 교환 형식(SIF) 및 지리 정보 데이터 파일(GDF)을 사용하고, 텔레아틀라스(Tele Atlas)는 GDF의 독자적인 형태를 사용한다. 이는 대개 일반 텍스트 형태(ASCII)로 되어 있어 데이터를 처리하는 여러 당사자가 쉽게 파싱하고 해석할 수 있는 필드들로 구성된다. 이 휴대용 형식 덕분에 단순한 텍스트 편집 프로그램으로도 추가, 삭제 및 수정을 쉽게 수행할 수 있다.

다양한 유형의 데이터를 나타내기 위해 소수의 레코드 유형이 사용된다. 각 레코드 유형은 고정 길이이거나 쉼표와 같은 구두점으로 구분된 필드 시퀀스로 구성된다. 예를 들어, 링크 엔티티는 다음과 같은 형식의 레코드로 표현될 수 있다:

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

지도 데이터베이스의 교환 형식은 실행 시간(runtime) 동안 내비게이션 장치가 사용하기에는 잘 조직되어 있지 않다. 레코드는 임의의 순서로 되어 있어 검색하기 어렵고, 거리 이름이나 좌표 값과 같은 데이터가 레코드마다 반복된다. 결과적으로 데이터베이스 내용은 런타임 운영에 더 적합한 이진(binary) 형태로 재구성된다.

## 런타임 형식
런타임 형식은 일반적으로 독점적(proprietary)이어서 서로 다른 내비게이션 시스템 간의 지도 상호 운용을 방해한다. 그러나 내비게이션 데이터 표준(NDS)이라는 새로운 이니셔티브는 자동차 내비게이션 시스템에 사용되는 데이터 형식의 표준화를 목표로 하는 자동차 제조업체, 내비게이션 시스템 공급업체 및 지도 데이터 공급업체의 산업 그룹이다. 참여 기업으로는 톰톰(TomTom), BMW, 폭스바겐(Volkswagen), 다임러 AG(Daimler), 르노(Renault), ADIT, 알파인 전자(Alpine Electronics), 나비곤(Navigon), 보쉬(Bosch), 덴소(DENSO), 미쓰비시(Mitsubishi), 하만 베커(Harman Becker), 파나소닉(Panasonic), PTV, 콘티넨탈 AG(Continental AG), 나브텍(Navteq) 및 젠린(Zenrin) 등이 있다.

데이터베이스는 내비게이션 제공업체에 의해 최소한 다음 다섯 단계를 포함하는 컴파일 프로세스를 통해 재구성된다:

# 네트워크 일관성 확인. 예를 들어, 링크로 연결되어야 하는 모든 노드 쌍이 실제로 그러한 링크를 가지고 있는지, 반대로 연결되지 않아야 하는 모든 노드 쌍이 연결 링크를 가지고 있지 않은지 확인한다.
# 모든 엔티티에 체계적인 방식으로 식별자(ID)를 할당한다.
# 예상되는 방식으로 데이터베이스 검색을 용이하게 하기 위해 엔티티에 여러 세트의 인덱스를 적용한다.
# 데이터 항목(거리 이름, 좌표 등)의 다중 발생을 해당 항목의 단일 사본을 포함하는 테이블의 인덱스로 대체한다.
# 데이터베이스의 전체 크기를 줄이기 위해 다른 압축 기술을 적용한다.

1단계의 일관성 확인은 일반적으로 매우 대화식이고 반복적인 프로세스이며 완료하는 데 몇 주가 걸릴 수 있다. 이 기간 동안 불일치 사항을 감지, 조사 및 해결해야 한다.

2단계에서 ID는 일반적으로 각 유형의 엔티티가 발견되는 순서대로 할당된다. 버전 간에 입력 데이터베이스에 가해진 모든 변경 사항은 모든 엔티티에 대한 ID 할당에 영향을 미친다. 결과적으로 버전 간 할당의 연속성은 거의 기대하기 어렵다.

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

## 증분 업데이트
대부분의 내비게이션 기능에서 차량 내에 최신 지도 데이터베이스를 보유하는 것은 중요하며, 특히 능동 안전과 관련된 기능의 경우 매우 중요하다. 일반적인 전략은 무선 채널을 통해 업데이트 정보가 가용해질 때마다 차량으로 전송하는 것이다. 무선 채널은 와이파이(Wi-Fi)나 휴대전화와 같은 양방향일 수도 있고, 위성 라디오, FM 부반송파 또는 ATSC 데이터 방송(datacasting)과 같은 방송일 수도 있으며, 또는 두 가지의 조합일 수도 있다. 어떤 경우든 수 기가바이트 크기에 달할 수 있으므로 기존 버전을 교체하기 위해 전체 새 데이터베이스를 전송하는 것은 비현실적이거나 매우 비효율적이다.

대신 기존 데이터베이스에 가해진 변경 사항과 관련된 정보만 전송하는 것이 바람직하다. 주요한 어려움은 지도 데이터베이스의 내용에 가해진 모든 변경이 일반적으로 컴파일 프로세스 중에 할당된 모든 엔티티 ID와 할당된 모든 인덱스의 변경을 초래한다는 점이다. 이러한 새로운 ID와 인덱스는 컴파일된 데이터베이스 전체에 퍼지기 때문에, 어떠한 증분 모음이라도 결국 데이터베이스의 대부분을 구성하게 될 가능성이 크다. 이 어려움을 극복하기 위해 세 가지 접근 방식이 취해졌는데, 간략히 1) 온보드 컴파일러 2) 룩어사이드 저장소(look-aside store) 3) 지리적 타일이다.

### 온보드 컴파일러
이 경우, 데이터베이스의 교환 형식에 가해진 기본적인 변경 사항이 차량으로 전송된다. 이러한 변경 사항은 추가, 삭제 및 교체로 구성된 트랜잭션 형태로 표현된다. 이러한 변경 사항은 교환 형식으로 된 기존 온보드 데이터베이스에 적용된다. 온보드 데이터베이스를 위한 교환 형식은 별도로 저장되거나 런타임 형식을 "역컴파일"하여 필요할 때 생성될 수 있다. 그런 다음 결합된 데이터베이스가 컴파일되며, 여기에는 ID 할당 및 인덱스 적용이 포함된다.

이러한 온보드 컴파일은 계산 집약적이며 상당한 메모리를 필요로 할 가능성이 크다. 그러나 일관성 확인 및 해결이 이미 완료되었을 것이므로 오프보드 컴파일처럼 대화식이고 반복적일 필요는 없다. 또한 온보드 컴파일은 백그라운드에서 수행될 수 있으므로 계산 시간이 결정적이지는 않다.

### 룩어사이드 저장소
이 경우에도 기본적인 변경 사항이 차량으로 전송되지만, 룩어사이드 저장소라고 불리는 별도의 메모리 위치에 배치된다. 변경 사항은 또한 트랜잭션 형태로 표현되지만, 교환 형식이나 런타임 형식일 필요 없이 편리한 형식으로 나타날 수 있다. 내비게이션 장치 작동 중에 주 데이터베이스에 액세스할 때마다 룩어사이드 저장소를 검색한다. 액세스된 데이터와 관련된 모든 트랜잭션(변경 사항)이 그때 적용된다.

데이터베이스에 액세스할 때마다 룩어사이드 저장소를 검사하고 변경 사항을 적용해야 하는 필요성은 당연히 내비게이션 알고리즘을 복잡하게 만들고 계산 시간을 연장시킨다. 그러나 이는 온보드 컴파일러의 필요성을 피하게 해준다.

### 지리적 타일
이 접근 방식에서 지도 데이터베이스는 지도를 격자 형태로 채우는 비교적 작은 직사각형 영역(타일)으로 나뉜다. 타일 크기는 한 변이 약 1&nbsp;km 정도이다. 이러한 타일들은 개별적으로 컴파일되므로, 모든 ID와 인덱스는 해당 타일에 국한된다. 데이터베이스의 기본 엔티티나 속성 변경으로 인해 변경된 타일들이 차량으로 전송되어 기존의 해당 타일을 교체한다.

타일을 교체하는 것은 온보드 컴파일이나 룩어사이드 저장소를 사용하는 것보다 훨씬 간단하다. 그러나 전송 효율이 떨어질 수 있다. 엔티티 및 속성에 대한 국지적 변경은 그 범위에 상관없이 해당 엔티티를 포함하는 전체 타일의 전송을 요구한다. 또한 한 타일 내의 엔티티 변경이 인접 타일의 엔티티에 영향을 미치는 경계 효과가 있다. 적은 수의 엔티티 변경으로 인해 거의 모든 타일을 전송해야 할 수도 있으며, 이는 증분 업데이트의 목적을 무색하게 만든다. 이러한 문제는 타일 크기와 업데이트 빈도를 선택함으로써 해결될 수 있다.

## 보조 데이터 부착
능동 안전, 운전자 보조 및 위치 기반 서비스와 관련된 다양한 내비게이션 기능은 지도 데이터베이스의 일부로 간주되지 않으며 지도 제공업체가 아닌 다른 벤더가 공급할 가능성이 있는 데이터를 필요로 한다. 이러한 데이터는 주 데이터베이스의 엔티티 및 속성과 상호 참조될 필요가 있다. 그러나 보조 데이터가 반드시 주 데이터베이스와 함께 컴파일되는 것은 아니므로, 보조 데이터를 부착한다고 하는 상호 참조를 확립하기 위한 다른 수단이 필요하다. 두 가지 일반적인 접근 방식은 기능 특정 참조 테이블과 범용 참조이다.

### 기능 특정 참조 테이블
기능 특정 참조 테이블은 참여하는 모든 공급업체가 생산한 지도 데이터베이스에 기능 특정 데이터를 부착하기 위한 수단을 제공한다. 이러한 테이블은 위치 기반 서비스, 능동 안전 또는 첨단 운전자 보조와 관련된 특정 기능 또는 기능 클래스를 지원하기 위해 협력적으로 제작된다. 이는 일반적으로 식별 속성(예: 거리 이름, 경도/위도 좌표 등)과 함께 특정 유형의 지도 요소(예: 링크, 교차로, 관심 지점 위치 등) 목록으로 구성된다. 또한 테이블의 각 항목에는 고유한 식별자가 할당된다. 테이블의 항목 세트는 일반적으로 모든 이해 관계자의 합의를 통해 선택된다. 실제적인 문제로서, 그 결과는 지도 데이터베이스에서 사용 가능한 해당 유형 요소들의 작은 부분 집합이 될 것이며 애플리케이션 분야에서 더 중요한 것들로 구성될 것이다. 테이블이 공식화된 후, 각 참여 공급업체는 테이블 항목에 해당하는 자신의 지도 데이터베이스 요소를 결정하고 상호참조하는 과업을 수행한다.

frame|right|메트로 디트로이트의 TMC 위치
널리 사용되는 예는 교통 데이터를 참조하기 위한 위치 코드 테이블의 TMC 표준이다. 라디오 데이터 시스템(RDS)의 일부인 TMC(교통 메시지 채널)는 상업용 FM 방송 신호의 부반송파 변조로 구현된다. TMC 테이블은 주로 다른 도로와의 교차로에 해당하는 주요 도로를 따른 지점 위치에 대한 참조를 제공한다. 테이블 항목은 문맥 정보(지역, 도로 및 도로 구간, 교차로 이름 등)와 대략적인 경위도 좌표를 모두 사용하여 지점 위치를 식별한다.

테이블의 항목에 할당된 식별자는 16비트 정수이므로 65536개의 값 범위를 갖는다. 이는 전 세계를 커버하기에는 너무 적기 때문에 각 국가 또는 국가의 지역별로 별도의 테이블이 구성된다. 특정 대도시 지역의 경우, 고속도로, 간선 도로 및 일부 주요 도로를 따른 교차로만 포함된다. 이는 디트로이트 메트로 지역에 대한 다음 그림에 예시되어 있다. 이 범위는 사용량이 많은 도로에서 교통 안내 정보를 제공하기 위한 것이다. 반면 교통 기반 경로 계획은 모든 또는 거의 모든 주요 도로의 범위를 필요로 하므로, 현재 구성된 TMC 위치 코드 테이블로는 충분히 지원되지 않는다.

### 범용 참조
범용 참조(Generic referencing)는 일종의 지도 매칭을 통해 참조 정보를 발견함으로써 모든 지도 데이터베이스에 데이터를 부착하려는 시도이다. 기능 특정 데이터 항목은 특정 지도 데이터베이스의 해당 지도 요소와 단지 근사할 가능성이 있는 점, 링크 또는 영역과 같은 요소에 할당된다. 최적의 일치를 위해 지도 데이터베이스 검색이 이루어진다. 검색 프로세스를 향상시키기 위해, 각 사례에서 올바른 해결책이 발견되도록 돕기 위해 주변 요소들을 각 해당 요소에 전략적으로 추가한다. 예를 들어, 지도 요소가 두 교차로를 연결하는 링크라면, 검색을 위해 하나 또는 두 교차하는 도로를 추가할 수 있다. 다행히도 이는 잘못된 매칭이 발생할 가능성을 낮춘다. 이 절차는 상당히 휴리스틱하지만, Agora라는 제안된 표준은 추가할 주변 요소를 선택하기 위한 전략을 개략적으로 설명한다.

## 유럽 컨소시엄 ActMAP
ActMAP(Actualize Map)이라 불리는 유럽 컨소시엄은 (그들의 표현에 따르면) "기존 지도 데이터베이스 내용을 업데이트하고 디지털 차량용 지도에 정보를 동적으로 부착할 수 있게 하는 표준화된 메커니즘을 개발 중"이다. ActMAP 컨소시엄은 ERTICO(코디네이터), BMW, CRF 피아트 연구 센터, 다임러크라이슬러, 나비곤, 나브텍, 텔레아틀라스, 지멘스 VDO 오토모티브로 구성된다. 그들은 대부분의 작업을 마쳤으며 다수의 보고서를 발표했고, 이는 표준화를 위해 국제 표준화 기구(ISO) 위원회 TC204 WG3에 제출되었다. 그들의 보고서는 이 프로젝트의 훌륭한 출발점이자 참고 자료 역할을 한다. 보고서가 다루는 중요한 문제는 독점 형식을 사용하는 여러 지도 공급업체와 여러 데이터 공급업체 및 여러 버전의 차량용 지도가 결합된 복잡성을 처리하는 것이다. 그들은 XML로 표현되고 ISO 표준 GDF 4.0의 개념을 기반으로 하는 개방형 중간 지도 형식을 사용하여 이를 해결한다. 공급업체 데이터베이스에 대한 모든 수정 사항은 먼저 이 중간 형식으로 변환되어 서버에 저장된 다음 각 개별 차량 내에서 사용되는 형식으로 변환된다. 그들은 각 차량에 지도 공급업체의 "베이스라인" 지도가 있으며, 이 베이스라인이 업데이트될 대부분의 피처에 대한 참조 식별자(예: 지도 세그먼트 ID)를 정의한다고 가정한다. 베이스라인에 참조 식별자가 없는 피처의 경우, AGORA라 불리는 제안된 표준에서 설명된 대로 지도 매칭을 사용하여 휴리스틱하게 발견되는 "범용" 참조를 사용할 것을 제안한다.

ActMAP이 직접 다루지 않은 주요 문제는 공급업체의 지도 데이터베이스 새 버전이 나올 때마다 모든 참조 ID가 대개 컴파일 프로세스에 의해 다시 할당되어 이전 버전 ID와의 대응 관계가 파괴된다는 점이다. 이는 이전 버전에서 지도 데이터베이스의 새 버전을 생성하기 위해 증분 업데이트를 사용하는 능력을 심각하게 방해한다. ActMAP이 해결하지 못한 또 다른 문제는 도로 세그먼트의 하위 섹션(예: 곡선, 언덕, 조작 차로 등)을 업데이트하기 위해 이를 참조하고 특성화할 수 없다는 점이다.

## 같이 보기
* 차량 자동 항법 장치
* 최단 경로 문제: 지도 데이터베이스로부터 내비게이션 경로를 얻기 위해 사용되는 문제 및 알고리즘 클래스.
* 지리 데이터베이스
* 지리 정보 시스템
* 위성 항법 시스템
* 지능형 교통 체계
* 지도
* 나브텍
* 관심 지점
* 객체 관계 데이터베이스
* 개방형 공간 정보 컨소시엄
* 로봇 매핑
* 텔레아틀라스
* 텔레매틱스

## 각주


분류:데이터베이스 관리 시스템
분류:지리 정보 소프트웨어