[發(fā)明專利]數(shù)據(jù)流θ連接優(yōu)化方法、系統(tǒng)、終端以及存儲(chǔ)介質(zhì)

有效

• 申請(qǐng)?zhí)枺?/td>: 202110331197.7
• 申請(qǐng)日: 2021-03-26
• 公開（公告）號(hào): CN112948442B
• 公開（公告）日: 2022-06-21
• 發(fā)明（設(shè)計(jì)）人: 王洋;吳嘉澍;須成忠
• 申請(qǐng)（專利權(quán)）人: 深圳先進(jìn)技術(shù)研究院
• 主分類號(hào): G06F16/2455
• 分類號(hào): G06F16/2455;G06F16/2453;G06F16/27
• 代理公司: 深圳市科進(jìn)知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 44316
• 代理人: 魏毅宏

本發(fā)明涉及一種數(shù)據(jù)流θ連接優(yōu)化方法，包括：根據(jù)θ條件對(duì)兩個(gè)數(shù)據(jù)流進(jìn)行第一次預(yù)過濾；對(duì)第一次預(yù)過濾后的兩個(gè)數(shù)據(jù)流根據(jù)分區(qū)數(shù)及最大最小值分別計(jì)算分區(qū)標(biāo)記，并將兩個(gè)數(shù)據(jù)流的分區(qū)標(biāo)記進(jìn)行聯(lián)合，得到聯(lián)合分區(qū)標(biāo)記，根據(jù)聯(lián)合分區(qū)標(biāo)記進(jìn)行聯(lián)合分區(qū)；根據(jù)θ條件對(duì)聯(lián)合分區(qū)后的兩個(gè)數(shù)據(jù)流進(jìn)行第二次預(yù)過濾；分別計(jì)算第二次預(yù)過濾后數(shù)據(jù)流的平均分區(qū)尺寸，對(duì)于分區(qū)尺寸大于平均分區(qū)尺寸的分區(qū)進(jìn)行重分區(qū)；對(duì)重分區(qū)后的兩數(shù)據(jù)流進(jìn)行笛卡爾積操作，得到數(shù)據(jù)流θ連接的結(jié)果。本發(fā)明還涉及一種數(shù)據(jù)流θ連接優(yōu)化系統(tǒng)。本發(fā)明利用二次預(yù)過濾與聯(lián)合分區(qū)，對(duì)theta?join算法進(jìn)行優(yōu)化，盡可能地減少不必要的笛卡爾積數(shù)量，從而大幅提高了運(yùn)行效率。

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

本發(fā)明涉及一種數(shù)據(jù)流θ連接優(yōu)化方法、系統(tǒng)、終端以及存儲(chǔ)介質(zhì)。

背景技術(shù)

隨著數(shù)字時(shí)代的迅猛發(fā)展，數(shù)據(jù)也隨之大量產(chǎn)生。為了更加高效地對(duì)產(chǎn)生的數(shù)據(jù)加以處理、利用，高效的數(shù)據(jù)處理算法變得愈發(fā)重要。在很多應(yīng)用中，數(shù)據(jù)都會(huì)以在線數(shù)據(jù)流的形式在線到來(lái)，如隨時(shí)間波動(dòng)的股票、匯率數(shù)據(jù)，隨時(shí)間變化的氣溫、風(fēng)速數(shù)據(jù)等等。

在對(duì)數(shù)據(jù)流數(shù)據(jù)進(jìn)行處理時(shí)，一種很重要的操作便是θ連接(Theta-Join)操作。Theta-join操作能夠通過所給定的θ條件，找出數(shù)據(jù)流中符合θ條件的數(shù)據(jù)組，方便其他后續(xù)的數(shù)據(jù)分析與利用。

為應(yīng)對(duì)現(xiàn)今大數(shù)據(jù)與信息化應(yīng)用對(duì)數(shù)據(jù)處理效率的要求，theta-join算法需要盡可能高效地對(duì)數(shù)據(jù)流進(jìn)行連接操作。但是，theta-join中所需用到的笛卡爾積(cross-product)操作十分耗時(shí)，成為了影響theta-join算法效率的最重要因素。

現(xiàn)有的theta-join算法在進(jìn)行θ連接時(shí)，都會(huì)進(jìn)行大量不必要的笛卡爾積操作，使得其算法運(yùn)行效率欠佳。因此，如何能夠盡可能地減少theta-join算法所進(jìn)行的不必要的笛卡爾積的數(shù)量，提高theta-join算法的運(yùn)行效率，成為了一個(gè)亟待優(yōu)化的問題。

發(fā)明內(nèi)容

有鑒于此，有必要提供一種數(shù)據(jù)流θ連接優(yōu)化方法、系統(tǒng)、終端以及存儲(chǔ)介質(zhì)，其能夠利用二次預(yù)過濾與聯(lián)合分區(qū)，對(duì)theta-join算法進(jìn)行優(yōu)化，盡可能地減少theta-join算法所進(jìn)行的不必要的笛卡爾積數(shù)量，從而大幅提高theta-join算法的運(yùn)行效率。

本申請(qǐng)實(shí)施例提供一種數(shù)據(jù)流θ連接優(yōu)化方法，該方法包括如下步驟：a.根據(jù)θ條件對(duì)兩個(gè)數(shù)據(jù)流進(jìn)行第一次預(yù)過濾；所述預(yù)過濾是指過濾掉不可能滿足θ條件的數(shù)據(jù)流的分區(qū)；b.對(duì)第一次預(yù)過濾后的兩個(gè)數(shù)據(jù)流根據(jù)分區(qū)數(shù)及最大最小值分別計(jì)算分區(qū)標(biāo)記，并將兩個(gè)數(shù)據(jù)流的分區(qū)標(biāo)記進(jìn)行聯(lián)合，得到聯(lián)合分區(qū)標(biāo)記，根據(jù)所述聯(lián)合分區(qū)標(biāo)記進(jìn)行聯(lián)合分區(qū)；c.根據(jù)θ條件對(duì)上述分區(qū)后的兩個(gè)數(shù)據(jù)流進(jìn)行第二次預(yù)過濾；d.分別計(jì)算第二次預(yù)過濾后數(shù)據(jù)流的平均分區(qū)尺寸，對(duì)于分區(qū)尺寸大于平均分區(qū)尺寸的分區(qū)進(jìn)行重分區(qū)；e.對(duì)重分區(qū)后的兩數(shù)據(jù)流進(jìn)行笛卡爾積操作，得到數(shù)據(jù)流θ連接的結(jié)果。

其中，所述的步驟b包括：

在計(jì)算完兩個(gè)數(shù)據(jù)流分別的分區(qū)標(biāo)記后，將兩個(gè)數(shù)據(jù)流計(jì)算得出的分區(qū)標(biāo)記進(jìn)行合并得到以聯(lián)合分區(qū)標(biāo)記，并利用所述聯(lián)合分區(qū)標(biāo)記分別對(duì)兩個(gè)數(shù)據(jù)流進(jìn)行更為細(xì)化的分區(qū)。

其中，所述的平均分區(qū)尺寸由下述公式計(jì)算得到：

其中，average_partition_size為該數(shù)據(jù)流的平均分區(qū)大小，number_of_elements_in_stream為該數(shù)據(jù)流處于當(dāng)前處理窗口中的數(shù)據(jù)量，number_of_partitions為該數(shù)據(jù)流由聯(lián)合分區(qū)產(chǎn)生的分區(qū)數(shù)。

其中，所述重分區(qū)的分區(qū)數(shù)由下述公式計(jì)算得到：