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

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

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

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

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

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