一種用於結構化導航資料庫的技術的製作方法

2023-05-01 19:59:31

專利名稱：一種用於結構化導航資料庫的技術的製作方法
技術領域：
本發明總體涉及導航資料庫。本發明尤其涉及一種將導航資料庫中的數據進行結構化的技術。
背景技術：
現有技術的導航設備提供了有關行駛路線、在所計算出的路線附近或在設備位置附近的興趣點(POI, Point Of Interest)、城市的名稱、街道或建築物、交通信息等等的大量有用信息和搜索選項。根據導航系統將要提供的服務，導航設備在它們的資料庫中存儲大量的導航數據，這些導航數據與例如路線、地圖顯示、目的地條目、Ρ0Ι、交通信息相關聯。當基於用戶的輸入和所存儲的導航數據計算路線時，路線算法必須能夠在導航資料庫中尋址到對路線計算有用的所有可能的路線鏈路，並能夠將所計算出的路線存於導航設備的主存儲器中。因此，為了從大量的所存儲的導航數據中訪問到特定的導航數據，需要一種尋址方案。一般來說，所使用的尋址方案與資料庫中的數據結構化緊密相關。現有技術的導航資料庫(例如，符合導航數據標準(NDS)存儲格式的導航資料庫)使用全局切片方案(global tiling scheme)來進行導航數據尋址。將參照圖1和圖2來更詳細地說明依照NDS的數據結構和尋址方案。如圖1a所示，NDS為路線數據提供了 16個數據級別(參見圖1a中的x軸:最高的數據級別標記為級別0，最低的數據級別標記為級別15)。特定的數據級別被分配給了表示具有特定道路功能分類(FC，functional class)(即符合道路國際分類標準的FCl到FC4道路)的道路的路線數據。在本文中，NDS將級別13限定為基準級別，其包含從FCO到FC4道路的路線數據。因而，級別13包括從公路到局部小路的整個道路網絡，並因此具有最高的道路網絡解析度。進一步如圖1a所示，道路網絡解析度隨著級別編號的降低而連續降低。例如，數據級別10、9、8和6僅僅與FCO到FC3道路、FCO到FC2道路、FCO到FCl道路(對應於僅僅由公路組成的道路網絡)和FCO道路分別相關聯(參見圖1a中的叉號)。為了清楚起見，應該注意，並不是所有由NDS支持的級別都需要提供在資料庫中。在圖1a所示的實施例中，僅級別6、8、9、10和13與路線數據相關聯。每個NDS都具有它自己基礎的全球切片結構。切片表示在全局坐標系統下具有預定尺寸的矩形地域。每個級別的切片結構來自於全局切片方案，該全局切片方案將通過參考圖2a來作簡要討論。對於級別0，地球的表面被劃分為兩個切片，一個切片覆蓋0°到+180°的經度線的地球表面(圖2中的切片I)，一個切片覆蓋0°到-180°的經度線的地球表面(圖2中的切片2)。對於之後的級別1，兩個切片各自被分割成四個切片(在圖2中僅示出了針對切片2的分割)。級別I中的每個切片被再次分割成用於級別2的四個切片(參見陰影區域)，依此類推。該等級分割方案在所有級別中持續直到基準級別。更一般地說，對於級別k，其中k = 0，1，2，...，15，會產生2(2K+1)個切片。當級別O僅包括兩個覆蓋整個地球的表面的切片時，227個切片被提供給結構化的基準級別13，其中，每一個切片覆蓋大約2.5kmX 2.5km的矩形地域。
在圖1b和Ic中，針對NDS級別9，示例性地說明了 NDS數據級別的NDS子結構化。圖1b示出了四個切片201、203、205、207，它們覆蓋了在「慕尼黑」周圍的局部地域(見橢圓形投影區域)。此外，路線鏈路LI至L8表示城市道路網絡的一些道路，該城市道路網絡以如下所示的方式被組織在相應的導航資料庫中(參見包括圖1c中德國地理區的導航資料庫)。切片201的路線鏈路L2、L8(參見圖1b)被存儲在一個切片標識符為T-1D10111的切片塊中，路線鏈路L3、L4和L5在另一個具有T-1DlOl 12的切片塊中，路線鏈路LI在具有T-1DlOl 13的切片塊中，路線鏈路L6、L7在具有T-1DlOl 14的切片塊中(請注意，NDS存儲了延續到切片的切片邊界的路線鏈路，在這些切片邊界中，路線鏈路具有它們的起點)。同樣，基本的地圖顯示數據也可以按照基礎的切片結構組織起來。NDS使用全局T-1d來尋址切片內的各個路線鏈路。T-1D的結構與在NDS系統中使用的地理坐標系統的編碼有密切的聯繫，並且如圖2a和2b所示。經度和緯度坐標(X-和y_坐標)分別用32比特的整數和31比特的整數來表示。因此，NDS的坐標單位對應經度和緯度的90/23°度(注意比例因子23°)。通過使用Morton (莫頓)映射，經度的整數值和緯度的整數值被進一步映射成單個的整數值。所接收到的Morton碼表示從對經度的32比特的整數和緯度的31比特的整數進行比特交織接收到的63比特的整數。另一方面，針對級別K，地理坐標系統被劃分為2(2k+1)個切片。級別K中給定的切片的切片編號可以從存在於該切片中的坐標的Morton碼的最高有效2k+l比特推斷出來。因此，需要2K+1個比特數來對級別K內的單個切片進行明確的尋址。因此，需要至少27個比特來級別13的切片進行尋址。為了進一步區分不同級別的切片，需要另外的尋址比特。如圖2b所示，NDS中的每個T-1D由級別編號和切片編號組成。對於具有如圖1a-1c所示的級別和切片結構的導航資料庫，需要32比特的ID來對每個任意級別的切片進行明確的尋址，32比特數的ID是必需的。此外，NDS建議用16比特的路線鏈路標識符(L-1D)來尋址每個切片中的路線鏈路。因為NDS不區分具有高密度和低密度的路線鏈路(例如，覆蓋大城市的切片可能包括大量的路線鏈路，而覆蓋山脈(例如，喜馬拉雅山)或海洋的切片可能包括少量的路線鏈路(例如，表示渡輪連接的鏈路)，或者該切片也可能是空的)的切片，所以這種消耗內存的L-1D是必需的，以為了用來尋址每個特定切片中所有可能的路線鏈路。總之，消耗內存的48比特的ID是必需的，以便在NDS中尋址單個路線鏈路。

