空間數(shù)據(jù)庫中移動κ近鄰線段查詢技術的研究.pdf

1、隨著個人電子設備的普及和通信技術的發(fā)展，基于位置的服務在日常生活中已經(jīng)無處不在，如急救服務，道路導航和人員跟蹤等。其中，空間數(shù)據(jù)庫中的移動k近鄰查詢，由于巨大的應用需求，已經(jīng)引起了學術界和工業(yè)界的廣泛關注。目前關于移動k近鄰查詢的工作，均將查詢對象抽象為點。但是現(xiàn)實世界中的查詢對象，可能是河流、公路等復雜的線型事物，在這種情況下，傳統(tǒng)方法將無法提供有效的服務。本文將復雜線型事物抽象為線段或者由一組線段組成的折線段，并從線段距離計算和線段

2、安全區(qū)構建兩個方面研究了空間數(shù)據(jù)庫中移動k近鄰的線段查詢技術。
　　本文首先形式化定義了空間線段查詢的基本概念，針對查詢點與線段之間距離計算的復雜性，提出了線段劃分區(qū)的概念來分類求解點與線段的距離。然后本文提出了移動k近鄰線段查詢安全區(qū)的構建算法LRkNN。LRkNN算法在RangeNN方法的基礎上，僅需掃描部分數(shù)據(jù)對象建立局部安全區(qū)，在保證查詢結果準確性和有效性的基礎上，可以有效提高線段安全區(qū)的構建效率。此外為支持數(shù)據(jù)對象的動態(tài)

3、變化，本文在安全區(qū)基礎上提出了沖突域概念。如果變化的數(shù)據(jù)對象不包含于沖突域，則不需要重新計算查詢結果。實驗驗證了本文所提出的LRkNN算法在高效性和準確性上的優(yōu)越性，相比基于抽樣的方法，LRkNN在響應時間，I/O代價和通信代價方面至少提高一個數(shù)量級。
　　為提高移動k近鄰線段查詢結果的可用性，通常需要對k個查詢結果進行排序。因此，本文首先通過擴展IRU排序方法（即LIRU），使其支持線段排序功能。然后基于V*-Diagram方法

4、提出了LV*-Diagram技術及算法LMkNN，通過求解關于線段的安全區(qū)和LIRU結果的交集，構建線段的近似安全區(qū)，保證了查詢結果的準確性和有序性。最后，提出折線段劃分區(qū)的概念，在折線段劃分區(qū)內，折線段問題簡化為單一線段問題。分別用LV*-Diagram技術構建每個折線段劃分區(qū)內的線段安全區(qū)，來處理查詢對象抽象為折線段的情況。LV*-Diagram技術同樣可以支持數(shù)據(jù)對象的動態(tài)增刪。如果動態(tài)變化的數(shù)據(jù)對象不在關于線段的安全區(qū)內，則查詢