[發(fā)明專利]面向時(shí)空感知發(fā)布/訂閱系統(tǒng)的高效匹配方法及系統(tǒng)

在審

• 申請(qǐng)?zhí)枺?/td>: 202010813627.4
• 申請(qǐng)日: 2020-08-12
• 公開（公告）號(hào): CN111949913A
• 公開（公告）日: 2020-11-17
• 發(fā)明（設(shè)計(jì)）人: 錢詩友;丁天琛;曹健;薛廣濤
• 申請(qǐng)（專利權(quán)）人: 上海交通大學(xué)
• 主分類號(hào): G06F16/958
• 分類號(hào): G06F16/958;G06F16/9537;G06F16/901
• 代理公司: 上海漢聲知識(shí)產(chǎn)權(quán)代理有限公司 31236
• 代理人: 胡晶

本發(fā)明提供了一種面向時(shí)空感知發(fā)布/訂閱系統(tǒng)的匹配方法及系統(tǒng)，包括：步驟M1：選擇符合預(yù)設(shè)條件的且分布均勻的屬性作為索引屬性，對(duì)索引屬性的值域進(jìn)行混合劃分，實(shí)現(xiàn)訂閱中區(qū)域謂詞和事件屬性值到劃分單元的映射；步驟M2：通過級(jí)聯(lián)多個(gè)進(jìn)行混合劃分的索引屬性構(gòu)造MO?Tree，實(shí)現(xiàn)訂閱和事件到MO?Tree中葉子節(jié)點(diǎn)的映射；步驟M3：根據(jù)索引屬性值，基于MO?Tree實(shí)現(xiàn)訂閱匹配和事件匹配；本發(fā)明解決方案完整性：事件和訂閱都可以在MO?Tree中進(jìn)行索引。

技術(shù)領(lǐng)域

本發(fā)明涉及時(shí)空感知數(shù)據(jù)分發(fā)網(wǎng)絡(luò)中的匹配方法，具體地，涉及一種面向時(shí)空感知發(fā)布/訂閱系統(tǒng)的高效匹配方法及系統(tǒng)，更為具體地，涉及一種新穎的數(shù)據(jù)結(jié)構(gòu)以實(shí)現(xiàn)高效的事件匹配、訂閱匹配、事件與訂閱維護(hù)操作。

背景技術(shù)

隨著通信技術(shù)的發(fā)展以及諸如智能電話之類的移動(dòng)設(shè)備的普及，許多應(yīng)用以前所未有的規(guī)模不斷生成大量具有位置標(biāo)記和對(duì)時(shí)間敏感的數(shù)據(jù)，這些應(yīng)用促使了時(shí)空感知數(shù)據(jù)實(shí)時(shí)分發(fā)的需求。

以移動(dòng)電子商務(wù)場(chǎng)景為例，商家會(huì)以事件的形式定期發(fā)布對(duì)時(shí)間敏感的線下促銷活動(dòng)，這些事件信息中包含商家位置，以及促銷活動(dòng)的截止日期。這些活動(dòng)不是一次性的，而是會(huì)持續(xù)一段時(shí)間，這意味著它們可能會(huì)滿足后加入客戶的要求。另一方面，持有移動(dòng)設(shè)備的客戶希望收到那些在其附近并且滿足其指定的偏好要求的促銷活動(dòng)，他們的偏好要求中包含了用戶對(duì)商品的偏好、當(dāng)前位置以及感興趣的附近范圍大小。由于用戶在不斷移動(dòng)，因此，即使他們訂閱了一次，需要根據(jù)他們不斷變化的位置更新其訂閱。

