空間受限移動(dòng)對(duì)象的概率查詢處理技術(shù)研究與可達(dá)區(qū)域分析.pdf

1、隨著無(wú)線網(wǎng)絡(luò)、計(jì)算機(jī)存儲(chǔ)等技術(shù)的高速發(fā)展，移動(dòng)對(duì)象數(shù)據(jù)庫(kù)作為空間數(shù)據(jù)庫(kù)的一個(gè)分支正被越來(lái)越多的學(xué)者所關(guān)注。查詢處理是移動(dòng)數(shù)據(jù)庫(kù)中一個(gè)極為常用的的操作，并且查詢移動(dòng)對(duì)象的方式、方法各式各樣，從而關(guān)于移動(dòng)對(duì)象查詢處理技術(shù)的研究近年來(lái)一直是一個(gè)十分活躍的主題。最近，研究者注意到了移動(dòng)對(duì)象位置數(shù)據(jù)蘊(yùn)含著不確定性，為了捕獲不確定性，許多有代表性的模型相繼被提出，并且針對(duì)移動(dòng)對(duì)象的概率查詢處理也得到了大量的關(guān)注，例如概率范圍查詢、概率最近鄰查詢、概

2、率地平線查詢等等?？v觀移動(dòng)對(duì)象概率查詢處理技術(shù)的發(fā)展歷程，我們發(fā)現(xiàn)存在的工作大致可以歸為兩大類(lèi)：一類(lèi)是假定對(duì)象沒(méi)有任何限制的自由運(yùn)動(dòng)在二維空間；另外一類(lèi)是假定對(duì)象按照預(yù)設(shè)定的路徑運(yùn)動(dòng)在道路網(wǎng)絡(luò)中。這兩類(lèi)工作已經(jīng)有大量的研究結(jié)果被報(bào)道，然而，關(guān)于空間受限移動(dòng)對(duì)象的概率查詢處理，很少有相關(guān)的報(bào)道。鑒于這一原因，本文以空間受限移動(dòng)對(duì)象作為研究客體，考慮如何有效地回答概率查詢，并探討其他相關(guān)的問(wèn)題。本文的創(chuàng)造性研究成果主要有：
　?。?）

3、提出了面向空間受限不確定移動(dòng)對(duì)象的概率范圍查詢，分析了該問(wèn)題的特性，證明了簡(jiǎn)單地適應(yīng)存在的方法是不可行的，并發(fā)展了有效的解，其關(guān)鍵思想是使用一種稱(chēng)之為前置逼近的策略。此外，基于兩個(gè)重要的洞悉，進(jìn)一步優(yōu)化了我們的方法。實(shí)驗(yàn)結(jié)果說(shuō)明了提出方法的優(yōu)越性，同時(shí)報(bào)告了一個(gè)額外的發(fā)現(xiàn)，即基于預(yù)計(jì)算的方法消耗較長(zhǎng)的預(yù)計(jì)算時(shí)間。這一額外的發(fā)現(xiàn)為將來(lái)的研究提供了重要的指示信號(hào)。
　?。?）提出了顯式和隱式的約束空間概率閾值范圍查詢，闡明了傳統(tǒng)的概率

4、閾值范圍查詢技術(shù)不適用于我們的情形。為此，發(fā)展了一套新的技術(shù)回答顯式的查詢，其關(guān)鍵的思想是交換幾何操作的順序、以及采用多步方式計(jì)算呈現(xiàn)的概率。隨后，擴(kuò)展這些技術(shù)回答隱式查詢，其中增強(qiáng)的多步機(jī)制被提出。進(jìn)一步地，基于新的洞悉”不同的候選移動(dòng)對(duì)象可能共享相同的候選局限區(qū)域”，繼續(xù)優(yōu)化了提出的方法。此外，對(duì)提出的算法給出了嚴(yán)格的理論分析，并展示了這些技術(shù)易于擴(kuò)展到處理其他概率閾值查詢。最后，通過(guò)大量的實(shí)驗(yàn)驗(yàn)證了提出方法的效率和有效性，且進(jìn)一步

5、說(shuō)明了顯式和隱式查詢的區(qū)別。
　?。?）提出了移動(dòng)對(duì)象可達(dá)區(qū)域計(jì)算問(wèn)題，證明了所謂的大致解是不正確的。首先發(fā)展了一個(gè)簡(jiǎn)單版本的算法，其基本思想是將該問(wèn)題歸約為計(jì)算一系列環(huán)可視區(qū)域的布爾并集，該算法復(fù)雜度為O(n3)。通過(guò)分析其主導(dǎo)性的步驟，我們整合了最短路徑圖技術(shù)突破其瓶頸，獲得了一個(gè)O(n2 log n)算法。最后，對(duì)最短路徑圖的特性給出了一些新的洞悉，并利用這些特性構(gòu)造了最終的算法，該算法獲得了O(n log n)最壞情形下的