【摘要】：移動通信設(shè)備的普及和無線定位技術(shù)的發(fā)展,使得基于位置的服務(wù)得到了廣泛的應(yīng)用。然而,隨著這些服務(wù)應(yīng)用的擴(kuò)散,空間數(shù)據(jù)日益增多,空間數(shù)據(jù)結(jié)構(gòu)日益復(fù)雜,空間數(shù)據(jù)庫面臨著越來越復(fù)雜的搜索查詢問題。因此,對其中的移動對象建立快速有效的查詢算法具有重要意義。k近鄰查詢一直是空間數(shù)據(jù)庫中數(shù)據(jù)查詢的基礎(chǔ)技術(shù)之一,廣泛應(yīng)用于各種領(lǐng)域,引起了國內(nèi)外眾多學(xué)者的深入研究。但現(xiàn)有的研究方法大多是在特定環(huán)境下(如歐式空間)實現(xiàn)其功能目標(biāo)的,充分考慮到道路網(wǎng)絡(luò)連通性及移動對象特性等因素的研究較少。而道路網(wǎng)絡(luò)環(huán)境下的k近鄰查詢往往更符合人們實際需求,具有更重要的研究意義。路網(wǎng)環(huán)境中數(shù)據(jù)量巨大、數(shù)據(jù)結(jié)構(gòu)復(fù)雜、數(shù)據(jù)分布傾斜、數(shù)據(jù)更新頻繁,這些情況使得移動對象k近鄰查詢的操作代價相當(dāng)昂貴,因此如何提高其查詢效率成為研究人員面臨的一大挑戰(zhàn)。為了應(yīng)對這一挑戰(zhàn),解決在移動數(shù)據(jù)分布傾斜的路網(wǎng)環(huán)境下如何進(jìn)行高效查詢的問題,本文在分析總結(jié)國內(nèi)外相關(guān)研究成果的基礎(chǔ)上,提出了路網(wǎng)環(huán)境中移動對象k近鄰查詢的解決方案。本文主要研究工作有以下幾個方面:(1)針對道路相對靜止且移動對象分布傾斜的情況,本文采用R樹和四叉樹的雙層索引結(jié)構(gòu)分別索引道路網(wǎng)絡(luò)和移動對象。用四叉樹的每一個矩形存儲該區(qū)域中移動對象的位置等信息,其層次結(jié)構(gòu)能控制每個矩形中對象的數(shù)量,使得k近鄰查詢時能獲取合適的搜索區(qū)域。采用R樹對道路建立索引,查詢R樹中與搜索區(qū)域交疊的矩形,獲取這些矩形的葉子結(jié)點中對應(yīng)的道路,加載出搜索區(qū)域?qū)?yīng)的局部道路。(2)建立四叉樹矩形區(qū)域間的信息更新機(jī)制。四叉樹矩形區(qū)域中存儲的移動對象數(shù)量超過一定閾值時,矩形會劃分或者合并,因此需要設(shè)計發(fā)生變化的矩形間的更新機(jī)制讓這些矩形也能實現(xiàn)高效的近鄰的查詢。首先新矩形利用原矩形近鄰信息來更新獲取其近鄰信息,然后新矩形再向其自身近鄰矩形發(fā)送信息更新替代原矩形信息。(3)設(shè)計基于矩形更新機(jī)制的搜索區(qū)域增量擴(kuò)展方法和基于此擴(kuò)展方法的k近鄰查詢算法。為了實現(xiàn)高效的搜索區(qū)域擴(kuò)展,得到合適的k近鄰查詢范圍,設(shè)計搜索區(qū)域增量擴(kuò)展算法,該算法需要先計算新搜索區(qū)域近鄰的矩形。最后基于搜索區(qū)域增量擴(kuò)展的方法,結(jié)合道路網(wǎng)絡(luò)信息設(shè)計完整的路網(wǎng)中k近鄰查詢算法。(4)設(shè)計實驗對比分析,本文采用兩個不同的路網(wǎng)數(shù)據(jù)集,從查詢效率和更新時間兩方面對本文算法進(jìn)行分析。實驗結(jié)果表明,在移動對象分布不均的情況下,本文算法能高效地修剪掉大部分不必要的移動對象,使得其查詢處理效率優(yōu)于對比算法,并且本文算法具有一定的可伸縮性和可擴(kuò)展性;從更新時間上看,本文算法的更新機(jī)制所需成本低,對頻繁更新的移動對象有良好適應(yīng)的能力。
【學(xué)位授予單位】：西南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：TN929.5;TP311.13
【圖文】：

