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

在審

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

1.一種面向時空感知發(fā)布/訂閱系統(tǒng)的匹配方法，其特征在于，包括：

步驟M1：選擇符合預(yù)設(shè)條件的且分布均勻的屬性作為索引屬性，對索引屬性的值域進行混合劃分，實現(xiàn)訂閱中區(qū)域謂詞和事件屬性值到劃分單元的映射；

步驟M2：通過級聯(lián)多個進行混合劃分的索引屬性構(gòu)造MO-Tree，實現(xiàn)訂閱和事件到MO-Tree中葉子節(jié)點的映射；

步驟M3：根據(jù)索引屬性值，基于MO-Tree實現(xiàn)訂閱匹配和事件匹配；

所述索引屬性的值域進行混合劃分包括將索引屬性的值域分別劃分為不相交的單元格和多級重疊的單元格。

2.根據(jù)權(quán)利要求1所述的面向時空感知發(fā)布/訂閱系統(tǒng)的匹配方法，其特征在于，所述步驟M1包括：

步驟M1.1：將屬性的值域均勻地劃分為一定數(shù)量的不相交單元格，實現(xiàn)事件屬性值與單元格的一對一映射；

步驟M1.2：在多級重疊式劃分方案中，將值域劃分為單元格數(shù)量逐級減少，單元格間的重疊寬度逐級增大的多級重疊式劃分，多級單元重疊結(jié)構(gòu)處理不同寬度的區(qū)間謂詞，實現(xiàn)區(qū)間謂詞與完全包含區(qū)間謂詞的最小單元格的一對一映射；

所述多級重疊劃分包括相同級別的相鄰兩個單元格的重疊劃分和不同級別的單元格的重疊劃分；多級重疊式劃分實現(xiàn)了從具有不同寬度和中心的區(qū)域謂詞到單元格的一對一映射。

3.根據(jù)權(quán)利要求2所述的面向時空感知發(fā)布/訂閱系統(tǒng)的匹配方法，其特征在于，所述步驟M1.2包括：

步驟M1.2.1：設(shè)置級別數(shù)量L，每一級中單元格的數(shù)量為c_i=L-i+1，則第i級中兩個相鄰單元格之間的重疊寬度其中，w_i表示每一級單元格的寬度；

步驟M1.2.2：當(dāng)區(qū)間謂詞的寬度遵循齊夫分布，將區(qū)間謂詞均勻地存儲在L級的單元格中，則第i級中存儲的區(qū)間謂詞的理想寬度t_i滿足

步驟M1.2.3：第i級中單元格寬度w_i的最大取值最小取值

步驟M1.2.4：設(shè)ρ_i表示在第i級中與屬性值相交的單元格數(shù)量，則：

其中，z表示屬性值變量，P_e(z)表示事件中屬性值的概率密度函數(shù)，k_i(z)表示第i級中包含屬性值z的單元格數(shù)量；當(dāng)P_e(z)符合均勻分布時，則ρ_i＝c_i*w_i；

步驟M1.2.5：設(shè)γ_i表示在第i級成功索引目標(biāo)范圍中區(qū)間謂詞的比例，r_i(x)表示在第i級索引寬度為x的成功率：

其中，P_l(y|x)表示區(qū)間謂詞的低值為y，寬度為x的區(qū)間謂詞的概率密度函數(shù)，b_i(y，x)表示區(qū)間謂詞的低值為y，寬度為x的區(qū)間謂詞是否存儲在第i級的某個單元格中；1表示存儲在第i級的單元格中，0表示沒有存儲在第i級的單元格中；

其中，j表示第i級中的單元格，j＝0，1，…，c_i-1；

當(dāng)P_l(y|x)符合均勻分布時，在第i級索引寬度x的成功率

其中，t_i表示第i級中存儲的區(qū)間謂詞的理想寬度，P_w(x)表示區(qū)間謂詞寬度的概率密度函數(shù)；γ_i表示第i級成功索引目標(biāo)范圍中區(qū)間謂詞的比例；

步驟M1.2.6：根據(jù)每個級別的區(qū)間謂詞的理想寬度t_i，優(yōu)化每一級中單元格寬度，滿足在事件匹配時與屬性值相交的單元格數(shù)量不超過給定閾值η，每一級單元格寬度的最大化公式如下：

其中，λ是拉格朗日乘子；

每一級i中單元格寬度的最優(yōu)解為：

其中，和分別表示求w_i和λ的偏導(dǎo)數(shù)。

4.根據(jù)權(quán)利要求1所述的面向時空感知發(fā)布/訂閱系統(tǒng)的匹配方法，其特征在于，所述多級重疊式劃分單元格包括覆蓋整個值域?qū)挾鹊膯卧瘢采w整個值域?qū)挾鹊膯卧裼糜诖鎯ψ畲髮挾鹊膮^(qū)間謂詞，并用于解決訂閱中不包含在索引屬性上定義的謂詞。