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

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

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

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

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

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

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

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