一種基于空間文本信息流的分布式的發(fā)布訂閱算法

周澤寧

摘?要：發(fā)布訂閱系統(tǒng)是進(jìn)行發(fā)布的事件和訂閱消息之間的匹配系統(tǒng)。首先需要對(duì)訂閱消息進(jìn)行聚類(lèi)操作，按照聚類(lèi)結(jié)果，找到事件所屬類(lèi)別，隨后在類(lèi)別中，找尋和事件匹配的訂閱。本文提出了一個(gè)即時(shí)的發(fā)布訂閱的算法，統(tǒng)籌空間信息和事件屬性信息，不僅可以即時(shí)地處理事件和訂閱的匹配操作，也可以在分布式環(huán)境上即時(shí)地進(jìn)行訂閱的更新和類(lèi)別的更新。并且可以在沒(méi)有先驗(yàn)知識(shí)的情況下即時(shí)地進(jìn)行聚類(lèi)操作和匹配操作。設(shè)計(jì)一個(gè)分布式的系統(tǒng)，將發(fā)布訂閱算法部署其上，并且提出了在分布式系統(tǒng)上該算法的負(fù)載均衡策略。隨后通過(guò)自建集群，使用真實(shí)的數(shù)據(jù)，實(shí)驗(yàn)驗(yàn)證本文提出的發(fā)布訂閱算法。

關(guān)鍵詞： 發(fā)布訂閱系統(tǒng);分布式系統(tǒng);聚類(lèi)算法

文章編號(hào)： 2095-2163（2021）01-0046-06 中圖分類(lèi)號(hào)：TP391.1 文獻(xiàn)標(biāo)志碼：A

【Abstract】The publish and subscribe system is a matching system between published events and subscribed messages. First， it is necessary to perform a clustering operation on the subscription messages， find the category to which the event belongs according to the clustering result， and then find the subscription that matches the event in the category. This paper proposes an instant publish and subscribe algorithm， which coordinates the spatial information and event attribute information. It can not only handle the matching operation of events and subscriptions in real time， but also update subscriptions and categories in a distributed environment. In addition， clustering and matching operations can be performed immediately without prior knowledge. A distributed system is designed， the publish-subscribe algorithm is deployed on it， and the load balancing strategy of the algorithm is put forward on the distributed system. Therefore through the self-built cluster， using real data， the publish and subscribe algorithm proposed in this article is verified in the experiments.

【Key words】publish and subscribe system; distributed system; clustering algorithm

0 引?言

發(fā)布訂閱系統(tǒng)主要目的是方便事件發(fā)布者和事件訂閱者在網(wǎng)上進(jìn)行信息交換這一過(guò)程，事件的訂閱者持續(xù)關(guān)注某一特定區(qū)域內(nèi)的特定事件，事件的發(fā)布者將事件發(fā)生的空間位置和事件發(fā)布到網(wǎng)上，隨后這些事件和事件訂閱者的訂閱信息進(jìn)行匹配并將符合要求的事件推送給訂閱者。

中央服務(wù)器上基于空間屬性信息的發(fā)布訂閱算法[1-8]，使用樹(shù)狀結(jié)構(gòu)按照空間索引訂閱數(shù)據(jù)，以加速空間屬性事件和空間屬性訂閱的比較。許多分布式系統(tǒng)[9-12]使用現(xiàn)有的空間索引將數(shù)據(jù)劃分到不同的服務(wù)器，這些系統(tǒng)是基于靜態(tài)數(shù)據(jù)的一次性查詢。

本文提出了一個(gè)沒(méi)有先驗(yàn)知識(shí)、可以即時(shí)處理數(shù)據(jù)流、統(tǒng)籌事件信息和空間信息的發(fā)布訂閱系統(tǒng)，滿足了對(duì)于靈敏度的要求，并且提出了一個(gè)分布式的系統(tǒng)，將基礎(chǔ)的發(fā)布訂閱系統(tǒng)部署其上，滿足了大規(guī)模的數(shù)據(jù)量的要求。

1 基礎(chǔ)發(fā)布訂閱系統(tǒng)

