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

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

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

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

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