[發(fā)明專利]一種面向海量路網(wǎng)數(shù)據(jù)壓縮存儲的層次網(wǎng)絡(luò)構(gòu)建方法

有效

• 申請?zhí)枺?/td>: 201710488522.4
• 申請日: 2017-06-23
• 公開（公告）號: CN107330030B
• 公開（公告）日: 2019-10-15
• 發(fā)明（設(shè)計）人: 俞肇元;袁林旺;朱帥;胡勇;袁帥;閭國年
• 申請（專利權(quán)）人: 南京師范大學(xué)
• 主分類號: G06F16/29
• 分類號: G06F16/29;G06F16/174
• 代理公司: 南京蘇高專利商標(biāo)事務(wù)所(普通合伙) 32204
• 代理人: 唐紅

本發(fā)明公開一種面向海量路網(wǎng)數(shù)據(jù)壓縮存儲的層次網(wǎng)絡(luò)構(gòu)建方法，包括以下步驟：對海量網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行層次劃分，劃分的層次可通過參數(shù)設(shè)定；在網(wǎng)絡(luò)層次劃分的基礎(chǔ)上進(jìn)行網(wǎng)絡(luò)覆蓋圖的構(gòu)建，重構(gòu)上層網(wǎng)絡(luò)基于最短路的拓?fù)涮卣鳎股蠈泳W(wǎng)絡(luò)依然具有連通性；在層次網(wǎng)絡(luò)覆蓋圖的基礎(chǔ)上對網(wǎng)絡(luò)進(jìn)行分區(qū)；在分層分區(qū)構(gòu)建基礎(chǔ)上，對區(qū)域內(nèi)的節(jié)點進(jìn)行壓縮，通過計算所能到達(dá)的最近鄰分區(qū)邊界節(jié)點，將這個節(jié)點附著在邊界節(jié)點上并保存相關(guān)信息，從而實現(xiàn)對海量網(wǎng)絡(luò)數(shù)據(jù)的壓縮。本發(fā)明主要用于對大規(guī)模道路網(wǎng)絡(luò)的層次構(gòu)建與壓縮存儲，在對網(wǎng)絡(luò)做大規(guī)模壓縮后仍能很好的保持網(wǎng)絡(luò)的整體結(jié)構(gòu)和拓?fù)涮卣鳎軌蛱岣咦泳W(wǎng)絡(luò)分析算法效率。

技術(shù)領(lǐng)域

本發(fā)明涉及一種計算機信息處理技術(shù)，具體涉及一種面向海量路網(wǎng)數(shù)據(jù)壓縮存儲的層次網(wǎng)絡(luò)構(gòu)建方法。

背景技術(shù)

在面向大規(guī)模道路網(wǎng)絡(luò)數(shù)據(jù)的地理信息系統(tǒng)應(yīng)用中，道路網(wǎng)絡(luò)復(fù)雜多樣，信息量大。在導(dǎo)航系統(tǒng)設(shè)計中，面向大規(guī)模地理網(wǎng)絡(luò)的路徑查找往往會有很高計算復(fù)雜度，且不能支持網(wǎng)絡(luò)的動態(tài)性，增加了查詢時間，影響用戶體驗，且隨著大數(shù)據(jù)技術(shù)發(fā)展，海量道路網(wǎng)絡(luò)數(shù)據(jù)下的網(wǎng)絡(luò)分析引起了越來越多的關(guān)注，傳統(tǒng)算法在解決海量網(wǎng)絡(luò)數(shù)據(jù)條件下的網(wǎng)絡(luò)分析問題時往往具有很高的計算復(fù)雜度和內(nèi)存占用。針對這一問題，在對現(xiàn)實道路網(wǎng)絡(luò)進(jìn)行觀察研究的基礎(chǔ)上，后續(xù)研究者提出了一系列的啟發(fā)式優(yōu)化算法，其中最重要的一種就是層次化方法。層次化方法通過挖掘道路網(wǎng)內(nèi)部的層次特征，即不同的節(jié)點在搜索過程中有不同的重要程度這一事實來降低搜索空間。上述兩種方法在降低算法復(fù)雜度，提升路徑查詢效率上具有顯著的提升，但這同時也是以犧牲一定的預(yù)處理時間作為代價的。