發(fā)布訂閱系統(tǒng)包含發(fā)布的事件和訂閱這兩種數(shù)據(jù)流。在研究中，t表示一個(gè)發(fā)布的事件，包含至少2個(gè)信息：空間位置和屬性文本，可用二元組來(lái)表示：（t.s，t.k）。其中，t.s表示該事件發(fā)生的空間位置，空間位置采用經(jīng)緯度的表達(dá)方式，表示空間中的一個(gè)點(diǎn)。t.k表示該事件的一系列屬性。同樣，q表示一個(gè)訂閱消息，用二元組來(lái)表示：（q.s，q.k）。其中，q.s表示該訂閱發(fā)布者關(guān)注的空間范圍，該數(shù)據(jù)使用的是此次訂閱關(guān)注范圍的最小鄰接矩形。q.k表示訂閱者持續(xù)關(guān)注的屬性信息，該信息是事件匹配時(shí)的屬性要求。

發(fā)布訂閱系統(tǒng)所關(guān)注的是事件和訂閱的匹配過(guò)程。如果滿足t.s在q.s的范圍中，即事件的發(fā)生位置在訂閱的要求的空間范圍之內(nèi)，并且q.kt.k，也就是事件的屬性包含了訂閱要求的事件屬性，則認(rèn)定事件t滿足該訂閱q的要求，就可將事件t分配給該查詢q。

為了節(jié)省大量不必要的匹配操作，本文先是將訂閱進(jìn)行聚類(lèi)操作，將其按照空間信息和事件屬性通過(guò)聚類(lèi)操作獲得眾多類(lèi)別ci（i=1，2，3…），對(duì)到來(lái)的事件，將其分配到訂閱類(lèi)別，再在匹配成功的類(lèi)別中對(duì)訂閱和事件進(jìn)行匹配操作，具體如圖1所示。

事件流進(jìn)入類(lèi)別集合后，首先找到相匹配的類(lèi)別，再和類(lèi)別中的訂閱一一匹配，找到相匹配的訂閱輸出。訂閱流進(jìn)入類(lèi)別集合后，如果進(jìn)行訂閱的增加操作，就通過(guò)聚類(lèi)算法更新類(lèi)別集合;如果是訂閱的刪除操作，就找到該訂閱所屬類(lèi)別，進(jìn)行刪除操作。類(lèi)別的集合最初為空，隨著訂閱的到來(lái)，逐漸通過(guò)聚類(lèi)算法形成類(lèi)別。

2 發(fā)布訂閱系統(tǒng)的聚類(lèi)算法

對(duì)于發(fā)布訂閱系統(tǒng)，至關(guān)重要的就是訂閱的聚類(lèi)算法，因其直接決定聚類(lèi)結(jié)果的優(yōu)劣，并最終影響整個(gè)算法的反應(yīng)速度。本文提出一個(gè)沒(méi)有訓(xùn)練集（在進(jìn)行訂閱和事件的匹配過(guò)程中，同時(shí)進(jìn)行訓(xùn)練）、即時(shí)的聚類(lèi)算法Rt-Cluter （RealTime-Cluter），可以對(duì)接受到的事件和訂閱進(jìn)行即時(shí)的處理。通過(guò)對(duì)比實(shí)驗(yàn)顯示了本算法的有效性。

訂閱和事件包含2種數(shù)據(jù)，分別是：空間信息和屬性信息。本文采取一個(gè)融合2種策略的混合策略。面對(duì)空間信息，文中采取網(wǎng)格的結(jié)構(gòu)來(lái)存儲(chǔ)空間數(shù)據(jù)。面對(duì)事件的屬性信息，文中采取倒排索引的結(jié)構(gòu)。其存儲(chǔ)形式如圖2所示。

Rt-Cluter算法使用相似性和相關(guān)性作為判斷標(biāo)準(zhǔn)。其中，相似性主要解決聚類(lèi)操作中，對(duì)訂閱的聚類(lèi)判斷問(wèn)題。當(dāng)一個(gè)新的需要添加的訂閱q到來(lái)時(shí)，需要按照空間信息和事件的屬性信息對(duì)其進(jìn)行聚類(lèi)操作，將其分配給最相似的一個(gè)類(lèi)別c。本文將會(huì)分別計(jì)算屬性相似性和空間相似性，并對(duì)這2個(gè)相似性采用加權(quán)和的方式進(jìn)行融合。屬性相似性KeySim的計(jì)算公式如下：

其中，key表示屬性，key.Pro表示屬性key在類(lèi)別c的屬性集合c.k中所占的比例，即類(lèi)別c中屬性key的頻數(shù)和類(lèi)別c中所有屬性的頻數(shù)之比。