移動(dòng)電子商務(wù)的應(yīng)用場(chǎng)景展現(xiàn)了時(shí)空感知數(shù)據(jù)分發(fā)的三個(gè)特征，即細(xì)粒度的表達(dá)能力，時(shí)間敏感性和位置感知。首先，產(chǎn)品或服務(wù)的促銷事件通常包含多個(gè)屬性，客戶可以非常精確地表達(dá)他們感興趣的銷售產(chǎn)品類型。其次，每個(gè)促銷事件都具有有效期，過期促銷將終止。第三，每個(gè)客戶提交的訂閱都指定一個(gè)隨用戶移動(dòng)的空間通知區(qū)域。

為了實(shí)現(xiàn)時(shí)空感知的數(shù)據(jù)分發(fā)，四種操作至關(guān)重要，即訂閱維護(hù)，事件維護(hù)，訂閱匹配和事件匹配。1)訂閱維護(hù)：應(yīng)有效維護(hù)客戶提交的所有訂閱信息，以提高事件匹配性能，這涉及訂閱的插入，刪除和更新。2)事件維護(hù)：類似地，應(yīng)有效維護(hù)所有未過期的歷史促銷事件以提高訂閱匹配性能，這涉及事件插入和刪除。3)訂閱匹配：當(dāng)客戶提交一個(gè)新訂閱時(shí)，應(yīng)將其與維護(hù)的未過期歷史促銷事件集進(jìn)行匹配，以便向客戶發(fā)送滿足其偏好要求的促銷事件。4)事件匹配：每當(dāng)發(fā)布一個(gè)事件時(shí)，應(yīng)將其與維護(hù)的訂閱集進(jìn)行匹配，以便將促銷事件發(fā)送給感興趣的客戶。

當(dāng)面對(duì)大量的訂閱和海量的促銷事件時(shí)，例如，阿里巴巴推出的喵街App為數(shù)百萬消費(fèi)者提供了巨大的折扣信息，到2020年2月總下載量達(dá)到5200萬。保證時(shí)空感知促銷事件的快速傳播非常具有挑戰(zhàn)性。現(xiàn)有的具有位置感知能力的發(fā)布/訂閱系統(tǒng)都無法提供高性能的整體解決方案，無法支持事件和訂閱的高效匹配和維護(hù)操作。

本發(fā)明提出了一種新穎的數(shù)據(jù)結(jié)構(gòu)MO-Tree，以統(tǒng)一的方式對(duì)事件和訂閱進(jìn)行索引，從而在匹配和維護(hù)操作中均實(shí)現(xiàn)了較高的性能。因此，MO-Tree可作為為時(shí)空感知基于內(nèi)容的發(fā)布/訂閱系統(tǒng)的轉(zhuǎn)發(fā)引擎。MO-Tree是一種樹狀數(shù)據(jù)結(jié)構(gòu)，其中，訂閱和事件存儲(chǔ)在葉節(jié)點(diǎn)中，并且采用基于剪枝的搜索策略來支持事件匹配和訂閱匹配。

MO-Tree的設(shè)計(jì)理念是使數(shù)據(jù)結(jié)構(gòu)盡量保持簡(jiǎn)潔，以便在匹配和維護(hù)操作中達(dá)到較高的整體性能，這體現(xiàn)在三個(gè)方面。首先，通過限制樹的高度并擴(kuò)大節(jié)點(diǎn)的扇出，使MO-Tree的形狀變平。其次，通過利用時(shí)間交換空間的策略來限制每個(gè)葉節(jié)點(diǎn)中存儲(chǔ)的訂閱或事件個(gè)數(shù)，以提高匹配操作效率。第三，避免節(jié)點(diǎn)拆分和合并，以提高維護(hù)操作效率，這與傳統(tǒng)樹結(jié)構(gòu)不同。

設(shè)計(jì)MO-Tree的一個(gè)困難是索引由不同寬度的區(qū)間謂詞組成的訂閱。本專利提出了一種混合分區(qū)方案，將屬性的值域劃分為多級(jí)重疊單元，以處理各種區(qū)間寬度。此外，建立了一個(gè)優(yōu)化模型來計(jì)算每個(gè)級(jí)別中重疊單元的寬度。