[發(fā)明專利]基于時(shí)間滑動(dòng)窗口的數(shù)據(jù)流點(diǎn)連接查詢方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310219213.9
• 申請(qǐng)日: 2013-06-04
• 公開（公告）號(hào): CN103309966A
• 公開（公告）日: 2013-09-18
• 發(fā)明（設(shè)計(jì)）人: 王坤朋;王偉平;木偉民;孟丹
• 申請(qǐng)（專利權(quán)）人: 中國(guó)科學(xué)院信息工程研究所
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 北京輕創(chuàng)知識(shí)產(chǎn)權(quán)代理有限公司 11212
• 代理人: 楊立

1.基于時(shí)間滑動(dòng)窗口的數(shù)據(jù)流點(diǎn)連接查詢方法，其特征在于，包括如下步驟：

步驟1：為數(shù)據(jù)流A和數(shù)據(jù)流B分別建立基于時(shí)間的滑動(dòng)窗口，分別為時(shí)間滑動(dòng)窗口A和時(shí)間滑動(dòng)窗口B，進(jìn)入步驟2；

步驟2：為數(shù)據(jù)流A和數(shù)據(jù)流B分別設(shè)定更新周期為ta和tb；

步驟3：處理數(shù)據(jù)流A則依次執(zhí)行步驟4至步驟8，處理數(shù)據(jù)流B則依次執(zhí)行步驟9至步驟13；所述步驟4至步驟8與步驟9至步驟13并行執(zhí)行；

步驟4：數(shù)據(jù)流A的更新周期到來時(shí)創(chuàng)建一個(gè)緩沖區(qū)A（n-1）（n=2、3、4……），接收該更新周期內(nèi)到來的數(shù)據(jù)流A的元組，并初始化元組的狀態(tài)為有效，該緩沖區(qū)中所有元組具有相同的時(shí)間戳，時(shí)間戳為該緩沖區(qū)創(chuàng)建的時(shí)刻；

步驟5：數(shù)據(jù)流A的更新周期再次到來時(shí)，緩沖區(qū)A（n-1）（n=2、3、4……）不再接收元組，而是開辟新的緩沖區(qū)A（n）(n=2、3、4……)來接收后續(xù)到來的元組，同時(shí)對(duì)緩沖區(qū)A（n-1）中的元組進(jìn)行處理；

步驟6：緩沖區(qū)A（n-1）中所有的元組依次對(duì)時(shí)間滑動(dòng)窗口B進(jìn)行探測(cè)，查找與緩沖區(qū)A（n-1）中元組連接屬性值相同的元組；如果找到連接屬性值相同的元組則進(jìn)行連接并表明緩沖區(qū)A（n-1）中該元組連接成功，如果未找到表明連接失敗；

步驟7：查看緩沖區(qū)A（n-1）中所有元組連接情況，將連接成功的元組批量刪除，將連接失敗的元組批量插入到時(shí)間滑動(dòng)窗口A中；

步驟8：檢查在時(shí)間滑動(dòng)窗A口中停留時(shí)間超過預(yù)定時(shí)間TA且時(shí)間戳最小的一批元組并清理，檢測(cè)是否有數(shù)據(jù)流A的元組到來，如果有則返回步驟5，否則待緩沖區(qū)A(n)中和時(shí)間滑動(dòng)窗口A中的元組都處理完后結(jié)束；

步驟9：數(shù)據(jù)流B的更新周期開始時(shí)創(chuàng)建一個(gè)緩沖區(qū)B(n-1)（n=2、3、4……），接收該更新周期內(nèi)到來的數(shù)據(jù)流B的元組，并初始化元組的狀態(tài)為有效，該緩沖區(qū)中所有元組具有相同的時(shí)間戳，該時(shí)間戳為緩沖區(qū)創(chuàng)建的時(shí)刻；

步驟10：數(shù)據(jù)流B的更新周期再次到來時(shí)，緩沖區(qū)B（n-1）（n=2、3、4……）不再接收元組，而是開辟新的緩沖區(qū)B（n）（n=2、3、4……）來接收后續(xù)到來的元組，同時(shí)對(duì)緩沖區(qū)B（n-1）中的元組進(jìn)行處理；

步驟11：緩沖區(qū)B（n-1）中的所有元組順次對(duì)時(shí)間滑動(dòng)窗口A進(jìn)行探測(cè)，查找與緩沖區(qū)中B（n-1）元組連接屬性值相同的元組；如果找到連接屬性值相同的元組則進(jìn)行連接且表明緩沖區(qū)B（n-1）中該元組連接成功，如果未找到表明連接失敗；

步驟12：查看緩沖區(qū)B（n-1）中所有元組的連接情況；將連接成功的元組批量刪除，將連接失敗的元組批量插入到時(shí)間滑動(dòng)窗口B中；

步驟13：檢查在時(shí)間滑動(dòng)窗口B中停留時(shí)間超過預(yù)定時(shí)間TB且時(shí)間戳最小的一批元組并清理,檢測(cè)是否有數(shù)據(jù)流B的元組到來，如果有則返回步驟10，否則待緩沖區(qū)B(n)中和時(shí)間滑動(dòng)窗口B中的元組都處理完后結(jié)束。

2.根據(jù)權(quán)利要求1所述基于時(shí)間滑動(dòng)窗口的數(shù)據(jù)流點(diǎn)連接查詢方法，其特征在于，步驟6中所述緩沖區(qū)A（n-1）中所有的元組依次對(duì)時(shí)間滑動(dòng)窗口B進(jìn)行探測(cè)的具體步驟如下：

步驟6.1：對(duì)時(shí)間滑動(dòng)窗口B加鎖；

步驟6.2：遍歷緩沖區(qū)A（n-1）中的每個(gè)元組，每個(gè)元組對(duì)時(shí)間滑動(dòng)窗口B進(jìn)行探測(cè)，如果在時(shí)間滑動(dòng)窗口B中找到與該元組匹配的且狀態(tài)為有效的元組，則輸出連接結(jié)果，并將緩沖區(qū)A（n-1）中的該元組與時(shí)間滑動(dòng)窗口B中匹配的元組狀態(tài)均標(biāo)記為無效；如果在時(shí)間滑動(dòng)窗口B中未找到與該元組匹配的且狀態(tài)為有效的元組，則緩沖區(qū)A（n-1）中的該元組狀態(tài)保持為有效；

步驟6.3:釋放時(shí)間滑動(dòng)窗口B的鎖。

3.根據(jù)權(quán)利要求1所述基于時(shí)間滑動(dòng)窗口的數(shù)據(jù)流點(diǎn)連接查詢方法，其特征在于，步驟7中查看緩沖區(qū)A（n-1）中所有元組連接情況，將連接成功的元組批量刪除，將連接失敗的元組批量插入到時(shí)間滑動(dòng)窗口A中的具體步驟如下：

步驟7.1：對(duì)時(shí)間滑動(dòng)窗口A加鎖；

步驟7.2：遍歷緩沖區(qū)A(n-1)中每個(gè)元組，將狀態(tài)為有效的元組插入到時(shí)間滑動(dòng)窗口A中，將狀態(tài)為無效的元組直接刪除；

步驟7.3：釋放時(shí)間滑動(dòng)窗口A的鎖。