相應(yīng)地，空間相似性SpatialSim的計(jì)算需要用到如下公式：

其中，ex表示如果類(lèi)別c添加訂閱q，c.s需要擴(kuò)展的大小，c.s表示類(lèi)別c在添加訂閱q之前的最小鄰接矩形的面積大小。

綜上可得，進(jìn)行相似性的比較時(shí)，總體相似性Sim的計(jì)算，要同時(shí)考慮空間和屬性的相似性，其數(shù)學(xué)公式可寫(xiě)為：

其中，α表示權(quán)值（0≤α≤1），可以根據(jù)對(duì)屬性或者空間的重視程度進(jìn)行調(diào)整。

對(duì)于等待被分配的訂閱，將其分配給相似值最大的類(lèi)別。但是如果最大的相似度仍然足夠?。ㄐ∮谝粋€(gè)閾值），本文則為其創(chuàng)造一個(gè)新類(lèi)別，并將該新類(lèi)別分配到與其最為相似的類(lèi)別所在的工作節(jié)點(diǎn)中，如此一來(lái)就保證了最相似的類(lèi)別將處在同一個(gè)工作節(jié)點(diǎn)中，在后續(xù)數(shù)據(jù)傳輸上節(jié)省了資源。

在聚類(lèi)算法中，除了新類(lèi)別的創(chuàng)建，還需要進(jìn)行類(lèi)別融合，使用閾值CMaxNumTh來(lái)表示所能擁有的最大類(lèi)別數(shù)量，一旦類(lèi)別數(shù)量超過(guò)該值，就要進(jìn)行類(lèi)別融合操作。本文使用相關(guān)性來(lái)做類(lèi)別融合研究?？傮w而言，如果2個(gè)訂閱q0和q1被同一個(gè)發(fā)布的事件t所匹配并且匹配成功，那么就認(rèn)為這2個(gè)訂閱具有一點(diǎn)相關(guān)性，即：Correlation（q0，q1） = 1。需要進(jìn)行類(lèi)別融合操作時(shí)，將相關(guān)性最大的2個(gè)類(lèi)別進(jìn)行融合。

3 分布式系統(tǒng)設(shè)計(jì)與部署

網(wǎng)絡(luò)中數(shù)據(jù)量不斷擴(kuò)大，單處理器無(wú)法滿足現(xiàn)實(shí)要求，本文提出了一個(gè)分布式系統(tǒng)來(lái)承載發(fā)布訂閱算法，將分布式系統(tǒng)下的發(fā)布訂閱算法命名為DRt-Cluster（Distributed-Realtime-Cluster）。其邏輯結(jié)構(gòu)如圖3所示。

該系統(tǒng)中包含有2類(lèi)節(jié)點(diǎn)，分別是聚類(lèi)節(jié)點(diǎn)di（0

（1）聚類(lèi)節(jié)點(diǎn)。主要進(jìn)行聚類(lèi)操作，功能如下：

① 對(duì)于事件t，在聚類(lèi)節(jié)點(diǎn)中，同各個(gè)類(lèi)別的特征相比較，找尋可能存在與其相匹配的訂閱所在的類(lèi)別。

② 對(duì)于訂閱的增加，為其找尋歸屬的唯一類(lèi)別，進(jìn)行類(lèi)別更新的相應(yīng)操作。

③ 對(duì)于訂閱的刪除，需要找尋可能包含該事件的類(lèi)別，并進(jìn)行刪除操作。

（2）匹配節(jié)點(diǎn)。節(jié)點(diǎn)中分別保存著各個(gè)類(lèi)別，主要進(jìn)行事件的匹配和訂閱的增刪操作。功能如下：

① 對(duì)于事件，會(huì)根據(jù)其所從屬的訂閱類(lèi)別，尋找符合匹配條件的訂閱。

② 對(duì)于訂閱的增刪操作，根據(jù)其所從屬的訂閱類(lèi)別，進(jìn)行類(lèi)別的更新。

③ 類(lèi)別的更新，按照聚類(lèi)節(jié)點(diǎn)對(duì)類(lèi)別的更新信息，相應(yīng)地更新本節(jié)點(diǎn)內(nèi)的類(lèi)別。

