Zarządzanie bazą danych map - Map database management

Systemy zarządzania bazami danych map to programy zaprojektowane do wydajnego przechowywania i przywoływania informacji przestrzennych. Są szeroko stosowane w lokalizacji i nawigacji, zwłaszcza w zastosowaniach motoryzacyjnych. Co więcej, odgrywają one coraz większą rolę w powstających obszarach usług lokalizacyjnych , funkcji bezpieczeństwa aktywnego i zaawansowanych systemów wspomagania kierowcy . Wspólne dla tych funkcji jest wymóg posiadania pokładowej bazy danych map zawierającej informacje opisujące sieć drogową.

Dobrze zaprojektowana baza danych map umożliwia szybkie indeksowanie i wyszukiwanie dużej ilości danych geograficznych.

Zawartość bazy danych map

Rysunek 1: Obiekty i ich odpowiednie atrybuty w bazie danych map

Mapy są przechowywane jako wykresy lub dwuwymiarowe tablice obiektów z atrybutami lokalizacji i kategorii, przy czym niektóre popularne kategorie obejmują parki, drogi, miasta i tym podobne.

Baza danych map reprezentuje sieć dróg wraz z powiązanymi elementami. Dostawcy map mogą wybrać różne modele sieci drogowej jako podstawę do stworzenia bazy danych. Zazwyczaj taki model obejmuje podstawowe elementy (węzły, połączenia i obszary) sieci drogowej oraz właściwości tych elementów (współrzędne lokalizacji, kształt, adresy, klasa drogi, zakres prędkości itp.). Podstawowe elementy są określane jako cechy, a właściwości jako atrybuty. Uwzględniono również inne informacje związane z siecią dróg, w tym ciekawe miejsca, kształty budynków i granice polityczne. Jest to pokazane schematycznie na sąsiednim rysunku. Pliki danych geograficznych (GDF) to ustandaryzowany opis takiego modelu.

Każdy węzeł na wykresie mapy reprezentuje położenie punktu na powierzchni Ziemi i jest reprezentowany przez parę współrzędnych długości geograficznej (lon) i szerokości geograficznej (lat). Każde połączenie reprezentuje odcinek drogi między dwoma węzłami i jest reprezentowany przez odcinek linii (odpowiadający prostemu odcinkowi drogi) lub krzywą o kształcie, który jest ogólnie opisywany przez punkty pośrednie (zwane punktami kształtu) wzdłuż połączenia. Jednak krzywe mogą być również reprezentowane przez kombinację środka ciężkości (punktu lub węzła) z promieniem i współrzędnych biegunowych w celu zdefiniowania granic krzywej. Punkty kształtu, podobnie jak węzły, są reprezentowane przez współrzędne długie i szerokie, ale punkty kształtu nie służą do łączenia połączeń, tak jak węzły. Obszary to dwuwymiarowe kształty, które reprezentują takie rzeczy jak parki, miasta, bloki i są określone przez ich granice. Są one zwykle tworzone przez zamknięty wielokąt , czyli kształty wskazujące, że obiekt nad mapą musi mieć bliską granicę, co oznacza, że ​​pierwszy wielokąt powinien być taki sam jak ostatni wielokąt. (Na przykład, aby wykreślić kwadratowy obiekt na mapie, wielokąty to 1,2,3,4,1.)

Kolejnym punktem walidacji danych jest punkt w wielokącie , który pomaga w znalezieniu punktów leżących poza wielokątem. Np. dla określonych współrzędnych dł-łac w mieście, jeśli punkt przecina wielokąt w liczbie nieparzystej, to znajduje się on wewnątrz wielokąta i jest prawidłowym punktem; w przeciwnym razie jest poza wielokątem i jest nieważny.

Format wymiany

Dostawcy map na ogół zbierają, agregują i dostarczają dane w dobrze zdefiniowanym i udokumentowanym formacie pliku, który jest specjalnie przeznaczony do wymiany informacji, np. Navteq używa Standard Interchange Format (SIF) i GDF , podczas gdy Tele Atlas używa zastrzeżonej formy GDF. Zwykle ma postać zwykłego tekstu ( ASCII ) składającą się z pól, które są łatwo analizowane i interpretowane przez różne strony, które się nim zajmują. Przenośny format umożliwia łatwe dodawanie, usuwanie i modyfikacje za pomocą prostych programów do edycji tekstu.

