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

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

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

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

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