同構對稱發(fā)布-訂閱系統(tǒng)中ToP-k算法的研究與實現.pdf

1、近年來，隨著互聯(lián)網技術發(fā)展，同構對稱發(fā)布/訂閱系統(tǒng)的應用也越來越普及。由于在同構對稱發(fā)布/訂閱系統(tǒng)中，產生的候選環(huán)匹配結果集很大，特別是在大型的系統(tǒng)中，可能是海量的，不利于用戶對候選結果的選擇利用。如何快速、高效的為用戶推薦k個最優(yōu)的候選環(huán)匹配是同構對稱發(fā)布/訂閱系統(tǒng)中研究的關鍵問題之一。在同構對稱發(fā)布/訂閱系統(tǒng)的不同應用中，有時匹配結果可以調用打分函數為其打分，依據分值排序求出前k個最優(yōu)的。有時無法調用打分函數打分，不能對其排序。為此

2、本文分別提出了面向匹配結果不可排序的Top-k查詢算法和面向匹配結果可以排序的Top-k查詢算法。
　　針對匹配結果不能通過調用打分函數打分的問題，本文對相關的基礎理論工作分析與總結，尋求解決問題的相關技術。提出了基于k-支配Skyline查詢的面向匹配結果不可排序的Top-k查詢算法。首先擴展了同構對稱發(fā)布/訂閱模型;然后對算法基本思想以及基本操作做了詳細的描述;最后，本文在模擬環(huán)境中對算法做了多種評估分析比較試驗，從訂閱數量、

3、維度、數據分布、選擇度等方面分析實驗結果，實驗表明本文提出的算法查全率和查準率都在94％以上。
　　匹配結果可以通過調用打分函數打分時，打分函數復雜度不同算法性能可能也不一樣。本文針對高復雜度的打分函數，提出了基于高復雜度打分函數的面向匹配結果可以排序的Top-k查詢算法。該算法策略是基于在計算機中一次比較運算時間效率優(yōu)于一次算術運算。所以本算法核心就是減少了調用打分函數的次數，打分函數復雜度較高時，候選匹配各維上比較一次的操作總