Do reprezentowania różnych typów danych używana jest niewielka liczba typów rekordów. Każdy typ rekordu składa się z sekwencji pól, które mają stałą długość lub są oddzielone znakiem interpunkcyjnym, takim jak przecinek. Na przykład encja łącza może być reprezentowana przez rekord formularza:

gdzie type1 definiuje to jako typ rekordu łącza, a etykieta służy jako identyfikator do odróżnienia tego łącza od wszystkich innych. Pola z1 i z2 określają pionową separację tego łącza od innych współdzielących odpowiednie węzły node1 i node2 . Na przykład wiadukt do łącza może być reprezentowany jako nie połączony z tym łączem. Inne typy rekordów są używane do reprezentowania informacji adresowych, punktów kształtu dla łącza, miast i stanów, interesujących miejsc (POI) itp.

Format wymiany dla bazy danych map nie jest dobrze zorganizowany do wykorzystania przez jednostkę nawigacyjną w czasie wykonywania. Rekordy są ułożone w dowolnej kolejności i dlatego trudne do wyszukiwania, a dane, takie jak nazwy ulic i wartości współrzędnych, są powtarzane od rekordu do rekordu. W rezultacie zawartość bazy danych jest reorganizowana do postaci binarnej, bardziej odpowiedniej do działania w czasie wykonywania.

Format czasu wykonywania

Formaty uruchomieniowe są zazwyczaj zastrzeżone, co uniemożliwia współpracę map między różnymi systemami nawigacji. Jednak nowa inicjatywa o nazwie Navigation Data Standard (NDS) to branżowe zrzeszenie producentów samochodów, dostawców systemów nawigacji i dostawców danych map, których celem jest standaryzacja formatu danych używanego w samochodowych systemach nawigacji. Zaangażowane firmy to TomTom , BMW , Volkswagen , Daimler , Renault , ADIT, Alpine Electronics , Navigon , Bosch , DENSO , Mitsubishi , Harman Becker, Panasonic , PTV, Continental AG , Navteq i Zenrin .

Baza danych jest reorganizowana przez dostawcę nawigacji w procesie kompilacji, który obejmuje co najmniej pięć następujących kroków:

1. Sprawdź spójność sieci. Na przykład upewnij się, że wszystkie pary węzłów, które powinny być połączone łączem, mają takie łącze i odwrotnie, wszystkie pary węzłów, które nie powinny być połączone, nie mają łącza łączącego.
2. Przypisuj identyfikatory (ID) wszystkim podmiotom w sposób systematyczny.
3. Zastosuj wiele zestawów indeksów do jednostek, aby ułatwić przeszukiwanie bazy danych w oczekiwany sposób.
4. Zastąp wielokrotne wystąpienia elementów danych (nazwy ulic, współrzędne itp.) indeksami w tabelach zawierających pojedynczą kopię każdego takiego elementu.
5. Zastosuj inne techniki kompresji, aby zmniejszyć całkowity rozmiar bazy danych.

Kontrola spójności w kroku 1 jest zwykle bardzo interaktywnym i powtarzalnym procesem, który może zająć tygodnie. W tym czasie rozbieżności muszą zostać wykryte, zbadane i rozwiązane.

W kroku 2 identyfikatory są zazwyczaj przypisywane sekwencyjnie, w miarę napotkania jednostek każdego typu. Wszelkie zmiany wprowadzone do wejściowej bazy danych z jednej wersji do drugiej wpłyną na przypisanie identyfikatorów do wszystkich podmiotów. W związku z tym nie ma wiele oczekiwań co do ciągłości przyporządkowania między wersjami.

W kroku 3 każdy zastosowany indeks pozwala na szybkie przeszukanie bazy danych w określony sposób. Jeden zestaw indeksów zastosowany do łączy można posortować według kolejności alfabetycznej nazw ulic łączy. Kolejny zestaw indeksów zastosowany do połączeń można posortować według węzłów, z którymi są połączone, aby ułatwić planowanie trasy. Jeszcze inny zestaw indeksów zastosowany do węzłów może być sortowany zgodnie z ich kolejnością pojawiania się na drodze. W niektórych z tych przypadków można przeprowadzić wyszukiwanie binarne zamiast wyszukiwania wyczerpującego, aw niektórych przypadkach proces wyszukiwania można zastąpić prostym wyszukiwaniem w tabeli.

Aktualizacja przyrostowa

