同構(gòu)對(duì)稱發(fā)布-訂閱系統(tǒng)中ToP-k算法的研究與實(shí)現(xiàn).pdf

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

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

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