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

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

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

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

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

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

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

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