位置及文本相關(guān)查詢處理及驗證策略研究.pdf

1、隨著無線通信技術(shù)的快速發(fā)展和移動終端設(shè)備的不斷普及，位置相關(guān)查詢（Location Dependent Queries:LDQs）作為基于位置的服務(wù)（Location Based Services:LBSs）的支撐技術(shù)之一，已經(jīng)成為學(xué)術(shù)界和工業(yè)界共同關(guān)注的熱點問題。鑒于不確定數(shù)據(jù)廣泛存在于LBSs中，以及Top-k Dominating查詢是一種被廣泛運用的LDQ，人們開始研究不確定數(shù)據(jù)上的Top-k Dominating查詢處理方法，

2、并取得了一些研究成果。但是這些研究只限于靜態(tài)概率數(shù)據(jù)庫，它們不能處理不確定數(shù)據(jù)流環(huán)境下的Top-k Dominating查詢，目前國際上還未見針對不確定數(shù)據(jù)流環(huán)境下的Top-k Dominating查詢的相關(guān)研究。為了高效地提供基于位置的服務(wù)，人們通常采用空間數(shù)據(jù)庫外包模式來提供查詢服務(wù)。在該模式中，由于服務(wù)提供者（Services Provider:SP）并不是真正的數(shù)據(jù)擁有者（Data Owner:DO），它可能受利益的驅(qū)使或者其本

3、身缺陷，返回給客戶端的結(jié)果可能是不正確的或者不可信任的。此外，查詢結(jié)果在傳輸過程中，可能被第三方惡意攻擊或者篡改，導(dǎo)致客戶端接收到的結(jié)果是錯誤的和不可信任的。因此，針對位置相關(guān)查詢設(shè)計高效的認(rèn)證策略具有重要意義。隨著位置定位技術(shù)和位置共享服務(wù)的發(fā)展，在基于位置的服務(wù)中產(chǎn)生了大量的空間文本對象，針對空間文本對象的處理技術(shù)應(yīng)運而生，人們也提出了一些研究成果。但到目前為止，這些研究多數(shù)局限于歐氏空間，在歐氏空間下的相關(guān)技術(shù)是不能通過簡單的修改

4、便能應(yīng)用到路網(wǎng)環(huán)境中，因此，研究路網(wǎng)中的空間文本對象處理技術(shù)具有較高的研究價值。
　　首次討論了不確定數(shù)據(jù)流的Top-k Dominating查詢的處理問題，定義了如何計算不確定數(shù)據(jù)的支配分?jǐn)?shù)，鑒于計算該支配分?jǐn)?shù)代價較大，提出了由不確定數(shù)據(jù)的分?jǐn)?shù)區(qū)間來替代支配分?jǐn)?shù)的策略，并設(shè)計了逐步壓縮分?jǐn)?shù)區(qū)間的方法，基于滑動窗口模型提出了SWPTD算法實現(xiàn)對不確定數(shù)據(jù)流條件下的Top-k Dominating查詢（PTOPK）。分析發(fā)現(xiàn)，每次滑

5、動窗口移動將使得SWPTD重新計算PTOPK，前一個時刻的計算結(jié)果信息沒有被充分利用，當(dāng)滑動窗口較大時，SWPTD算法效率會降低。鑒于并非所有的非PTOPK對象在下一個時刻都能成為查詢結(jié)果（PTOPK），于是計算每個非PTOPK對象的最小時間間隔，在該時間間隔內(nèi)，不需考察該對象，基于此思想提出了PEA算法。模擬實驗表明PEA算法相對更為高效，具有一定的應(yīng)用價值。
　　在眾多位置相關(guān)查詢（也稱空間查詢）中，反向k近鄰查詢（RkNN）

6、被認(rèn)為是最基礎(chǔ)和應(yīng)用最廣的查詢，它廣泛運用于基于位置的服務(wù)、市場分析和決策支持?；谝陨弦蛩?，首次研究了RkNN查詢的認(rèn)證問題，提出了SP端處理算法，實現(xiàn)對RkNN查詢結(jié)果的搜索并基于Infl uencezone(Zk)構(gòu)建緊湊的認(rèn)證對象VO。同時提出兩種客戶端處理算法（IZ-Auth，AIZ-Auth），其中IZ-Auth是基于VO重新計算RkNN從而實現(xiàn)認(rèn)證。鑒于位于Zk內(nèi)的對象就是RkNN結(jié)果，AIZ-Auth基于對Infl ue

7、ncezone的認(rèn)證實現(xiàn)對RkNN查詢結(jié)果的認(rèn)證。理論分析了算法的復(fù)雜度。實驗結(jié)果表明，所提出的算法能有效地對單色和雙色RkNN查詢實施認(rèn)證，AIZ-Auth算法性能要優(yōu)于相關(guān)算法。
　　首次研究了路網(wǎng)中的空間文本反向k近鄰查詢問題（RSTkNN），為了高效地檢索候選對象集Scan，提出了三種剪枝方法和路網(wǎng)擴展終止條件，介紹了RSTkNN查詢處理框架。為了驗證候選對象，首先提出了基于路網(wǎng)擴展的NE-RSTkNN驗證算法；為了克服該