將算法應(yīng)用到分布式系統(tǒng)上需要注意數(shù)據(jù)傳輸問(wèn)題。此外，在分布式系統(tǒng)中還應(yīng)注意負(fù)載均衡的問(wèn)題，以避免某一個(gè)節(jié)點(diǎn)負(fù)載過(guò)重，成為性能瓶頸。

3.1 類(lèi)別融合

分布式環(huán)境下，需要在滿足聚類(lèi)要求的情況下，盡量減少節(jié)點(diǎn)間的數(shù)據(jù)傳輸，同時(shí)根據(jù)相關(guān)性，本文將優(yōu)先進(jìn)行同一節(jié)點(diǎn)內(nèi)的類(lèi)別融合。過(guò)程中擬用到2個(gè)變量：CS（correlation in the same worker）和CD（correlation in the different worker）。

研究中可得，c.cs表示類(lèi)別c和其同一匹配節(jié)點(diǎn)中的類(lèi)別的相關(guān)性之和，相應(yīng)數(shù)學(xué)公式可寫(xiě)為：

其中，w表示類(lèi)別c所處的匹配節(jié)點(diǎn)。

進(jìn)一步得到，c.cd表示類(lèi)別c和其不同匹配節(jié)點(diǎn)中的類(lèi)別的相關(guān)性之和，相應(yīng)數(shù)學(xué)公式可寫(xiě)為：

在此基礎(chǔ)上，本文采用c.MergeJudgePara作為類(lèi)別c的判斷標(biāo)準(zhǔn)，選擇該值最大的類(lèi)別c進(jìn)行同一匹配節(jié)點(diǎn)之內(nèi)的相關(guān)性值最大的類(lèi)別進(jìn)行融合操作。相應(yīng)數(shù)學(xué)公式可寫(xiě)為：

如果一個(gè)類(lèi)別和其同一匹配節(jié)點(diǎn)中的類(lèi)別相關(guān)性很差，而和不同匹配節(jié)點(diǎn)間的相關(guān)性很好，即MergeJudgePara很小，在這種情況下，本文提出一個(gè)匹配節(jié)點(diǎn)間的類(lèi)別融合策略。首先新增一個(gè)閾值merge，該閾值用于判斷僅僅使用節(jié)點(diǎn)內(nèi)融合是否合理，如果計(jì)算得到的最大的MergeJudgePara

3.2 負(fù)載均衡

負(fù)載均衡的主要目的是為了均衡各個(gè)節(jié)點(diǎn)的負(fù)載，避免出現(xiàn)某一節(jié)點(diǎn)負(fù)載過(guò)重，成為性能瓶頸。若經(jīng)過(guò)一定數(shù)量的事件和訂閱（本文使用經(jīng)過(guò)λ數(shù)量的事件）后，就要判斷節(jié)點(diǎn)的負(fù)載是否失衡，一旦發(fā)生失衡，將盡快修復(fù)。

為了判斷是否存在負(fù)載不均衡的情況，先要對(duì)工作負(fù)載進(jìn)行量化。經(jīng)過(guò)分析可知，類(lèi)別c需要處理的數(shù)據(jù)包括3種，分別是：事件t、新添加的訂閱q、需要?jiǎng)h除的訂閱q'，故而其工作負(fù)載也包含3部分，具體如下：

其中，t.num表示接收到的事件數(shù)量; c.size表示類(lèi)別c的大小，使用類(lèi)別中訂閱的數(shù)量表示。

在公式（7）中，第一部分表示處理事件t的匹配操作的工作負(fù)載，其中c.size會(huì)隨著訂閱的增刪而變化;第二部分表示在這一段時(shí)間內(nèi)增加訂閱所需的資源消耗;第三部分表示這一段時(shí)間內(nèi)刪除訂閱所需的資源消耗。工作節(jié)點(diǎn)的總工作負(fù)載就是一段時(shí)間內(nèi)節(jié)點(diǎn)內(nèi)所有類(lèi)別的工作負(fù)載之和。本文使用匹配操作的工作負(fù)載表示類(lèi)別的工作負(fù)載。

本文采取的負(fù)載均衡策略可描述為：當(dāng)某一個(gè)節(jié)點(diǎn)負(fù)載過(guò)大，直接將其中的一部分遷移到另一個(gè)節(jié)點(diǎn)中。研究中，將所有節(jié)點(diǎn)的工作負(fù)載之和設(shè)為T(mén)otalLoad，假設(shè)共有m個(gè)工作節(jié)點(diǎn)，如果一個(gè)節(jié)點(diǎn)w的工作負(fù)載滿足公式（8）：