Dla większości funkcji nawigacyjnych ważne jest posiadanie w pojeździe aktualnej bazy danych map, a dla niektórych funkcji ma to kluczowe znaczenie, zwłaszcza tych związanych z bezpieczeństwem aktywnym. Powszechną strategią jest przesyłanie informacji o aktualizacji do pojazdu, gdy tylko stają się one dostępne przez kanał bezprzewodowy. Kanał bezprzewodowy może być dwukierunkowy, taki jak Wi-Fi i telefon komórkowy, nadawczy , taki jak radio satelitarne, podnośna FM lub transmisja danych ATSC , lub kombinacja obu. W każdym razie przesyłanie całej nowej bazy danych w celu zastąpienia istniejącej wersji byłoby niepraktyczne lub skrajnie nieefektywne, ponieważ prawdopodobnie ma ona rozmiar kilku gigabajtów.

Zamiast tego pożądane jest przeniesienie tylko tych informacji związanych ze zmianami wprowadzonymi do istniejącej bazy danych. Główną trudnością jest to, że każda zmiana dokonana w zawartości bazy danych map generalnie powoduje zmiany we wszystkich przypisanych identyfikatorach jednostek i wszystkich przypisanych indeksach podczas procesu kompilacji. Te nowe identyfikatory i indeksy przenikają całą skompilowaną bazę danych, dzięki czemu każda kolekcja przyrostów będzie prawdopodobnie stanowić większość bazy danych. Aby przezwyciężyć tę trudność, zastosowano trzy podejścia, które są w skrócie 1) wbudowanym kompilatorem 2) sklepem podręcznym 3) kafelkami geograficznymi.

Wbudowany kompilator

W takim przypadku do pojazdu przesyłane są podstawowe zmiany wprowadzone w formacie wymiany bazy danych. Takie zmiany są reprezentowane w formie transakcyjnej składającej się z dodawania , usuwania i zastępowania . Zmiany te są stosowane do istniejącej pokładowej bazy danych w formacie wymiany. Format wymiany dla wbudowanej bazy danych może być przechowywany oddzielnie lub generowany w razie potrzeby przez „dekompilację” formatu czasu wykonywania. Połączona baza danych jest następnie kompilowana, co obejmuje przypisywanie identyfikatorów i stosowanie indeksów.

Ta wbudowana kompilacja będzie prawdopodobnie wymagała dużej mocy obliczeniowej i dużej ilości pamięci. Jednak nie musi być interaktywna i iteracyjna, jak to ma miejsce w przypadku kompilacji zewnętrznej, ponieważ sprawdzanie spójności i rozwiązywanie zostaną już wykonane. Co więcej, kompilacja na pokładzie może odbywać się w tle, więc czas obliczeń nie jest krytyczny.

Sklep Look-bok

W tym przypadku podstawowe zmiany są również przesyłane do pojazdu, ale są umieszczane w oddzielnej lokalizacji pamięci zwanej magazynem look-aside . Zmiany są również reprezentowane w formie transakcyjnej, ale mogą pojawić się w dowolnym dogodnym formacie, który niekoniecznie jest wymianą lub czasem wykonywania. Podczas działania jednostki nawigacyjnej, magazyn podręczny jest przeszukiwany przy każdym dostępie do głównej bazy danych. Następnie stosowane są wszelkie transakcje (zmiany), które dotyczą danych, do których uzyskano dostęp.

Konieczność badania pamięci podręcznej i wprowadzania zmian dla każdego dostępu do bazy danych oczywiście komplikuje algorytmy nawigacyjne i wydłuża czas ich obliczeń. Pozwala to jednak uniknąć konieczności stosowania wbudowanego kompilatora.

Kafelki geograficzne

W tym podejściu baza danych mapy jest podzielona na stosunkowo małe prostokątne regiony (kafelki), które tworzą teselację mapy. Rozmiar płytek jest rzędu 1 km z boku. Kafelki te są kompilowane osobno, dzięki czemu wszystkie identyfikatory i indeksy są uwarunkowane konkretnym kafelkiem, którego dotyczą. Kafelki, które uległy zmianie z powodu zmian podstawowych encji lub atrybutów w bazie danych, są przesyłane do pojazdu, gdzie zastępują odpowiedni istniejący kafelek.