第 2 章 相關(guān)概念及技術(shù)部分對應(yīng)的網(wǎng)格分別增加新的記錄來反映當(dāng)前處理的實體單網(wǎng)格空間索引。有創(chuàng)建、重建、插入、刪除和更新等關(guān)鍵操作。創(chuàng)建網(wǎng)格特征計算出一個合適的網(wǎng)格尺度，對每一個實體按網(wǎng)格進(jìn)有網(wǎng)格中追加該實體記錄，直到所有實體記錄完畢。隨著變，網(wǎng)格的統(tǒng)計特征可能會發(fā)生改變，這就需要重新統(tǒng)計適的網(wǎng)格尺度，重建網(wǎng)格。當(dāng)插入空間實體時，首先計算格，并計算出空間要素的網(wǎng)格編碼，然后在網(wǎng)格結(jié)構(gòu)索引數(shù)據(jù)項。而刪除實體記錄需要刪除所有該實體對應(yīng)的索引以通過刪除索引記錄再添加索引記錄來實現(xiàn)。

圖 2-2 R 樹索引數(shù)據(jù)結(jié)構(gòu)示例圖如圖 2-2 所示為一個 R 樹的索引結(jié)構(gòu)，圖左邊是 11 個空間對象集合，右邊對應(yīng)的 R 樹是一個平衡的 3 叉樹，其葉子結(jié)點都在第二層。相鄰的空間對象的 MBR進(jìn)行框選聚集，形成一個父結(jié)點的 MBR，圖中 6、8、9 的 MBR 構(gòu)成了 C 的 MBR。當(dāng)進(jìn)行查詢時，從根結(jié)點開始，首先查詢 A、B、C，如果搜索區(qū)域與 A 或者 B或者 C 結(jié)點相交，則繼續(xù)向下進(jìn)行查詢直到到達(dá)葉子結(jié)點，最后具體計算葉子結(jié)點中的數(shù)據(jù)�？梢钥吹� R 樹結(jié)構(gòu)的一個重要特點是兄弟結(jié)點所對應(yīng)的 MBR 可能相互交疊，使得 R 樹容易進(jìn)行插入或者刪除等更新的操作。但另一方面，當(dāng)在 R 樹中進(jìn)行插入或者刪除的時候，出現(xiàn)下溢或者上溢的狀況，則需要重新對結(jié)點內(nèi)的數(shù)據(jù)進(jìn)行調(diào)整，甚至需要對整個 R 樹的層次結(jié)構(gòu)進(jìn)行調(diào)整，使得空間查詢的效率下降，因此 R 樹并不適合頻繁進(jìn)行動態(tài)更新的環(huán)境。但現(xiàn)實道路拓?fù)渚W(wǎng)絡(luò)更新周期相對較長，整體上相對固定，利用平衡的 R 樹索引是比較合適的，因此本文采用 R 樹對路網(wǎng)拓?fù)溥M(jìn)行索引。

圖 2-3 基于路段的路網(wǎng)模型示例圖道路網(wǎng)絡(luò)用加權(quán)有向圖 G 來表示，令 G=(V,E)，其中，V 表示道路網(wǎng)絡(luò)中頂點的集合 V=(v1，v2，v3，…vi)，頂點模擬道路的交叉口、起點、終點；E 表示道路網(wǎng)絡(luò)中線段的集合，E=(e1，e2，e3，…ei),模擬起始點 vi和終點 vj兩個頂點間的路段；邊的權(quán)重 d 表示對應(yīng)的路段長度，記作 e=(vi,vj,d)。路網(wǎng)建立對應(yīng)路段模型后，建立起對路網(wǎng)線段的索引，即建立路段的 MBR。如圖 2-4 所示，所框選的矩形部分為線段 e1、e2、e3的 MBR。

【參考文獻(xiàn)】

相關(guān)期刊論文 前6條

1 李松;張麗平;郝忠孝;;動態(tài)數(shù)據(jù)集環(huán)境下的強(qiáng)鄰近對查詢[J];計算機(jī)研究與發(fā)展;2015年03期

2 張棟良;唐俊;;基于路由機(jī)制的時變路網(wǎng)k近鄰算法[J];計算機(jī)科學(xué);2013年02期

3 馮惠妍;郭俊鳳;;道路網(wǎng)絡(luò)中的連續(xù)最近鄰查詢[J];計算機(jī)工程;2010年08期

4 廖巍;張琪;吳曉平;鐘志農(nóng);;道路網(wǎng)絡(luò)環(huán)境下的連續(xù)k近鄰查詢處理研究[J];小型微型計算機(jī)系統(tǒng);2010年04期

5 廖巍;熊偉;王鈞;景寧;鐘志農(nóng);;可伸縮的增量連續(xù)k近鄰查詢處理[J];軟件學(xué)報;2007年02期

6 于忠誠,王金慧,郭景峰;移動對象的連續(xù)最近鄰查詢算法[J];計算機(jī)工程與應(yīng)用;2004年33期

相關(guān)博士學(xué)位論文 前1條

1 丁治明;移動數(shù)據(jù)庫關(guān)鍵技術(shù)研究[D];中國科學(xué)院研究生院（計算技術(shù)研究所）;2002年

本文編號：2760532