同構(gòu)發(fā)布-訂閱系統(tǒng)的系統(tǒng)最優(yōu)化與并行查詢算法的研究與實現(xiàn).pdf

1、發(fā)布/訂閱系統(tǒng)是一種提供給信息的生產(chǎn)者和消費(fèi)者互動平臺的分布式中間件系統(tǒng)，其中同構(gòu)發(fā)布/訂閱系統(tǒng)的一類應(yīng)用是易物服務(wù)、物品交換等，該系統(tǒng)的目的是使盡可能多的用戶參與匹配、提高系統(tǒng)的收益能力，因此逐漸獲得了電商的關(guān)注。近年來，云計算作為計算平臺中一種新型模型出現(xiàn)，覆蓋了多數(shù)計算領(lǐng)域。云計算的興起為高效、大規(guī)模計算平臺的產(chǎn)生提供了可能性。如何在發(fā)布/訂閱系統(tǒng)中使盡可能多的用戶參與匹配并且使系統(tǒng)具有良好的擴(kuò)展性是發(fā)布/訂閱系統(tǒng)的追求目標(biāo)，也是

2、發(fā)布/訂閱系統(tǒng)的關(guān)鍵技術(shù)。本文主要工作包含兩部分，第一是針對系統(tǒng)最優(yōu)化問題設(shè)計出高效的算法，找出盡可能多的訂閱用戶成功參與匹配，另一工作是利用云計算平臺的計算資源和技術(shù)，設(shè)計出具有良好擴(kuò)展性的發(fā)布/訂閱系統(tǒng)。
　　針對提高系統(tǒng)中參與匹配用戶數(shù)目的系統(tǒng)最優(yōu)化問題，本文應(yīng)用了兼顧用戶滿意度的貪心算法和啟發(fā)式算法?，F(xiàn)有的發(fā)布/訂閱相關(guān)的研究中，針對系統(tǒng)最優(yōu)化問題的研究相對較少。已知在環(huán)匹配長度大于等于3的前提下，系統(tǒng)最優(yōu)化問題是NPC問

3、題，為系統(tǒng)找到一個近似最優(yōu)解是本文的一個研究重點。而本文主要從系統(tǒng)收益和用戶滿意度兩個角度出發(fā)，應(yīng)用了兼顧兩者的貪心算法和啟發(fā)式算法。其中，貪心算法從考慮用戶滿意度的角度獲取系統(tǒng)近似最優(yōu)解;而啟發(fā)式算法中，針對長度為3的環(huán)匹配提出了兩種歸約規(guī)則，通過歸約規(guī)則逐步降低問題規(guī)模，并最終獲取系統(tǒng)近似最優(yōu)解。實驗結(jié)果證明，兩種算法執(zhí)行時間基本相同，啟發(fā)式算法的結(jié)果集中包含的訂閱數(shù)比貪心算法結(jié)果集中訂閱數(shù)多出9％到24％。
　　針對發(fā)布/訂

4、閱系統(tǒng)擴(kuò)展性這一問題，本文提出了基于Twitter Storm的發(fā)布/訂閱并行框架。目前雖然存在部分有關(guān)于云計算和發(fā)布/訂閱相結(jié)合的研究工作，還沒有關(guān)于實時處理系統(tǒng)Twitter Storm與發(fā)布/訂閱的整合工作。本文提出的基于Twitter Storm的發(fā)布/訂閱框架的目的是在大規(guī)模數(shù)據(jù)下，使事件與訂閱進(jìn)行快速的匹配。首先，對于云環(huán)境下缺少有效的索引結(jié)構(gòu)，本文針對訂閱數(shù)據(jù)建立基于HBase存儲的R-樹索引，通過維轉(zhuǎn)換和空間填充技術(shù)，可