則認(rèn)為該節(jié)點(diǎn)的工作負(fù)載過(guò)大，需要進(jìn)行均衡。在負(fù)載均衡過(guò)程中，就要從負(fù)載最大的節(jié)點(diǎn)中選擇一部分訂閱轉(zhuǎn)移到其他的節(jié)點(diǎn)，在選擇這一部分訂閱時(shí)，本文判斷轉(zhuǎn)移操作是否應(yīng)該停止的標(biāo)準(zhǔn)參見(jiàn)公式（8）。

文中采用貪心策略來(lái)計(jì)算需要遷移的子集，使用DiviPara作為選擇標(biāo)準(zhǔn)，對(duì)其進(jìn)行運(yùn)算時(shí)需用到公式為：

選擇DiviPara值最大的類(lèi)別作為需要遷移的子集，直至滿足負(fù)載的均衡的要求。使用公式（9），對(duì)節(jié)點(diǎn)內(nèi)類(lèi)別進(jìn)行排序，轉(zhuǎn)移類(lèi)別至待接收的節(jié)點(diǎn)，直至達(dá)到負(fù)載均衡的要求。對(duì)于待接收節(jié)點(diǎn)，可以選擇和待遷移類(lèi)別相關(guān)性最大的節(jié)點(diǎn)。

4 實(shí)驗(yàn)

本節(jié)將給出基礎(chǔ)的發(fā)布訂閱算法的實(shí)驗(yàn)驗(yàn)證結(jié)果。實(shí)驗(yàn)時(shí)使用3臺(tái)計(jì)算機(jī)來(lái)搭建分布式環(huán)境，3臺(tái)計(jì)算機(jī)的參數(shù)配置為：1臺(tái)內(nèi)存為8GB，處理器為Intel（R） Core（TM） i5-8400 2.8GHz，2臺(tái)Inter（R） Celeron（R） CPU 1007U 1.5GHz，4GB內(nèi)存。每個(gè)處理器為單核CPU。該分布式環(huán)境由研究者自行設(shè)計(jì)，計(jì)算機(jī)系統(tǒng)使用Ubuntu18.04，分布式系統(tǒng)使用zookeeper和storm組件進(jìn)行搭建，涉及到的聚類(lèi)節(jié)點(diǎn)僅選擇2個(gè)，匹配節(jié)點(diǎn)為4個(gè)。

實(shí)驗(yàn)數(shù)據(jù)采取的是網(wǎng)站http：//www.pocketgpsworld.com/上的數(shù)據(jù)，選擇了網(wǎng)站中大約10萬(wàn)條數(shù)據(jù)。這些數(shù)據(jù)僅僅可用作發(fā)布的事件信息，本文使用事件信息生成相應(yīng)的訂閱信息，方法如下：首先規(guī)定訂閱的數(shù)量，本文選擇為事件數(shù)量的0.01倍;緊接著隨機(jī)生成該數(shù)量的訂閱，方式為每一個(gè)訂閱隨機(jī)選擇一個(gè)事件，訂閱的屬性集合取該事件的隨機(jī)屬性子集，訂閱的空間位置選擇以該事件為中心，經(jīng)緯度隨機(jī)擴(kuò)大的一定數(shù)量為訂閱的空間位置。這樣做就是希望訂閱和事件的匹配結(jié)果數(shù)盡量多。方便更新相關(guān)性。

本文對(duì)實(shí)驗(yàn)過(guò)程中的參數(shù)定義如下：公式（3）中，平衡屬性相似性和空間相似性的參數(shù)α=0.5。節(jié)點(diǎn)內(nèi)類(lèi)別融合和節(jié)點(diǎn)間的類(lèi)別融合的判斷閾值merge=1，聚類(lèi)節(jié)點(diǎn)中網(wǎng)格的間隔設(shè)置為5，匹配節(jié)點(diǎn)中網(wǎng)格的間隔設(shè)置為2，新類(lèi)別生成的閾值NewTh=0.5，類(lèi)別負(fù)載均衡的次數(shù)為2，由事件平均分配，即如果總共10萬(wàn)條事件，每進(jìn)行5萬(wàn)條則轉(zhuǎn)入負(fù)載均衡判斷。