發明內容
本發明的目的是提供一種更靈活的資料庫結構，用於有效地尋址(address)導航數據。根據本發明的一個方面，提供了一種結構化導航資料庫的方法；其中所述導航資料庫至少包括用於預定地理區域的路線鏈路數據，所述方法包括以下步驟:將與所述預定地理區域相關聯的路線鏈路數據組織成至少一個路線集群；為所述至少一個路線集群提供集群標識符；以及將所述至少一個路線集群與所述集群標識符一起存儲到所述導航資料庫中。所述「預定地理區域」可以對應於由地圖或導航數據提供者所提供的任何(各個)地理區域。它可以包括較小或較大的地理上和/或行政上屬於一起的區域。例如，(聯邦)州、國家、國家群和/或單個大陸或大陸的一部分，例如可以是指北美、中東、南歐、西俄羅斯等。這裡給出的技術可以在NDS環境(如在背景技術部分中所描述的NDS環境)中實施，也可以在任何其它專用或通用的導航數據中和/或地圖標準中實施。因此應當理解的是，當本文中使用NDS特定表達時，該表達不應解釋為局限於NDS實體，而應當包括任何其它標準的相應實體。該方法可以進一步包括為所述導航資料庫提供用於尋址所述至少一個路線集群的至少一個索引結構。所述至少一個索引結構可以以索引樹的形式提供(任選地，以B樹/B+樹的形式)。所述至少一個索引結構可以包括集群標識符。經由所述至少一個索引結構，可以訪問資料庫的每個路線集群和/或路線鏈路。所述預定地理區域可以被進一步劃分成切片。切片可以表示所述預定地理區域的局部地域。換句話說，切片可以表示被設計用來無間隙地覆蓋整個預定地理區域的具有預定尺寸和預定形狀(例如，40kmX40km的矩形區域)的局部地域。形狀和尺寸可以取決於用於劃分的切片方案。可以設想，類似的切片方案可以用在NDS中。根據另一種實現方案，以上提及的NDS切片方案可以用來劃分預定地理區域(並用來劃分與預定地理區域相關聯的導航資料庫中的導航數據)。依然根據另一種實現方案，一種具有局部切片標識符(局部T-1D)的局部切片方案可以用來劃分預定地理區域(並用來劃分與預定地理區域相關聯的導航資料庫中的導航數據)。與給定的切片相關聯的路線鏈路(以及任選地，相應切片的其它導航數據，例如基本的地圖顯示數據、目的地條目數據等)可以被組織成至少一個路線集群。換句話說，覆蓋預定地理區域的每個切片可以被提供有不同的路線集群。與所述路線集群相關聯的至少一個索引結構以獨立於所述切片結構的方式被組織。換句話說，該索引樹可以依照路線集群結構來組織，且與資料庫內的切片結構無關。至少一個索引結構可以(僅)包括所述集群標識符(以及任選地，路線鏈路標識符)，經由該集群標識符可以引到每個集群。與路線集群相關聯的索引結構可獨立於與可能的資料庫切片結構相關聯的可能的索引結構。因此，用於對切片進行尋址的索引結構可以與對集群(和路線鏈路)進行尋址的索引結構無關。因此，該資料庫可以提供有兩套不同的尋址方案，一套用於切片尋址，另一套用於路線鏈路尋址(或其它導航數據尋址)。每個路線集群可以提供有靈活數量的路線鏈路。然而，每個路線集群可以提供有至少一個路線鏈路。不具有鏈路的路線集群可能不存在於資料庫中。每個路線集群可以代表資料庫子結構，該資料庫子結構包括存儲於存儲區的靈活數量的路線鏈路。在每個集群內的路線鏈路可以被組織成數據表(也就是路線鏈路表)。此數據表可以是關係表。與之前相反的是，可以存在不具有路線鏈路(和/或其它導航數據)的空的切片。切片的大小和數量可以僅取決於應用於對基礎的預定地理區域進行劃分的切片方案。空的切片可以沒有路線集群。每個集群的路線鏈路的數量不會超過(給定的)上限閾值。該上限閾值可以為任意值。小的閾值可以用來將每個集群的路線鏈路的可能的最大數量(即，集群的大小)保持得很小。
所存儲的路線集群的數量也可以是靈活的。集群的數量可取決於需被組織的資料庫中的路線鏈路數據的量。其可取決於用於預定地理區域的整個數量或路線鏈路密度。任選地，集群的數量可由上限閾值所限制。在劃分切片的情況下，所產生的每個切片的路線集群的數量可能取決於切片的路線鏈路密度。換句話說，具有大量路線鏈路的切片可包括比具有少量路線鏈路的切片相對較多的路線集群。因此，路線集群的數量可根據每個切片中路線鏈路的數量分別進行調整。所產生的路線集群的數量可與路線鏈路密度成正比。可以設想，所產生的集群可能完全填滿了路線鏈路(假設集群的大小受上限閾值的限制)，並且僅當所產生的集群被完全填滿時，才產生新的集群。或者，所產生的集群僅被路線鏈路數據部分填滿。該方法可以進一步包括以下步驟:將被組織在至少一個路線集群中的路線鏈路數據重新組織成至少一個新的路線集群，並將所述至少一個新的路線集群存儲到資料庫中。該新的路線集群可進一步提供有集群標識符。路線鏈路數據的重新組織可以在資料庫更新過程中進行。其可包括將在更新過程中新增到資料庫中的路線鏈路數據組織到新的路線集群和/或已有的路線集群中。其也可以包括將已有的路線集群中的已有路線鏈路分配給其它已有的或新產生的集群。所述至少一個索引結構可以根據新的集群配置進行適當的調整。因此，重新組織可以提供一種在資料庫內有效的路線鏈路組織。導航數據更新可包括整個資料庫的導航數據更新，或與一個或幾個切片相關聯的導航數據的更新(增量更新)。對於「切片式資料庫」，可基於單個切片更新來進行增量更新。在這種情況下，與將要更新的切片相關聯的路線鏈路數據和路線集群可以以如上所述的方式進行重新組織。所述至少一個路線集群可以提供有標識符(集群標識符)。該標識符可以是永久性標識符。該永久性標識符可能意味著標識符在(增量)資料庫更新過程中保持不變。新的集群可以提供有新的集群標識符。永久性標識符可以確保:在增量資料庫更新之後，路線集群和/或路線鏈路仍然可以訪問到，而無需更新整個索引結構。所述至少一個路線集群內的每個路線鏈路可以提供有鏈路標識符。該鏈路標識符可以是可變的鏈路標識符。該鏈路標識符可以對應於鏈路編號，該鏈路編號用於表示鏈路表內路線鏈路的順序。「可變的鏈路標識符」可能意味著路線鏈路順序可以隨著如上所述的路線鏈路的重新組織而發生改變。路線鏈路標識符的大小(即比特數大小)可由表示可組織在集群內的路線鏈路的最大數量的上限閾值所決定。路線鏈路標識符的大小可確定集群的大小。因此，可將路線鏈路標識符的上限閾值以及比特大小保持得很小從而將路線鏈路尋址空間保持得很小。換句話說，路線鏈路標識符的比特數大小可以採用預定(小)值。小比特數的路線鏈路標識符可能在「切片式資料庫」中尤其有利。可很容易地對在一個或幾個可尋址的路線集群內僅具有少量路線鏈路的切片的路線鏈路進行組織或尋址，而通過簡單地增加每個切片的路線集群的數量，可對大量的路線鏈路進行組織和尋址。因此，可尋址的路線集群的數量可以根據需被尋址的路線鏈路(或者通常的導航數據)的數量來(動態地)調整。集群標識符的比特數大小可以這樣選擇:以使每個所產生的路線集群能夠通過其所分配的集群標識符被分別地尋址到。集群標識符的大小可根據路線鏈路標識符的大小進行調整。如果路線鏈路標識符的比特數大小很小，則可增大集群標識符的大小(因為不得不產生並尋址更多的集群)，反之亦然。在為導航數據尋址提供預定的比特數大小的尋址方案中，可以從用於導航數據尋址的預定的比特數大小和(所選擇的)路線鏈路標識符的大小之間的差值得到集群標識符。通過訪問對應的集群標識符(其中組織有路線鏈路)和對應的路線鏈路標識符可以訪問導航資料庫中的每個路線鏈路。通過對應的索引結構可以直接訪問路線集群和/或該集群中的路線鏈路。因此，路線數據的訪問可與固定的切片結構無關。該導航資料庫還可以包括以下項目中的至少一種:地圖顯示數據、目的地條目數據、POI數據，TMC數據和其它增強型導航數據。以下項目中的至少一種:地圖顯示數據、目的地條目數據、POI數據、TMC數據和其它增強導航數據，可以被組織成可變的導航數據集群。增強型導航數據可以是，例如，正射影像數據(orthoimage data)、三維數據、語音數據、全文本搜索數據(full textsearch data),數字地形模型數據等等。還提供一種電腦程式產品，其具有:當電腦程式在計算機設備上執行時，用於實施這裡所述的結構化技術的程序代碼。為此，該電腦程式產品可以被存儲在一種計算機可讀記錄介質上(例如，存儲卡或只讀存儲器)。還提供一種導航資料庫，該導航資料庫至少包括用於預定地理區域的路線鏈路數據，其中對於所述預定地理區域而言，所述導航資料庫包括帶有集群標識符的用於組織所述路線鏈路數據的至少一個路線集群。該導航資料庫還可以包括含有集群標識符的至少一個索引結構，通過該至少一個索引結構能夠訪問至少一個路線集群和/或該至少一個路線集群內的路線鏈路。該集群標識符可以是永久性標識符，該永久性標識符在(增量)數據更新過程中保持不變。所述至少一個路線集群可以是靈活的路線集群，其包含可變數量的路線鏈路。所述至少一個路線集群內的路線集群可被組織成(有關係的)路線鏈路表。在該表中的每個路線鏈路可提供有路線鏈路標識符。該路線鏈路標識符可以與路線鏈路表內的路線鏈路的順序編號所對應。路線鏈路的順序是可變的。換句話說，在(增量)更新之後路線鏈路的順序可能發生變化。集群的大小是可變的。集群的大小可以由被組織在集群內的路線鏈路的數量所決定。每個集群中路線鏈路的最大數量不可超過上限閾值。所述閾值可以這樣選擇:以使能夠使用相應的存儲路線鏈路標識符的存儲器。該導航資料庫可以被進一步劃分成切片。與單個切片相關聯的路線鏈路(以及任選地，其它導航數據)可以被組織成集群。還提供一種導航設備，其包括與上述導航資料庫一致的導航資料庫。


