不確定數(shù)據(jù)集上ToP-k查詢及優(yōu)化算法的研究.pdf

1、Top-k查詢技術(shù)應(yīng)用廣泛，其目標(biāo)是根據(jù)用戶自定義的打分函數(shù)找出數(shù)據(jù)集中評(píng)價(jià)最高的k個(gè)結(jié)果。在傳統(tǒng)的確定性數(shù)據(jù)庫(kù)中，Top-k查詢具有明確的語(yǔ)義，學(xué)術(shù)界也已經(jīng)提出了多種有效的查詢優(yōu)化方法。然而，隨著數(shù)據(jù)采集和處理技術(shù)的不斷發(fā)展，越來越多的應(yīng)用領(lǐng)域發(fā)現(xiàn)了不確定性數(shù)據(jù)，如無(wú)線傳感器網(wǎng)絡(luò)、RFID系統(tǒng)、移動(dòng)計(jì)算等等。不確定性數(shù)據(jù)逐漸得到了人們的關(guān)注，成為了學(xué)術(shù)界的研究熱點(diǎn)。
　　在傳統(tǒng)數(shù)據(jù)庫(kù)中，Top-k查詢的結(jié)果僅僅依靠打分函數(shù)值來排

2、序，而基于不確定性數(shù)據(jù)集上的Top-k查詢處理，需要綜合考慮打分函數(shù)值及其取值概率。因此，傳統(tǒng)Top-k查詢技術(shù)不能直接應(yīng)用于不確定性數(shù)據(jù)集上。以往的研究，針對(duì)不同的應(yīng)用背景，已經(jīng)提出了多種不確定數(shù)據(jù)集上的Top-k查詢語(yǔ)義，然而針對(duì)特定語(yǔ)義不確定性Top-k查詢處理問題依然是學(xué)術(shù)界面臨的巨大挑戰(zhàn)。另外，現(xiàn)有的不確定性數(shù)據(jù)管理和Top-k查詢技術(shù)多是針對(duì)集中式數(shù)據(jù)庫(kù)或數(shù)據(jù)流，而不確定性數(shù)據(jù)多來自于分布式系統(tǒng)，典型地如無(wú)線傳感器網(wǎng)絡(luò)、P2

3、P系統(tǒng)等等。如果將集中式Top-k查詢處理技術(shù)簡(jiǎn)單地移植到分布式存儲(chǔ)的不確定數(shù)據(jù)集上，那么首先就需要從分布節(jié)點(diǎn)上收集所有的數(shù)據(jù)到中心節(jié)點(diǎn)，然后完成最終查詢，將給系統(tǒng)帶來巨大的通信開銷、存儲(chǔ)代價(jià)、及時(shí)間延遲。實(shí)際上，Top-k查詢具有顯著的特點(diǎn):查詢結(jié)果僅占全體數(shù)據(jù)集的極小部分。在某些系統(tǒng)中，節(jié)點(diǎn)資源非常有限，采用上述的集中式查詢處理算法，也會(huì)造成巨大的不必要的節(jié)點(diǎn)資源損失。
　　從上面的分析可以看出，集中式不確定性數(shù)據(jù)集上的Top

4、-k查詢，以及分布式環(huán)境下的不確定性數(shù)據(jù)的Top-k查詢，無(wú)論從查詢語(yǔ)義和查詢優(yōu)化技術(shù)上都亟待進(jìn)一步研究和解決。本文即針對(duì)上述問題展開研究，主要完成的工作有:
　　首先，提出了確定U-Topk最小范圍查詢的MSS4U-Topk算法，通過縮減U-Topk查詢的數(shù)據(jù)集，可以大幅度地減少可能世界模型規(guī)模。另外，將MSS4U-Topk算法作為U-Topk查詢處理的預(yù)處理過程，可以確定U-Topk查詢必須掃描的元組范圍，進(jìn)而確定需遍歷的可能

5、世界模型空間規(guī)模，這為U-Topk查詢處理算法的選擇提供了重要依據(jù)。
　　其次，針對(duì)屬性級(jí)不確定性提出了U-Topk查詢優(yōu)化算法APT4U-Topk。提出了可能世界模型概率閥值的概念，當(dāng)計(jì)算的可能世界模型概率等于閥值時(shí)，可以確定后續(xù)可能世界模型概率皆小于閥值，終止算法，從而實(shí)現(xiàn)快速找出U-Topk查詢結(jié)果的目標(biāo)。通過實(shí)驗(yàn)，可以看出APT4U-Topk算法有效的提高了U-Topk查詢效率。進(jìn)一步將APT4U-Topk算法應(yīng)用到分布式

6、環(huán)境中，提出了DAPT4UTop-k算法。DAPT4U-Topk算法避免了節(jié)點(diǎn)端發(fā)送全部本地元組，有效地減少分布式系統(tǒng)中的通信開銷。但是，在某些數(shù)據(jù)集情況下，節(jié)點(diǎn)依然需要上傳大部分?jǐn)?shù)據(jù)，DAPT4U-Topk算法的通信代價(jià)和時(shí)間復(fù)雜度依然較高。
　　針對(duì)在某些數(shù)據(jù)集上U-Topk查詢需要展開全部可能世界模型，查詢優(yōu)化算法失效的情況，論文在最后一個(gè)部分提出了MPUTop-k查詢優(yōu)化算法。MPUTop-k的語(yǔ)義是返回概率最大的可能世界

7、模型實(shí)例的Top-k向量。因?yàn)镸PUTop-k不需要計(jì)算全部可能世界模型概率，因此更具有實(shí)際應(yīng)用價(jià)值。進(jìn)一步，我們將MPUTop-k查詢優(yōu)化算法應(yīng)用到分布式環(huán)境中，提出了DMPUTop-k算法。由于全局MPUTop-k算法和各個(gè)結(jié)點(diǎn)局部MPUTop-k算法的返回的結(jié)果相同，因此DMPUTop-k算法可應(yīng)用于多跳地分布式環(huán)境中。特別地，文中證明了如果可能世界模型空間中某個(gè)實(shí)例的概率不小于0.5時(shí)，從查詢結(jié)果的角度來看，MPUTop-k和U