首先，驗(yàn)證相似性和相關(guān)性是否能夠優(yōu)化聚類(lèi)操作，從而提升事件和訂閱的匹配速度。提供3種算法來(lái)進(jìn)行對(duì)比，分別為：

（1）僅僅使用不包含頻數(shù)的相似性來(lái)進(jìn)行聚類(lèi)操作，使用Sim-NonFre來(lái)表示。

（2）使用包含頻數(shù)的相似性來(lái)進(jìn)行聚類(lèi)操作，使用Sim-Fre表示。

（3）同時(shí)使用包含頻數(shù)的相似性和相關(guān)性來(lái)進(jìn)行聚類(lèi)操作，使用Sim-Fre-Co來(lái)表示。

針對(duì)這三種算法，測(cè)量的數(shù)據(jù)為事件經(jīng)過(guò)空間篩選和屬性篩選后，被分配的類(lèi)別平均數(shù)量。測(cè)量的時(shí)機(jī)分別為：

（1）事件流和訂閱流同時(shí)存在的過(guò)程，該過(guò)程從0開(kāi)始，即從接收到的第一個(gè)事件和訂閱開(kāi)始，同時(shí)進(jìn)行數(shù)據(jù)的訓(xùn)練和匹配操作，結(jié)果如圖4所示。

（2）僅僅存在事件流的過(guò)程，此時(shí)訂閱聚類(lèi)過(guò)程已經(jīng)結(jié)束，數(shù)據(jù)訓(xùn)練完成，僅僅存在匹配過(guò)程，結(jié)果如圖4所示。

在圖4中，訓(xùn)練過(guò)程表示事件流和訂閱流同時(shí)存在，訓(xùn)練結(jié)束表示訓(xùn)練完成，僅僅進(jìn)行事件流的研究。事件需要進(jìn)行匹配的平均類(lèi)別數(shù)量使用Sim-NonFre結(jié)果最多，Sim-Fre結(jié)果居中，Sim-Fre-Co結(jié)果最少，即使用帶頻率的相似性和相關(guān)性相比較于普通的相似性有效地減少了事件需要進(jìn)行匹配操作的類(lèi)別數(shù)量。對(duì)比訓(xùn)練過(guò)程和訓(xùn)練結(jié)束，訓(xùn)練完成后單純進(jìn)行匹配操作時(shí)，事件被分配的類(lèi)別增加，因?yàn)橥瑫r(shí)進(jìn)行訓(xùn)練和匹配操作，有一些事件發(fā)布后，尚未對(duì)其給予訂閱關(guān)注，隨后才有訂閱關(guān)注該事件，使得事件需要進(jìn)行更多的匹配操作。

隨后，驗(yàn)證類(lèi)別融合策略的數(shù)據(jù)傳輸量。本文將提供訓(xùn)練過(guò)程中DataTra的結(jié)果，分別給出僅僅使用節(jié)點(diǎn)內(nèi)的類(lèi)別融合（使用InNode表示）和同時(shí)使用節(jié)點(diǎn)內(nèi)類(lèi)別融合和節(jié)點(diǎn)間的類(lèi)別融合的數(shù)據(jù)傳輸量（InAndBetNode表示）。實(shí)驗(yàn)結(jié)果如圖5所示。同時(shí)使用節(jié)點(diǎn)內(nèi)融合和節(jié)點(diǎn)間融合的數(shù)據(jù)傳輸量InAndBetNode從訓(xùn)練初期就處于上升階段，但是此后類(lèi)別將逐漸下降。僅僅使用節(jié)點(diǎn)內(nèi)類(lèi)別融合的數(shù)據(jù)量InNode，由于僅僅使用節(jié)點(diǎn)內(nèi)數(shù)據(jù)融合，類(lèi)別的分布不合理，使得類(lèi)別融合操作次數(shù)一直居高不下。

接下來(lái)，將驗(yàn)證類(lèi)別融合策略的效果。本節(jié)擬給出2種算法進(jìn)行對(duì)比，分別是：本文的DRt-Cluster算法，Chen等人[13]的發(fā)布訂閱算法，Chen等人[13]的研究使用kd-tree作為聚類(lèi)算法，所以本文使用kd-tree表示該算法。本文將提供事件的吞吐量進(jìn)行對(duì)比，對(duì)比結(jié)果如圖6所示。經(jīng)過(guò)事件和訂閱的訓(xùn)練之后，單單進(jìn)行事件的匹配過(guò)程和訂閱的增刪過(guò)程來(lái)驗(yàn)證類(lèi)別的聚類(lèi)結(jié)果和在匹配節(jié)點(diǎn)上的分布結(jié)果，使用tran/sec表示。由圖6可知，本文的DRt-Cluster算法的吞吐量略高于kd-tree算法。