層次化方法通過挖掘道路網(wǎng)內(nèi)部層次特征，將不同層次節(jié)點集合構(gòu)建出對應(yīng)的上層覆蓋網(wǎng)絡(luò)。在路徑搜索過程中，當(dāng)搜索遇到一些上層節(jié)點時只釋放上一層的節(jié)點集合和對應(yīng)的邊。這樣通過不同層級網(wǎng)絡(luò)的迭代構(gòu)建可以減少很多無關(guān)搜索節(jié)點釋放，進(jìn)一步降低搜索空間。現(xiàn)有的層次化算法主要分為兩種類型，一種是分割算法，利用道路網(wǎng)的平面特性對網(wǎng)絡(luò)做分割，然后利用邊界點及對應(yīng)的距離構(gòu)建高層網(wǎng)絡(luò)。另外一種是利用節(jié)點重要度對節(jié)點進(jìn)行層次劃分，并構(gòu)建相應(yīng)的覆蓋圖，路徑搜索過程在由原始網(wǎng)絡(luò)和覆蓋圖的集合上進(jìn)行。

在對大規(guī)模道路網(wǎng)絡(luò)數(shù)據(jù)分析時，現(xiàn)有技術(shù)往往只需要提取一些重要節(jié)點來表征整個網(wǎng)絡(luò)，即對整個網(wǎng)絡(luò)在保持整體結(jié)構(gòu)特征情況下做壓縮。當(dāng)前沒有方法能很好的能解決這一問題。

發(fā)明內(nèi)容

發(fā)明目的：本發(fā)明的目的在于解決現(xiàn)有技術(shù)中存在的不足，提供一種面向海量路網(wǎng)數(shù)據(jù)壓縮存儲的層次網(wǎng)絡(luò)構(gòu)建方法，現(xiàn)對大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)高精度壓縮，并通過將壓縮掉的節(jié)點信息保存在關(guān)聯(lián)節(jié)點上實現(xiàn)對原始網(wǎng)絡(luò)信息的保留。

技術(shù)方案：本發(fā)明一種面向海量路網(wǎng)數(shù)據(jù)壓縮存儲的層次網(wǎng)絡(luò)構(gòu)建方法，依次包括以下步驟：

(1)對道路網(wǎng)絡(luò)屬性信息進(jìn)行篩選，提取必要屬性信息并存儲；對所有網(wǎng)絡(luò)節(jié)點進(jìn)行編碼，利用網(wǎng)絡(luò)數(shù)據(jù)中節(jié)點和邊的起止節(jié)點的坐標(biāo)信息構(gòu)建網(wǎng)絡(luò)拓?fù)潢P(guān)系；然后設(shè)計基于節(jié)點-邊映射關(guān)系的網(wǎng)絡(luò)存儲數(shù)據(jù)結(jié)構(gòu)；

(2)對原始道路網(wǎng)絡(luò)節(jié)點進(jìn)行層次劃分，不同的劃分方法產(chǎn)生不同的網(wǎng)絡(luò)層次效果，然后根據(jù)不同分層結(jié)果對網(wǎng)絡(luò)層次劃分標(biāo)準(zhǔn)進(jìn)行評估，初步判斷劃分結(jié)果是否滿足區(qū)域特征；層次劃分方法包括基于道路網(wǎng)絡(luò)屬性即根據(jù)道路所屬等級進(jìn)行劃分，或者根據(jù)局部最優(yōu)路徑信息進(jìn)行層次劃分；此處，不同的網(wǎng)絡(luò)層次效果包括網(wǎng)絡(luò)層次劃分、覆蓋圖構(gòu)建和網(wǎng)絡(luò)分區(qū)構(gòu)建效果；

(3)根據(jù)道路網(wǎng)絡(luò)層次劃分結(jié)果，構(gòu)建不同層次網(wǎng)絡(luò)的覆蓋圖；覆蓋圖是由所屬上層網(wǎng)絡(luò)節(jié)點集和上層節(jié)點間不經(jīng)過下層節(jié)點的最短路徑構(gòu)成，其構(gòu)建過程基于下一層的網(wǎng)絡(luò)覆蓋圖進(jìn)行，通過對特定層次網(wǎng)絡(luò)節(jié)點做局部搜索確定上層網(wǎng)絡(luò)節(jié)點間連通性，通過遍歷上層節(jié)點完成對網(wǎng)絡(luò)覆蓋圖的構(gòu)建；