Wymiana kafelków jest znacznie prostsza niż kompilacja na pokładzie lub korzystanie ze sklepu look-aside. Jednak może nie być wydajny w transmisji. Lokalna zmiana encji i atrybutów, niezależnie od zasięgu, wymaga przesłania całego kafelka zawierającego. Ponadto istnieją efekty krawędzi, w których zmiana jednostki w obrębie jednej płytki wpływa na jednostki w sąsiednich płytkach. Jest całkiem możliwe, że niewielka liczba zmian jednostek będzie wymagała transmisji prawie wszystkich kafelków, tym samym niwecząc cel aktualizacji przyrostowych. Problemy te można rozwiązać, wybierając rozmiar kafelka i częstotliwość aktualizacji.

Dołączanie danych pomocniczych

Różne funkcje nawigacyjne, w tym aktywne bezpieczeństwo, pomoc kierowcy i usługi oparte na lokalizacji, wymagają danych, które nie są uważane za część bazy danych map i są prawdopodobnie dostarczane przez dostawcę innego niż dostawca map. Takie dane muszą być powiązane z podmiotami i atrybutami głównej bazy danych. Jednakże, ponieważ dane pomocnicze niekoniecznie są kompilowane z główną bazą danych, potrzebne są inne środki do ustanowienia powiązań, co określa się jako dołączanie danych pomocniczych. Dwa popularne podejścia to tabele odniesienia specyficzne dla funkcji i odniesienia ogólne.

Tabele referencyjne specyficzne dla funkcji

Tabele odniesienia specyficzne dla funkcji zapewniają środki do dołączania danych specyficznych dla funkcji do bazy danych mapy tworzonej przez dowolnego uczestniczącego dostawcę. Taka tabela jest tworzona wspólnie w celu obsługi określonej funkcji lub klasy funkcji obejmujących usługę lokalizacyjną, aktywne bezpieczeństwo lub zaawansowaną pomoc kierowcy. Na ogół składa się ona z listy elementów mapy określonego typu (np. łączy, skrzyżowań, punktów POI itp.) wraz z atrybutami identyfikującymi (np. nazwy ulic, współrzędne długości/szerokości geograficznej itp.). Dodatkowo każdemu wpisowi w tabeli przypisywany jest unikalny identyfikator. Zestaw wpisów w tabeli wybiera się na ogół w drodze konsensusu wszystkich zainteresowanych stron. Z praktycznego punktu widzenia wynik będzie reprezentował mały podzbiór elementów danego typu, które są dostępne w bazach danych map i będzie składał się z tych, które są ważniejsze dla obszaru zastosowania. Po sformułowaniu tabeli zadaniem każdego uczestniczącego dostawcy jest określenie i odniesienie do elementów w swojej bazie danych mapy, które odpowiadają wpisom w tabeli.

Rysunek 2: Lokalizacje TMC w Metro Detroit

Szeroko stosowanym przykładem jest standard TMC dotyczący tabel kodów lokalizacji do odwoływania się do danych o ruchu. TMC, co oznacza Traffic Message Channel , jest częścią Systemu Danych Radiowych (RDS), który jest zaimplementowany jako modulacja podnośnej komercyjnego sygnału rozgłoszeniowego FM. Tabele TMC zapewniają przede wszystkim odniesienia do lokalizacji punktów wzdłuż głównych dróg odpowiadających skrzyżowaniu z innymi drogami. Wpis w tabeli identyfikuje lokalizację punktu przy użyciu zarówno informacji kontekstowych (takich jak region, droga i odcinek drogi, nazwa skrzyżowania), jak i przybliżonych współrzędnych długości/szerokości geograficznej.

Identyfikatory przypisane do wpisów w tabeli są 16-bitowymi liczbami całkowitymi, a zatem mają zakres 65536 wartości. Jest to zbyt mało, aby objąć cały świat, dlatego dla każdego kraju lub regionu kraju formułuje się osobne tabele. W przypadku danego regionu metropolitalnego uwzględniane są tylko skrzyżowania wzdłuż autostrad, arterii i niektórych głównych dróg. Ilustruje to poniższy rysunek dla obszaru miejskiego Detroit. Pokrycie jest przeznaczone do dostarczania informacji o ruchu drogowym na drogach o dużym natężeniu ruchu. Z drugiej strony, planowanie tras oparte na ruchu wymaga pokrycia wszystkich lub prawie wszystkich głównych dróg, a zatem nie jest odpowiednio wspierane przez tabele kodów lokalizacji TMC w obecnym kształcie.

