發(fā)布時間：2020-07-18 06:16

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

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

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

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

【參考文獻】

相關期刊論文 前6條

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

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

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

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

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

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

相關博士學位論文 前1條

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

本文編號：2760532