發(fā)布訂閱系統(tǒng)中壓縮感知匹配算法研究

同濟(jì)大學(xué) 陶 金 饒衛(wèi)雄

發(fā)布訂閱系統(tǒng)中壓縮感知匹配算法研究

同濟(jì)大學(xué) 陶 金 饒衛(wèi)雄

布爾表達(dá)式常用于表達(dá)發(fā)布訂閱系統(tǒng)中的訂閱條件及發(fā)布內(nèi)容。由于海量信息的多樣性，系統(tǒng)經(jīng)常表現(xiàn)出高維的特征。如何對海量數(shù)據(jù)進(jìn)行有效索引并快速找出有用信息對當(dāng)前研究提出巨大挑戰(zhàn)。本文提出一個壓縮感知的匹配算法從時間和空間兩方面來優(yōu)化系統(tǒng)性能。通過編碼壓縮降低空間開銷，然后設(shè)計壓縮感知的匹配算法加速匹配過程。本文最后與相關(guān)工作進(jìn)行對比實驗驗證本文方案的性能。

發(fā)布/訂閱系統(tǒng)；高維稀疏；壓縮感知；匹配算法

1.引言

布爾表達(dá)式（BE）目前已廣泛用于表示發(fā)布/訂閱系統(tǒng)中應(yīng)用的訂閱條件和發(fā)布信息，比如定向廣告系統(tǒng)、信息過濾應(yīng)用和財政新聞簡訊[1],[2],[4]。由于需求目標(biāo)及數(shù)據(jù)特征的多樣性，系統(tǒng)經(jīng)常面臨高維稀疏語義空間的挑戰(zhàn)。計算機(jī)一方面面臨大批量數(shù)據(jù)存儲壓力的同時還面臨著快速從海量數(shù)據(jù)中找出有用信息的挑戰(zhàn)，這一點對于某些時效性非常高的應(yīng)用如在線廣告推薦系統(tǒng)尤為重要。

當(dāng)前許多方案在解決小批量低維數(shù)據(jù)時，可以通過構(gòu)建多維樹形結(jié)構(gòu)[6],[7],[8]來實現(xiàn)很好的性能。但是當(dāng)系統(tǒng)中數(shù)據(jù)維度急劇增加時，大多數(shù)方案中索引結(jié)構(gòu)空間開銷急劇增加，同時匹配效率大大降低，不具備處理高維稀疏數(shù)據(jù)的能力。本文在研究數(shù)據(jù)特征的基礎(chǔ)上提出通過編碼壓縮降低數(shù)據(jù)存儲開銷，同時基于壓縮后的數(shù)據(jù)進(jìn)行快速的匹配處理，表現(xiàn)出良好的適應(yīng)性。

2.基礎(chǔ)數(shù)據(jù)模型

布爾表達(dá)式中的謂詞：一個謂詞由屬性A，操作符以及操作數(shù)O組成。訂閱條件S的布爾表達(dá)式由一系列謂詞的合取組成：。為方便將訂閱與布爾表達(dá)式等價轉(zhuǎn)換，需要對范圍操作符按一定粒度劃分到多個離散取值情況當(dāng)中。發(fā)布事件E：。

布爾表達(dá)式匹配：當(dāng)任何出現(xiàn)在訂閱S中的屬性A都出現(xiàn)在事件E中，并且事件E中屬性A的取值都滿足訂閱S中相應(yīng)約束，則稱訂閱S與事件E匹配。給定一個訂閱的集合和一個發(fā)布事件E，發(fā)布/訂閱系統(tǒng)的匹配處理目標(biāo)就是找到所有的滿足的訂閱S使得S與E匹配。

設(shè)，每個元素表示某屬性和一個取值的復(fù)合變量，A表示整個屬性取值空間。表示訂閱條件向量。關(guān)系矩陣為訂閱條件的布爾矩陣表達(dá)。為方便后續(xù)匹配處理，此處將訂閱條件按謂詞數(shù)量分組，每組再構(gòu)建布爾矩陣。由此得到個布爾矩陣，表示所有訂閱條件中謂詞數(shù)量的最大值。

3.編碼壓縮

為降低上述高維稀疏布爾矩陣的存儲開銷，本文將矩陣中元素視為數(shù)據(jù)的二進(jìn)制表達(dá)，每行元素按機(jī)器字長劃分為組，每組編碼為一個數(shù)據(jù)（表示為），同時不存儲編碼后為0的數(shù)據(jù)。該方案可將空間開銷降低到原始矩陣空間開銷的至少分之一。

4.索引結(jié)構(gòu)

本文設(shè)計的索引結(jié)構(gòu)主要分為兩大部分：屬性空間和編碼列表。屬性空間對應(yīng)布爾矩陣中的A，A中每條記錄指向編碼列表中的一行數(shù)據(jù)。編碼列表對應(yīng)布爾矩陣的一行行數(shù)據(jù)，其中,。每個編碼項中表示每組數(shù)據(jù)最左邊訂閱的id，表示編碼后的數(shù)據(jù)。通過加偏移量即可還原出每個原始數(shù)據(jù)。

5.壓縮感知匹配算法

