發(fā)布時(shí)間：2017-12-12 07:07

  本文關(guān)鍵詞：基于NOSQL數(shù)據(jù)庫的路網(wǎng)最短路徑查詢及優(yōu)化研究

  更多相關(guān)文章： Neo4j A* 路網(wǎng) 最短路徑 PostgreSQL

【摘要】：基于路網(wǎng)的路徑規(guī)劃問題作為地理信息與交通工程領(lǐng)域一直備受人們青睞。在過去,路網(wǎng)信息主要以表的形式存儲在關(guān)系數(shù)據(jù)庫中。從對網(wǎng)絡(luò)以及圖等結(jié)構(gòu)的數(shù)據(jù)處理來看,傳統(tǒng)的關(guān)系數(shù)據(jù)庫以關(guān)系模式進(jìn)行存儲,但在關(guān)系模型上存儲圖結(jié)構(gòu)以及實(shí)現(xiàn)圖相關(guān)算法時(shí)較為復(fù)雜,大量的關(guān)系表聯(lián)結(jié)使得性能不高。伴隨著NOSQL數(shù)據(jù)庫的發(fā)展,涌現(xiàn)出了一大批適合不同數(shù)據(jù)模型的數(shù)據(jù)庫,像文檔數(shù)據(jù)庫、鍵值對數(shù)據(jù)庫、列式數(shù)據(jù)庫和圖數(shù)據(jù)庫等。這為許多不適合關(guān)系結(jié)構(gòu)存儲的數(shù)據(jù)模型提供了新的發(fā)展空間。Neo4j作為NOSQL數(shù)據(jù)庫里圖數(shù)據(jù)庫的代表,提供了以節(jié)點(diǎn)與關(guān)系為實(shí)體的存儲模型。這種以圖為數(shù)據(jù)模型的存儲形式將更符合路網(wǎng)數(shù)據(jù)模型。因此,本文對基于Neo4j的路網(wǎng)最短路徑查詢進(jìn)行了研究。研究過程中通過與關(guān)系型數(shù)據(jù)庫比較分析了圖數(shù)據(jù)庫的特點(diǎn),并根據(jù)其特點(diǎn)以及最短路徑算法提出了一種改進(jìn)的雙向搜索算法。論文的研究內(nèi)容主要包括以下幾點(diǎn):(1)研究關(guān)系型數(shù)據(jù)庫與Neo4j數(shù)據(jù)庫存儲結(jié)構(gòu)的特征,實(shí)現(xiàn)路網(wǎng)數(shù)據(jù)在兩種平臺的數(shù)據(jù)存儲與預(yù)處理。具體內(nèi)容是分析兩者的數(shù)據(jù)模型,將數(shù)據(jù)轉(zhuǎn)換為適用于兩種數(shù)據(jù)庫的不同格式,實(shí)現(xiàn)同一數(shù)據(jù)源在不同存儲平臺的存儲。提出數(shù)據(jù)處理的方法,包括頂點(diǎn)經(jīng)緯度坐標(biāo)及位置的處理,并實(shí)現(xiàn)數(shù)據(jù)庫中路網(wǎng)數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)。(2)研究Neo4j數(shù)據(jù)庫特性。為了分析圖形數(shù)據(jù)庫特殊的數(shù)據(jù)模型在圖結(jié)構(gòu)上的優(yōu)勢以及與關(guān)系數(shù)據(jù)庫的差異,基于兩種不同存儲平臺實(shí)現(xiàn)A*算法。研究兩種存儲平臺下路網(wǎng)最短路徑查詢,并以冷熱兩種啟動方式分析查詢過程中內(nèi)存消耗和緩存對兩種數(shù)據(jù)庫的作用以及數(shù)據(jù)庫查詢效率方面的性能。(3)基于Neo4j改進(jìn)的A*算法的研究。通過對圖數(shù)據(jù)庫Neo4j的研究發(fā)現(xiàn),其關(guān)系結(jié)構(gòu)可以很好支持雙向遍歷;其次,其在圖數(shù)據(jù)路徑查詢時(shí)存在消耗大量內(nèi)存的弊端。針對Neo4j的弊端以及結(jié)構(gòu)特點(diǎn)提出了改進(jìn)的雙向搜索A*算法。改進(jìn)主要有兩點(diǎn):一是提出以最佳節(jié)點(diǎn)為相對目的節(jié)點(diǎn)的動態(tài)搜索思想;二是提出比較兩端最小估計(jì)值的切換標(biāo)準(zhǔn)。同時(shí)結(jié)構(gòu)上使用了可以快速排序的最小二叉堆數(shù)據(jù)結(jié)構(gòu)。對其改進(jìn)效果進(jìn)行了實(shí)驗(yàn)驗(yàn)證,發(fā)現(xiàn)改進(jìn)后的算法有很好的效果。
【學(xué)位授予單位】：北京工業(yè)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：TP311.13

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 ;第一屆全國數(shù)據(jù)庫應(yīng)用技術(shù)年會[J];計(jì)算機(jī)學(xué)報(bào);2006年01期