Ogólne odniesienia

Ogólne odniesienia to próba dołączenia danych do dowolnej bazy danych map poprzez odkrycie informacji referencyjnych za pomocą formy dopasowywania map. Elementy danych specyficzne dla funkcji są przypisywane do elementów, takich jak punkty, łącza lub obszary, które prawdopodobnie tylko przybliżają odpowiednie elementy mapy w określonej bazie danych map. Przeszukuje się bazę danych map w celu uzyskania najlepszego dopasowania. Aby usprawnić proces wyszukiwania, sąsiednie elementy są strategicznie dołączane do każdego danego elementu, aby zapewnić znalezienie prawidłowego rozwiązania w każdym przypadku. Na przykład, jeśli element mapy jest łączem łączącym dwa skrzyżowania, na potrzeby wyszukiwania można dołączyć jedną lub obie ulice poprzeczne. Mamy nadzieję, że to sprawia, że ​​nieprawidłowe dopasowanie jest mało prawdopodobne. Chociaż procedura jest dość heurystyczna, proponowany standard o nazwie Agora określa strategię wyboru sąsiednich elementów do dołączenia.

Europejskie konsorcjum ActMAP

Europejskie konsorcjum o nazwie ActMAP (Aktualizuj mapę) (w ich słowach) „opracowuje znormalizowane mechanizmy aktualizacji istniejącej zawartości bazy danych map i umożliwia dynamiczne dołączanie informacji do cyfrowej mapy w pojeździe”. W skład konsorcjum ActMAP wchodzą ERTICO (koordynator), BMW, CRF Fiat Research Centre, DaimlerChrysler, Navigon, Navteq, Tele Atlas i Siemens VDO Automotive. Zakończyli większość swojej pracy i opublikowali szereg raportów, które zostały przedłożone komitetowi ISO TC204 WG3 w celu standaryzacji. Ich raporty służą jako dobry punkt wyjścia i odniesienie do pracy nad tym projektem. Ważną kwestią, którą zajmują się ich raporty, jest radzenie sobie ze złożonością wielu dostawców map, przy użyciu zastrzeżonych formatów, w połączeniu z wieloma dostawcami danych i wieloma wersjami map w pojazdach. Rozwiązują to za pomocą otwartego formatu mapy pośredniej wyrażonej w XML i opartej na koncepcjach standardu ISO GDF 4.0. Wszystkie modyfikacje bazy danych dostawcy są najpierw konwertowane do tego formatu pośredniego, przechowywane na serwerze, a następnie konwertowane do każdego formatu używanego w poszczególnych pojazdach. Zakładają, że każdy samochód ma mapę „bazową” od dostawcy map i że ta linia bazowa definiuje identyfikatory odniesienia (np. identyfikator segmentu mapy) dla większości funkcji, które mają być aktualizowane. W przypadku obiektów bez identyfikatora odniesienia w linii bazowej proponują użycie „ogólnego” odniesienia, które jest wykrywane heurystycznie za pomocą dopasowywania map zgodnie z proponowanym standardem o nazwie AGORA

Głównym problemem nierozwiązanym bezpośrednio przez ActMAP jest to, że dla każdej nowej wersji bazy danych map dostawcy wszystkie identyfikatory referencyjne są zwykle ponownie przypisywane w procesie kompilacji, co niszczy wszelką korespondencję z identyfikatorami z poprzednich wersji. To poważnie zakłóca możliwość korzystania z aktualizacji przyrostowych w celu wygenerowania nowej wersji bazy danych mapy z poprzedniej wersji. Kolejną kwestią nierozwiązaną przez ActMAP jest brak możliwości odniesienia i scharakteryzowania pododcinków odcinków dróg (np. zakrętów, wzniesień, pasów manewrowych itp.) w celu ich aktualizacji.

Zobacz też

• Samochodowy system nawigacji
• Problem najkrótszej ścieżki , klasa problemów i algorytmy służące do uzyskania trasy nawigacyjnej z bazy danych map.
• Baza danych geograficznych
• System informacji Geograficznej
• Globalny system nawigacji satelitarnej
• Inteligentny system transportu
• Mapa
• Navteq
• Punkt zainteresowania
• Obiektowo-relacyjna baza danych
• Otwarte Konsorcjum Geoprzestrzenne
• Mapowanie robotów
• Tele Atlas
• Telematyka

Bibliografia