資源描述：
《基于半度量路網(wǎng)的高效查詢算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、萬方數(shù)據(jù)分類號UDC作者姓名：指導(dǎo)教師：申請學(xué)位級別：學(xué)科專業(yè)名稱：論文提交日期：學(xué)位授予日期：評閱人：密級學(xué)位論文基于半度量路網(wǎng)的高效查詢算法張晶晶楊曉春教授東北大學(xué)信息科學(xué)與工程學(xué)院碩士學(xué)科類別：工學(xué)計算機應(yīng)用技術(shù)2014年6月論文答辯曰期：2014年6月2014年7月答辯委員會主席：申德榮王斌，石祥濱東北大學(xué)2014年6月萬方數(shù)據(jù)AThesisinComputerApplicationTechnologyQueryAlgorithmsinSemimetricRoadNetworkByZhangJingjingSupervisor
2、：ProfessorYangXiaochunNortheasternUniversityJune2014萬方數(shù)據(jù)獨創(chuàng)性聲明本人聲明，所呈交的學(xué)位論文是在導(dǎo)師的指導(dǎo)下完成的。論文中取得的研究成果除加以標注和致謝的地方外，不包含其他人己經(jīng)發(fā)表或撰寫過的研究成果，也不包括本人為獲得其他學(xué)位而使用過的材料。與我一同工作的同志對本研究所做的任何貢獻均已在論文中作了明確的說明并表示謝意。學(xué)位論文作者簽名：多次赫晶日期：2DJ牛．6．≯畢學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者和指導(dǎo)教師完全了解東北大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定：即學(xué)校有權(quán)保留并向國
3、家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和磁盤，允許論文被查閱和借閱。本人同意東北大學(xué)可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索、交流。作者和導(dǎo)師同意網(wǎng)上交流的時間為作者獲得學(xué)位后：半年口一年口一年半口兩年∥學(xué)位論文作者簽名：弓歌晶晶導(dǎo)師簽名：％砭勿農(nóng)簽字日期：】of峪．6．了牛簽字日期：)。l‰6．L壚萬方數(shù)據(jù)東北大學(xué)碩士學(xué)位論文摘要基于半度量路網(wǎng)的高效查詢算法摘要空間數(shù)據(jù)庫己成為數(shù)據(jù)庫領(lǐng)域中的熱點研究方向，路網(wǎng)作為空間數(shù)據(jù)庫領(lǐng)域中重要的一部分，目前在各個地圖服務(wù)、商用在線導(dǎo)航系統(tǒng)以及基于位置的查詢應(yīng)用軟件中有著廣泛的應(yīng)用，路網(wǎng)中
4、的查詢得到了越來越廣泛的關(guān)注。由于路網(wǎng)具有道路數(shù)量多、密度大、交叉頻繁、路況復(fù)雜等特性，如何在路網(wǎng)中高效的查詢至關(guān)重要。路網(wǎng)中利用網(wǎng)絡(luò)距離作為距離的度量方式，廣泛存在不滿足三角不等式關(guān)系的情況，稱這樣的路網(wǎng)為半度量路網(wǎng)。由于半度量路網(wǎng)不滿足三角不等式關(guān)系，常見的度量空間中的索引結(jié)構(gòu)無法有效工作，目前已提出的預(yù)計算的方法存在查詢速度慢、計算代價慢的問題，如何在半度量路網(wǎng)中高效的查詢是本文的研究重點和難點。為了解決半度量路網(wǎng)中的查詢速度慢、計算代價大的問題，本文提出了半度量路網(wǎng)中的高效查詢方法。首先，由于直接在半度量路網(wǎng)中查詢代價大，本文
5、提出了兩種方法將半度量路網(wǎng)轉(zhuǎn)化為度量路網(wǎng)來降低查詢代價。一種方法為隨機刪除邊算法將半度量路網(wǎng)轉(zhuǎn)化為度量路網(wǎng)，該方法簡單，容易實現(xiàn)，但轉(zhuǎn)化過程中信息損失比較大。為了進一步降低查詢代價，以最小化的信息損失將半度量路網(wǎng)轉(zhuǎn)化為度量路嘲，這是一個NP．hard問題，因此本文提出了另一種啟發(fā)式的排序刪除邊算法以近似最小化的信息損失完成度量化。其次，提出了QM一樹索引結(jié)構(gòu)，在查詢中利用三角不等式關(guān)系剪枝不可能包含查詢結(jié)果的子樹，有效的減少了查詢時問。最后，本文提出j=，半度量路網(wǎng)中的范圍查詢方法以及K近鄰查詢方法。這兩種查詢方法都包括查詢和驗證兩部
6、分，查詢部分利用三角不等式關(guān)系來剪枝不可能為查詢結(jié)果的子樹，快速的找出查詢結(jié)果，有效的加速查詢；驗證部分對找到的查詢結(jié)果節(jié)點和查詢點中指針指向的包含信息損失的鏈表中的元素分別進行驗證，有效的保證了查詢的正確性。最后，本文在真實的數(shù)據(jù)集上進行了大量的測試研究，通過對實驗結(jié)果的分析與總結(jié)，證明了排序刪除邊算法能夠以近似最小化的信息損失將半度量路網(wǎng)轉(zhuǎn)化為度量路網(wǎng)；基于QM．樹索引結(jié)構(gòu)的半度量路網(wǎng)中的范圍查詢算法以及K近鄰查詢算法有效的降低了查詢代價并保證了查詢結(jié)果的準確性。關(guān)鍵詞：路網(wǎng)；三角不等式：半度量；范圍查詢；K近鄰查詢?nèi)f方數(shù)據(jù)東北大
7、學(xué)碩士學(xué)位論文AbstractQueryAlgorithmsResearchinSemimetricRoadNetworkAbstractSpatialdatabaseshavebecomeahotresearchdirectioninthefieldofthedatabase，inwhichroadnetworkasanimportantparthascurrentlybeenwidelyappliedinvariousmapservices，commercialonlinenavigationsystemsandlocation-
8、basedqueryapplication．Queryinginroadnetworkhasgotmoreandmoreattention．Duetothelargenumberofroads，highdensity,c