給定上述索引結(jié)構(gòu)，本文提出一個基于壓縮感知的匹配算法。給定一個事件e和布爾索引（大小為,）。由布爾表達(dá)式匹配定義可知，當(dāng)事件e的大小|e|小于訂閱S的大小|S|時，不存在匹配。由于構(gòu)造索引時對訂閱按大小進(jìn)行分組，所以可以首先篩選出的索引，再分兩步進(jìn)行匹配處理。

第一步，給定大小為的索引，對事件e中的多個,可以根據(jù)屬性空間查找對應(yīng)的編碼列表，若找出的編碼列表數(shù)量（第1行）,則該事件e在當(dāng)前索引中不存在匹配。否則進(jìn)入第二步。

第二步，給定當(dāng)前索引大小和第一步選出的個編碼列表集合(表示為)。算法將遍歷編碼列表,利用快速的按位與或操作進(jìn)行元素檢測（第8-11行）并記錄，最后輸出一個由組成的集合S。S中的鍵值對可以解碼并還原出壓縮前成功匹配的訂閱id。

整個算法的思路是：用一個有序列表H記錄候選列表中的當(dāng)前位置的編碼項數(shù)據(jù)，將H中數(shù)據(jù)按排序，每次循環(huán)過程中，若到間的編碼項數(shù)量不小于，就對這些編碼項中的，分別判斷第位上的元素1數(shù)量是否大于等于，若是則保存到最終結(jié)果S中。若數(shù)量低于(第7行)，則將后移，進(jìn)入下一次循環(huán)。

6.實驗對比

為了驗證本方案性能，決定與當(dāng)前最新研究成果BETree[3],[4]進(jìn)行對比。在同一臺服務(wù)器上本文使用BE-Tree的數(shù)據(jù)生成器，通過調(diào)參生成發(fā)布事件和BE訂閱數(shù)據(jù)。

大多數(shù)實際的pub/sub應(yīng)用[5,3,4]都表明用戶興趣即系統(tǒng)中出現(xiàn)的訂閱條件通常都會服從傾斜的冪律分布：一小部分屬性和相關(guān)的取值在大量的訂閱條件中會頻繁出現(xiàn)；而大量屬性和取值只會在少量訂閱條件中出現(xiàn)。給定這樣的數(shù)據(jù)分布，相關(guān)矩陣中元素1的分布同樣偏斜。因此除了訂閱數(shù)據(jù)總量，我們還將數(shù)據(jù)分布作為變量驗證數(shù)據(jù)分布對實驗結(jié)果的影響。

圖1 訂閱數(shù)量對空間和時間的影響趨勢

圖2 參數(shù)對空間和時間的影響趨勢

從圖1中我們可以看到：隨著訂閱數(shù)量的增加二者都需要更多存儲空間來存儲索引結(jié)構(gòu)，平均匹配時間也隨需要處理的數(shù)據(jù)量增加而上升。從圖2，我們可以看到隨著參數(shù)增大，二者的儲存空間都逐漸降低，匹配時間也依次減少，原因在于隨著參數(shù)增大，數(shù)據(jù)分布變得更加緊密，索引結(jié)構(gòu)開銷和匹配處理開銷都因此逐漸減低。需要注意的是，同等條件下本文方案性能都優(yōu)于BE-Tree。

7.結(jié)論

本文針對發(fā)布/訂閱系統(tǒng)中的高維稀疏數(shù)據(jù)，提出了有效的編碼壓縮方案降低索引結(jié)構(gòu)空間開銷，并在此基礎(chǔ)上提出壓縮感知的匹配算法實現(xiàn)高效匹配性能。后續(xù)將針對分布式環(huán)境中索引結(jié)構(gòu)及算法進(jìn)行研究。

[1]A.Machanavajjhala,E.Vee,M.N.Garofalakis,and J. Shanmugasundaram.Scalable ranked publish/subscribe.PVLDB, 1(1):451–462,2008.

[2]M.Sadoghi and H.Jacobsen. Be-tree: an index structure to efficiently match boolean expressions over high-dimensional discrete space. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2011, Athens, Greece, June 12-16,2011,pages 637–648,2011.

[3]M.Sadoghi and H.Jacobsen. Analysis and optimization for Boolean expression indexing. ACM Trans. Database Syst., 38(2):8, 2013.

[4]S.Whang,C.Brower,J.Shanmugasundaram,S.Vassilvitskii, E.Vee, R.Yerneni,and H.Garcia-Molina. Indexing boolean expressions.PVLDB, 2(1):37–48, 2009.

[5]H.Liu,V.Ramasubramanian, and E. G.Sirer. Client behavior and feed characteristics of rss, a publish-subscribe system for web micronews.In Internet Measurment Conference, pages 29–34,2005.

[6]S.Bianchi,P.Felber,M.Gradinariu Potop-Butucaru: Stabilizing Distributed R-Trees for Peer-to-Peer Content Routing. IEEE Trans. Parallel Distributed System (TPDS) 21(8): 1175-1187 (2010).

[7]A.Riabov,Z.Liu,JL.Wolf, PS.Yu,L Zhang:New Algorithms for Content-Based Publication-Subscription Systems. ICDCS 2003: 678-686.

[8]W.Rao,L.Chen,Ada WC.Fu,H.Chen,F.Zou:On Efficient Content Matching in Distributed Pub/Sub Systems.INFOCOM 2009:756-764.