隨著移動互聯(lián)網(wǎng)技術的發(fā)展,大量應用的順利部署和實施都不同程度依賴空間數(shù)據(jù)對象的查詢�？臻g最近鄰查詢是空間對象涉及的主要查詢種類之一,用于找到距離用戶最近的目標對象。然而,目前的最近鄰查詢存在著查詢源單一、查詢結(jié)果分散無序、結(jié)果集過大且不能滿足用戶偏好等問題。針對上述問題,本文主要研究多源最近鄰查詢,用于返回滿足空間約束條件和屬性約束條件的目標對象,避免單源最近鄰查詢的不足。該查詢不僅可以應用到選址分析、旅游規(guī)劃、物流配送等日常生活服務的應用中,還可以應用到與位置有關的空間實體對象的查詢、分析中。首先,針對現(xiàn)有最近鄰查詢的查詢源單一的問題,利用空間距離約束為查詢主要條件,研究由多個查詢點組成查詢源的最近鄰查詢方法。該研究基于兩種單源基礎算法（Dijkstra和IER）的結(jié)點擴展思想,提出基于局部優(yōu)先策略和全局優(yōu)先策略的多源最近鄰查詢算法,構(gòu)建R樹索引,并設計緊致上下界,縮小結(jié)點訪問范圍,提高算法性能。其次,針對現(xiàn)有最近鄰查詢結(jié)果分散無序、且存在現(xiàn)實目標對象位置集中（如商場、廠房、倉庫等）的問題,研究空間距離和屬性關鍵字共同約束下的多源最近鄰查詢,提出目標群的影響力計算方法和關鍵字查詢算法... 

【文章來源】：燕山大學河北省

【文章頁數(shù)】：122 頁

【學位級別】：博士

【部分圖文】：

路網(wǎng)局部示意圖

圖 2-2 R 樹示例Fig. 2-2 Example of R tree B 樹一樣，R 樹也是一顆平衡樹，它用最小外接矩形(MBR)把空間距象集中于矩形框中，如果某個查詢不能對應到某個矩形，則矩形內(nèi)的是查詢目標。R 樹中的非葉子結(jié)點(根結(jié)點除外)所能擁有的子結(jié)點數(shù)目圍。如果在 n 維空間下，M 表示子結(jié)點的最大個數(shù)，m 表示子結(jié)點的I 表示用來存儲空間對象邊界的坐標閉區(qū)間[a, b]，則 R 樹有如下性質(zhì)：1)所有非根結(jié)點包含有[m, M]個索引條目，通常 m = M 2。2)所有葉子結(jié)點都位于同一層。3)所有結(jié)點存儲的記錄條目中，I 是覆蓋記錄所代表目標對象的最小矩形圖 2-2 b)所示，圖中有 19 個區(qū)域，虛線框表示的區(qū)域為 R 樹的內(nèi)部7)，實線矩形框表示數(shù)據(jù)對象(R8~R19)。比如，樹中根結(jié)點 R1包含 3 個R3、R4和 R5，另一個根結(jié)點 R2包含 2 個內(nèi)部結(jié)點 R6和 R7，其中 R3包

花費更多的計算代價。鑒于此原因，在實際路網(wǎng)最近鄰查詢的過程中，產(chǎn)生了更多的 R 樹的變體結(jié)構(gòu)，對 R 樹存在的問題做了改進，例如 VR 樹[31]。2.2.2 四叉樹索引結(jié)構(gòu)四叉樹通常也叫做四元樹，是二叉樹的高維變體結(jié)構(gòu)，對于空間數(shù)據(jù)來說，四叉樹在目標對象的最大覆蓋范圍內(nèi)，迭代地將目標區(qū)域進行四塊分割，直到每個被分割的最小區(qū)域中都包含目標對象，再根據(jù)目標劃分區(qū)域的層次、個數(shù)，建立對應的索引，是一種非常有效的索引結(jié)構(gòu)。四叉樹的結(jié)構(gòu)比較簡單，對于目標對象分布比較均勻的網(wǎng)絡來說，查詢效率很高，是 GIS 和地圖查詢應用中的主要索引手段之一。常規(guī)四叉樹結(jié)構(gòu)如圖 2-3 所示，平面示意圖中有 8 個區(qū)域，每個區(qū)域可劃分為更小的四個區(qū)域，如 b 區(qū)域中可以繼續(xù)劃分成 x，y，z 和 t 四個區(qū)域。在最近鄰查詢中，假設要查找的空間對象為 9，則正確的查詢路徑為：b→ →9。ba1

【參考文獻】：
期刊論文
[1]一種GIS與集合覆蓋法的消防區(qū)優(yōu)化布局[J]. 劉莉,陳晨.  測繪科學. 2018(09)
[2]空間Skyline查詢處理:應用、研究與挑戰(zhàn)[J]. 余未,鄭吉平,王海翔,王永閣,陳嘉良,江順青.  計算機科學. 2017(02)
[3]基于聚類的路網(wǎng)上關鍵字查詢[J]. 吳丹,楊衛(wèi)東.  小型微型計算機系統(tǒng). 2017(02)
[4]路網(wǎng)中基于預計算的跳躍式查詢最近鄰的算法[J]. 王恒.  天津理工大學學報. 2011(02)
[5]基于Voronoi圖的最近鄰查詢的研究[J]. 王淼.  微計算機信息. 2008(33)
[6]空間網(wǎng)絡數(shù)據(jù)庫中最近鄰查詢的設計與實現(xiàn)[J]. 孫亞.  計算機科學. 2008(03)
[7]基于SR-樹的空間對象最近鄰查詢[J]. 張奮,潘梅生,鄒北驥.  計算機工程與應用. 2007(04)
[8]R樹家族的演變和發(fā)展[J]. 張明波,陸鋒,申排偉,程昌秀.  計算機學報. 2005(03)

碩士論文
[1]基于集合覆蓋與智能優(yōu)化算法的WCDMA網(wǎng)絡基站位置優(yōu)化[D]. 代超.華南理工大學 2013



本文編號：2972436