通過以下附圖給出本文描述的該公開的進一步的細節、優點和方面，其中:圖1a-1c示意性地示出了根據現有技術的導航資料庫結構的結構化；圖2a_2b示意性地示出了根據現有技術的一種尋址方案；圖3示意性地示出了根據本發明的一個實施例的一種導航設備；圖4a_4b示意性地示出了根據本發明的一個實施例的導航資料庫的結構化；圖5示出了 一個方法實施例的流程圖6a_6b示意性地示出了根據本發明的一個實施例的一種尋址方案。
具體實施例方式在下面的描述中，為了解釋而不是限制的目的，給出了特定的細節，例如特定的導航資料庫結構和特定的信令場景，以便提供本公開的詳細了解。對於本領域的技術人員來說顯而易見的是，在此描述的技術可以在脫離這些特定細節的其它實施例中實施。例如，可以很容易地在NDS資料庫標準中執行在此說明的方法、步驟和功能。本領域的技術人員可很容易認識到，所說明的方法、步驟和功能獨立於NDS的數據級別結構和特殊的依賴於級別的切片設計。所說明的方法、步驟和功能也可以應用於其它的導航數據或地圖數據標準的環境中。本領域技術人員還將理解到在此說明的方法、步驟和功能，可以通過使用單獨硬體電路、使用與程序化的微處理器或者通用計算機結合的軟體功能、使用一個或多個專用集成電路(ASIC)、一個或多個數位訊號處理器(DSP)和/或一個或多個現場可編程門列陣(FPGA)來執行。還應當理解的是，在此公開的方法、步驟和功能可以嵌入在處理器內和聯接到處理器的存儲器中，其中所述存儲器存儲一個或多個程序，當處理器執行該一個或多個程序時，該一個或多個程序控制該處理器實施在此討論的步驟。參照圖3至圖5，將更詳細地描述本公開的示例性實施例的原理。圖3示出了與伺服器40通信的導航設備10的實施例。導航設備10包括導航資料庫20，其導航數據根據本公開進行結構化。資料庫的結構化和導航數據的尋址將在下面參照圖4、5和6來更詳細地描述。設備10還包括處理單元12、位置傳感器14、輸入/輸出(I/O)模塊16、主存儲器18、以及通信模塊22。所述位置傳感器14被配置為接收來自定位系統(如全球定位系統(GPS)、伽利略或其它系統)的位置坐標。所述I/o-模塊16表示一方面的導航設備10和另一方面的用戶之間的接口。它可以包括光學和/或聲學裝置，用於輸出所計算出的或所搜索到的導航信息(例如，所計算出的路線的光學和/或聲學輸出)。所述主存儲器18被配置為對輸入數據、通過所述通信模塊22接收的數據和/或從資料庫20載入的用於由處理單元12進一步處理的導航數據進行緩衝。所述處理單元12被配置為根據預先存儲在導航設備10中的程序或(子)例行程序，來協調和處理從通信模塊接收的數據(例如，更新數據)、需通過通信模塊傳輸的數據(例如，更新請求)、位置傳感器14的數據、I/O模塊16的數據和/或所述導航資料庫20的數據(圖3中的箭頭)。通信模塊22被配置為支持與外部設備的無線和/或有線通信，所述外部設備例如為導航伺服器40和/或其它的導航設備，用戶終端(智慧型手機，PDA等)。通信模塊可包括至少一個無線電模塊(圖3中未示出)，用於支持UMTS和GPRS通信中的至少一個。伺服器40被配置為嚮導航設備提供導航數據。該伺服器包括數據倉庫42、處理單元44以及通信模塊46。數據倉庫42被配置為存儲與各個州、國家、大陸或其它地理區有關的至少最新版本的導航數據。該倉庫也可以存儲以前版本的導航數據。導航數據可包括以下項目中的至少一種:路線數據、地圖顯示數據、目的地條目數據、興趣點(POI)數據、TMC數據和其它增強型導航數據。數據可以以模塊化的方式進行存儲。比如，以下項目中的至少一種:路線數據、目的地條目數據、地圖顯示數據、POI數據、TMC數據和其它增強型導航數據，每個都可以以數據集群的形式存儲。也可以設想該集群可與切片相關聯，以支持切片結構化的導航資料庫的增量數據更新。此外，倉庫42可以包括指示導航內容版本的版本數據。導航數據可以進一步包括被配置為訪問單個導航數據(即，路線鏈路集群，地圖顯示集群，等)的索引結構。伺服器40可以被進一步配置為執行導航數據結構化，下文將會結合圖4對此進行更詳細的說明。為此，伺服器可以包括至少一個控制處理單元44執行結構化步驟(該步驟將在下面討論)的程序(存儲在伺服器存儲器(未在圖3中示出)上)。處理單元44可以被進一步配置為控制從通信模塊46到數據倉庫42的數據業務量，反之亦可。換句話說，通信模塊可以被配置為給導航設備提供更新信號，以響應於通過通信模塊46從導航設備10接收的更新請求30。根據更新請求，處理單元44可提供包括所更新的導航數據的更新信號32，該所更新的導航數據是根據導航資料庫20的數據結構以及所更新的索引數據進行結構化的。所述更新信號32可以包括數據集群形式的導航數據。根據一個實施例，數據集群可與各個切片相關聯。數據信號可以包括導航資料庫20的全部更新或增量更新(即基於單個切片)。參考圖4到圖6，本文對導航資料庫20的結構化和尋址進行了更詳細的說明，其中，導航資料庫20至少包含用於預定地理區域的路線鏈路數據。如上面已經描述的那樣，可以設想導航數據結構化由導航數據提供者(例如，圖3中的伺服器40)來執行。當導航設備10包含有相應的預存的程序時，則導航數據結構化由導航設備10來執行也是可能的。圖4a和4b顯示了根據本發明的一個實施例的資料庫結構化的示意圖。為了清楚起見，圖4a只顯示了與較大預定區域相關聯的部分導航資料庫內容的路線鏈路數據。為了比較，示出了與圖2a中一樣的在慕尼黑周圍的相同地理區域(因此，具有相同的路線鏈路數據)。該地理區域部分被劃分成了切片。在本文中，可以使用與NDS中使用的全局切片方案類似的局部或全局切片方案。但是，本公開不依賴於與由資料庫內容表示的預定區域的切片有關的細節。將參照圖4B和圖5來闡述資料庫的結構和結構化。在第一步中，每個預定地理區域的切片的路線鏈路數據都被組織成至少一個路線集群。並且，每個路線集群都提供有唯一的集群標識符。例如，如圖4b所示，切片203的路線鏈路L2b、L4、L3、L5、L6a被組織成兩個獨立的路線鏈路集群，相對應的集群標識符(C-1D)是C-1D100和C-1DlOl。顯然，在圖4b中給出的C-1D值僅僅是示例性的數值。該集群標識符通常通過預定的比特值來給定，並且後文將會對該集群標識符進行更詳細地討論。同樣地，路線鏈路Llb、L2a和L8被組織成兩個獨立的集群，它們的C-1D分別為102和103。儘管未在圖4b中示出，與切片205和207相關聯的路線鏈路也被分別組織成至少一個路線集群。因此，路線集群表示了資料庫20的資料庫子結構，該資料庫子結構與唯一的標識符相關聯。在接下來的步驟中，所產生的路線集群及其相應的所提供的集群標識符被存儲到導航資料庫20中。該導航資料庫還包括含有集群標識符的至少一個索引結構。該至少一個索引結構被配置為提供通向路線集群和/或路線集群的路線鏈路的(直接)訪問。例如，B樹可用於集群和/或路線鏈路，參考B樹，葉節點包括路線集群ID。索引結構可以與所述路線數據分開存儲(以及，任選地，與其它導航數據分開存儲)。所述導航資料庫20還包括基本的地圖顯示數據，目的地條目數據和POI數據。在示例性實施例中，基本的地圖顯示數據和目的地條目數據(對每個切片而言)也被組織成數據集群。例如，切片203包含地圖顯示集群305和目的地條目數據集群，該地圖顯示集群305和目的地條目數據集群分別包括地圖顯示數據，以及下一個有效字符(NVC，Next ValidCharacter)數據和命名對象數據(Named Object data)。因此,正如圖4a中所劃分的部分M1、M2、M3、M4示意性所示，對於每個切片的路線數據、基本的地圖顯示數據和目的地條目數據被單獨地組織成至少一個數據集群。當然，路線鏈路數據、目的地條目數據和/或基本的地圖顯示數據也可以以獨立於基礎的切片方案的方式被組織成集群。例如，幾個切片的路線鏈路可以組織成單個路線集群。此外，POI數據可以以獨立於基礎的切片方案的方式被組織成POI集群。與預定地理區域相關聯的POI數據可根據POI的分類進行組織。例如，表示餐館的POI數據可被組織成至少一個POI集群，其中表示藥房的POI數據可被存儲在至少另一個POI集群裡。所存儲的路線集群(和其它導航數據集群)表示可尋址的數據子結構，該可尋址的數據子結構可以通過相應的索引結構而被直接訪問(通過導航應用)。基礎的切片結構不會影響導航數據尋址方案以及訪問。所述切片結構可只用於支持導航資料庫20中的增量更新(即基於單個切片的導航數據的置換或更新)。參照圖6的路線集群的結構及與其相關聯的結構，下面討論一種路線鏈路的尋址方案。在下文中，假設導航資料庫20具有用於支持增量更新的切片結構。圖6a顯示了導航資料庫20的兩個示例性的切片301、302，以及路線鏈路，該路線鏈路表示與兩個切片301、302都相關聯的道路網絡。切片301中的路線鏈路被進一步組織成三個路線集群61、62、63，路線集群61、62、63與集群標識符(C-1D) 110、111、112相關聯。詳細地說，集群61包括路線鏈路la、lb，集群62包括路線鏈路2a和2b，以及集群63包括路線鏈路3a和3b。類似地，切片302中的集群64包含路線鏈路4a-4e。與切片301、302相關聯的路線鏈路和/或路線集群被靈活地組織。雖然切片302隻包括可被容易地組織成單個路線集群的少量路線鏈路，但是切片301卻包括了被組織成三個路線集群的較大數量的路線鏈路。很顯然，本示例僅用於說明根據本發明的靈活的路線鏈路集群化的原理。集群的數量和每個集群的路線鏈路的數量可分別隨切片和集群的變化而變化。可根據路線鏈路組織方案來進行組織。例如，可以設想表示橫越切片邊緣的道路或道路部分的路線鏈路被集群到單個集群裡。也有可能的是，具有特定道路功能分類的路線鏈路可被存儲在集群裡。獨立於該組織細節，每個路線鏈路集群都提供有C-1D，且集群裡的每個路線鏈路還提供有路線鏈路標識符(L-1D)。例如，L-1D可以是集群內路線鏈路的位置編號。因此，每個路線鏈路可通過路線所屬的集群的C-1D和相應的L-1D來進行尋址。例如，可以使用24比特的C-1D來尋址路線集群，且可以使用8比特的L-1D來尋址每個集群裡的路線鏈路。在這種情況下，可使用224個集群標識符，這是一個用於在導航資料庫中對可能的集群進行尋址的足夠大的數。此外，在每個路線集群裡可以尋址到28個路線鏈路。總之，僅需要24比特+8比特來進行路線鏈路尋址，而不需要像使用死板的全局切片方案的NDS那樣使用48比特。當然，根據資料庫的數據數量，C-1D和/或L-1D可以具有其它比特值。然而，由於路線集群僅是針對路線鏈路組織而產生的且集群的數量與集群的大小(由所提供的L-1D的大小來確定)成比例，因此，集群的數量和集群標識符的大小可被保持得很小，從而使得導航數據尋址更有效。圖6b顯示了(增量)更新之後的切片301和302。如圖所示，在兩個切片301、302中，加入了新的路線鏈路(ld、5a-5c)。根據靈活的集群化方案，新的道路可以被組織成新的集群65 (針對切片302示出)或者被添加到已有的集群(集群61、63)中。因此，集群61可能被重新組織，並且集群的路線鏈路Ia-1c可能提供有新的L-1D。此外，由於路線配置的改變，已有的路線集群可以被修改(如果合適的話)。例如，在重新組織的過程中，集群62被刪除並且集群62的已有的路線鏈路2a與2b被添加到已有的集群61和63中(鏈路Ic和3c)。因此，對於每個切片，根據路線鏈路密度和/或路線性能，動態地生成、重新組織和/或刪除集群。這種靈活的路線鏈路和集群組織的優勢是集群的數量能夠被保持得很小。因此，相對於死板的尋址方案，集群標識符的尺寸也可以更小。因此，為導航數據的尋址提供了一種消耗更少內存的尋址方案。
權利要求
1.一種結構化導航資料庫(20)的方法，其中，所述導航資料庫(20)至少包括用於預定地理區域的路線鏈路數據，所述方法包括以下步驟: 將與所述預定地理區域相關聯的路線鏈路數據組織成至少一個路線集群； 為所述至少一個路線集群提供集群(61、62、63、64)標識符；以及 將所述至少一個路線集群(61、62、63、64)與所述集群標識符一起存儲到所述導航資料庫(20)中。
2.按權利要求1所述的方法，進一步包括:為所述導航資料庫(20)提供用於尋址所述至少一個路線集群(61、62、63、64)的至少一個索引結構。
3.按權利要求1或2所述的方法，其中，所述預定地理區域被進一步劃分成切片(301、302)，其中，對每個切片來說，所述組織的步驟包括將與所述切片(301、302)相關聯的路線鏈路數據組織成至少一個路線集群(61、62、63、64)。
4.根據結合權利要求3的權利要求2所述的方法，其中，與所述路線集群(61、62、63、64)相關聯的所述至少一個索引結構以獨立於切片結構的方式被組織。
5.根據權利要求1所述的方法，其中，每個路線集群(61、62、63、64)都提供有至少一個路線鏈路。
6.根據權利要求1所述的方法，其中，被組織在所述至少一個路線集群出1、62、63、64)中的路線鏈路的數量不超過上限閾值。
7.根據權利 要求1所述的方法，其中，路線集群(61、62、63、64)的數量取決於路線鏈路山/又ο
8.根據權利要求1所述的方法，進一步包括: 將被組織在至少一個路線集群(61、62、63、64)中的路線鏈路數據重新組織成至少一個新的路線集群；以及 將所述至少一個新的路線集群存儲到資料庫(20)中。
9.根據權利要求8的方法，其中，所述至少一個新的路線集群(61、62、63、64)提供有集群標識符。
10.根據前述權利要求中任一項所述的方法，其中，所述至少一個路線集群(61、62、63,64)內的每個路線鏈路都提供有路線鏈路標識符。
11.根據結合權利要求6的權利要求10所述的方法，其中，所述路線鏈路標識符的大小由表示可組織在集群內的路線鏈路的最大數量的上限閾值所決定。
12.根據權利要求1所述的方法，其中，所述導航資料庫進一步包括以下項目中的至少一種:地圖顯示數據、目的地條目數據、POI數據、TMC數據和其它增強型導航數據。
13.根據權利要求12所述的方法，其中，所述以下項目中的至少一種:地圖顯示數據、目的地條目數據、POI數據、TMC數據和其它增強型導航數據，被組織成可變的導航數據集群。
14.一種電腦程式產品，具有:當所述電腦程式產品在計算機設備上執行時，用於實施根據至少一個前述權利要求所述的方法的程序代碼。
15.權利要求14所述的電腦程式產品，所述電腦程式產品被存儲在計算機可讀介質上。
16.一種導航資料庫(20)，所述導航資料庫(20)至少包括用於預定地理區域的路線鏈路數據，其中，對於所述預定地理區域而言，所述導航資料庫(20)包括帶有集群標識符的用於組織所述路線鏈路數據的至少一個路線集群(61、62、63、64)。
17.根據權利要求16所述的導航資料庫(20)，其中，所述導航資料庫(20)進一步包括至少一個索引結構，通過該至少一個索引結構能訪問所述至少一個路線集群(61、62、63、64)。
18.根據權利要求16或17所述的導航資料庫(20)，其中，所述至少一個路線集群(61、62、63、64)是靈活的路線集群，該靈活的路線集群包含可變數量的路線鏈路。
19.根據權利要求16所述的導航資料庫(20)，其中，所述集群標識符是永久性標識符。
20.一種導航設備(10)，包括根據權利要求16至18所述的導航資料庫(20)。
全文摘要
本發明提供了一種結構化導航資料庫的技術，其中，所述導航資料庫至少包括用於預定地理區域的路線鏈路數據。該技術的實施方法包括以下步驟將與所述預定地理區域相關聯的路線鏈路數據組織成至少一個路線集群；為所述至少一個路線集群提供集群標識符；以及將所述至少一個路線集群與所述集群標識符一起存儲到所述導航資料庫中。
文檔編號G01C21/26GK103092909SQ20121044224
公開日2013年5月8日 申請日期2012年11月7日 優先權日2011年11月7日
發明者塞巴斯提安·菲舍爾, 霍爾格·多爾曼 申請人:伊萊比特汽車公司