最后，本文研究了DRt-Cluster算法負(fù)載均衡操作前后，數(shù)據(jù)的吞吐量變化，實(shí)驗(yàn)結(jié)果如圖7所示。經(jīng)過(guò)負(fù)載均衡操作后，類(lèi)別的分布更加均勻，數(shù)據(jù)的吞吐量獲得一定的提升。

5 結(jié)束語(yǔ)

本文首先詳細(xì)介紹了發(fā)布訂閱系統(tǒng)，采取混合屬性的應(yīng)用方法，提出了相似性和相關(guān)性這2種聚類(lèi)算法中的判斷參數(shù)，設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)單處理器上的即時(shí)發(fā)布訂閱算法，隨后設(shè)計(jì)一個(gè)分布式的系統(tǒng)，并且將即時(shí)的發(fā)布訂閱算法部署其上提出了與其相適應(yīng)的負(fù)載均衡策略，最后通過(guò)實(shí)驗(yàn)驗(yàn)證其效果。

參考文獻(xiàn)

[1]LI G， WANG Y， WANG T， et al. Location-aware publish/subscribe[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Chicago：ACM SIGMOD Record， 2013：802-810.

[2]HU Huiqi， LIU Yiqun， LI Guoliang， et al. A location-aware publish/subscribe framework for parameterized spatio-textual subscriptions[C]// IEEE 31st International Conference on Data Engineering. Seoul， South Korea：IEEE， 2015：711-722.

[3]WANG Xiang， ZHANG Ying， ZHANG Wenjie， et al. AP-Tree： Efficiently support continuous spatial-keyword queries over stream[C]// ICDE Workshops 2015. Seoul， South Korea：IEEE，2015， 6（1）：1107-1118.

[4]CHEN L， CONG G， CAO X. An efficient query indexing mechanism for filtering geo-textual data[C]// ACM SIGMOD International Conference on Management of Data. New York：ACM， 2013：749-760.

[5]WANG X， ZHANG Y， ZHANG W， et al. Skype： Top-k spatial-keyword publish/subscribe over sliding window[J]. Vldb Journal， 2017， 26（3）：301-326.

[6]YU Minghe， LI Guoliang， FENG Jianhua. A cost-based method for location-aware publish/subscribe services[C]//Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. New York：ACM，2015：693-702.

[7]CHEN Lisi， CONG Gao， CAO Xin， et al. Temporal Spatial-Keyword Top-k publish/subscribe[C]// IEEE 31st International Conference on Data Engineering.Seoul， South Korea：IEEE， 2015：255-266.

[8]AJI A， WANG Fusheng， VO H， et al. Hadoop-GIS： A high performance spatial data warehousing system over mapreduce[J]. Proceedings of the VLDB Endowment， 2013，6（11）：1009-1020.

[9]ELDAWY A， MOKBEL M F. SpatialHadoop： A MapReduce framework for spatial data[C]// IEEE 32nd International Conference on Data Engineering. Helsinki， Finland： IEEE， 2016：1352-1363.

[10]AKDOGAN A， DEMIRYUREK U， BANAEI-KASHANI F， et al. Voronoi-based geospatial query processing with MapReduce[C]// 2010 IEEE Second International Conference on Cloud Computing Technology and Science. NW Washington，DC： IEEE Computer Society， 2010：9-16.

[11] NISHIMURA S， DAS S， AGRAWAL D， et al. Md-HBase： A scalable multi-dimensional data infrastructure for location aware services[C]// 2011 12th IEEE International Conference on MDM. Lulea， Sweden：IEEE， 2011，1： 7-16.

[12]ALY A M， MAHMOOD A R， HASSAN M S， et al. AQWA： Adaptive query-workload-aware partitioning of big spatial data[J]// Proceedings of the VLDB Endowment，2015，8（13）：2062-2073.

[13]CHEN Zhida， CONG Gao， ZHANG Zhenjie， et al. Distributed publish/subscribe query processing on the spatio-textual data stream[C]// IEEE International Conference on Data Engineering.San Diego， CA， USA：IEEE， 2017： 1095-1106.