發布訂閱系統中壓縮感知匹配算法研究

同濟大學 陶 金 饒衛雄

發布訂閱系統中壓縮感知匹配算法研究

同濟大學 陶 金 饒衛雄

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

發布/訂閱系統；高維稀疏；壓縮感知；匹配算法

1.引言

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

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

2.基礎數據模型

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

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

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

3.編碼壓縮

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

4.索引結構

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

5.壓縮感知匹配算法

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

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

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

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

6.實驗對比

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

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

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

圖2 參數對空間和時間的影響趨勢

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

7.結論

本文針對發布/訂閱系統中的高維稀疏數據，提出了有效的編碼壓縮方案降低索引結構空間開銷，并在此基礎上提出壓縮感知的匹配算法實現高效匹配性能。后續將針對分布式環境中索引結構及算法進行研究。

[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.