同濟(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)出高維的特征。如何對(duì)海量數(shù)據(jù)進(jìn)行有效索引并快速找出有用信息對(duì)當(dāng)前研究提出巨大挑戰(zhàn)。本文提出一個(gè)壓縮感知的匹配算法從時(shí)間和空間兩方面來(lái)優(yōu)化系統(tǒng)性能。通過(guò)編碼壓縮降低空間開(kāi)銷(xiāo)，然后設(shè)計(jì)壓縮感知的匹配算法加速匹配過(guò)程。本文最后與相關(guān)工作進(jìn)行對(duì)比實(shí)驗(yàn)驗(yàn)證本文方案的性能。

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

1.引言

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

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

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

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

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

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

3.編碼壓縮

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

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

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

5.壓縮感知匹配算法

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

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

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

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

6.實(shí)驗(yàn)對(duì)比

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

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

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

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

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

7.結(jié)論

本文針對(duì)發(fā)布/訂閱系統(tǒng)中的高維稀疏數(shù)據(jù)，提出了有效的編碼壓縮方案降低索引結(jié)構(gòu)空間開(kāi)銷(xiāo)，并在此基礎(chǔ)上提出壓縮感知的匹配算法實(shí)現(xiàn)高效匹配性能。后續(xù)將針對(duì)分布式環(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.