2 劉向民;;建立數(shù)據(jù)庫應(yīng)用團(tuán)隊(duì)的必要性[J];中國金融電腦;2011年06期

3 ;讓數(shù)據(jù)庫“大團(tuán)結(jié)”[J];每周電腦報(bào);2001年07期

4 趙昱;趙華;;不依賴數(shù)據(jù)庫實(shí)現(xiàn)不同頁面歌曲連播技巧[J];電腦學(xué)習(xí);2006年06期

5 王云愛,趙文莉;漫談網(wǎng)上查詢數(shù)據(jù)庫[J];山西煤炭;1999年04期

6 卞靜,余豪澤,王久興,何之璋;基于數(shù)據(jù)庫的函數(shù)搜索設(shè)計(jì)[J];現(xiàn)代計(jì)算機(jī)(專業(yè)版);2005年01期

7 李超;袁兆山;吳雷;;兩級數(shù)據(jù)庫的設(shè)計(jì)和實(shí)現(xiàn)技術(shù)研究[J];計(jì)算機(jī)應(yīng)用研究;2006年07期

8 郭思培;彭智勇;;數(shù)據(jù)庫規(guī)范化理論研究[J];武漢大學(xué)學(xué)報(bào)(理學(xué)版);2011年06期

9 楊凡;蔣建春;卿斯?jié)h;;弱點(diǎn)數(shù)據(jù)庫的設(shè)計(jì)及其實(shí)現(xiàn)[J];計(jì)算機(jī)科學(xué);2002年06期

10 徐貴紅;含有組合列的約束數(shù)據(jù)庫[J];內(nèi)蒙古大學(xué)學(xué)報(bào)(自然科學(xué)版);2001年01期

中國重要會議論文全文數(shù)據(jù)庫 前7條

1 李德毅;;歸納學(xué)習(xí):從數(shù)據(jù)庫中發(fā)現(xiàn)知識[A];第十屆全國數(shù)據(jù)庫學(xué)術(shù)會議論文集[C];1992年

2 劉佼;肖穩(wěn)安;王業(yè)成;;全國雷電災(zāi)害數(shù)據(jù)庫分析與設(shè)計(jì)[A];S13 第十屆防雷減災(zāi)論壇——雷電災(zāi)害與風(fēng)險(xiǎn)評估[C];2012年

3 陳恩紅;李青;;前言[A];第29屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（B輯）（NDBC2012）[C];2012年

4 尹少宜;陳繼東;孟小峰;賴彩鳳;;手機(jī)數(shù)據(jù)庫PhoneDB的存儲和恢復(fù)技術(shù)[A];第二十二屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報(bào)告篇）[C];2005年

5 湯庸;黃錦輝;李青;;前言[A];第二十三屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報(bào)告篇）[C];2006年

6 李寧;;基于全具象和Agent的虛擬數(shù)據(jù)庫實(shí)現(xiàn)[A];第十九屆全國數(shù)據(jù)庫學(xué)術(shù)會議論文集（技術(shù)報(bào)告篇）[C];2002年

7 ;前言[A];第十二屆全國數(shù)據(jù)庫學(xué)術(shù)會議論文集[C];1994年

中國重要報(bào)紙全文數(shù)據(jù)庫 前1條

1 江蘇 周轉(zhuǎn)義;用ASP實(shí)現(xiàn)動態(tài)IP轉(zhuǎn)向[N];電腦報(bào);2003年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 喬雋;Web數(shù)據(jù)庫采樣技術(shù)研究[D];東北大學(xué);2013年

2 朱小強(qiáng);基于J2EE的CRM客戶與協(xié)議系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D];南京大學(xué);2015年

3 于海鵬;基于NOSQL數(shù)據(jù)庫的路網(wǎng)最短路徑查詢及優(yōu)化研究[D];北京工業(yè)大學(xué);2016年

4 張耀坤;P2P數(shù)據(jù)庫內(nèi)容認(rèn)證方案的設(shè)計(jì)與實(shí)現(xiàn)[D];華中科技大學(xué);2007年

5 翟鈺;系統(tǒng)脆弱性研究及其數(shù)據(jù)庫的設(shè)計(jì)與實(shí)現(xiàn)[D];西安建筑科技大學(xué);2004年

6 劉才;中學(xué)學(xué)生信息管理系統(tǒng)[D];吉林大學(xué);2009年

7 黃睿;FCoE交換機(jī)ZONE數(shù)據(jù)庫模塊的設(shè)計(jì)和實(shí)現(xiàn)[D];北京郵電大學(xué);2011年

8 董華榮;小學(xué)高效課堂實(shí)驗(yàn)平臺設(shè)計(jì)與實(shí)現(xiàn)[D];山西大學(xué);2013年

9 包曙;內(nèi)蒙古電力公司人力資源管理系統(tǒng)設(shè)計(jì)[D];內(nèi)蒙古大學(xué);2012年

10 孫奇;ERP中庫存管理與人力資源管理的研究及開發(fā)[D];中北大學(xué);2008年

，

本文編號：1281585