[發(fā)明專利]面向Storm連續(xù)范圍查詢?nèi)重撦d均衡的分組方法及查詢方法

有效

• 申請?zhí)枺?/td>: 201710536098.6
• 申請日: 2017-07-04
• 公開（公告）號: CN107357659B
• 公開（公告）日: 2020-09-29
• 發(fā)明（設(shè)計）人: 王波濤;王國仁;周建鵬;張玉圻;王助;鐘漢輝
• 申請（專利權(quán)）人: 東北大學(xué)
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F16/2453;G06F16/2455
• 代理公司: 北京君泊知識產(chǎn)權(quán)代理有限公司 11496
• 代理人: 王程遠

1.一種面向Storm連續(xù)范圍查詢?nèi)重撦d均衡的分組方法，其特征在于，包括：

1)、獲取范圍查詢信息，所述范圍查詢信息包括查詢范圍和網(wǎng)格重疊量；

2)、根據(jù)查詢范圍和網(wǎng)格重疊量，將范圍查詢分為多個子查詢，每個子查詢的查詢范圍只和一個網(wǎng)格重疊；

3)、讀取Redis中存儲的與子查詢查詢范圍重疊網(wǎng)格中移動對象的密度，并根據(jù)子查詢的查詢范圍以及網(wǎng)格中移動對象的密度，計算子查詢的代價；

4)、根據(jù)查詢代價，將子查詢映射到相應(yīng)的組，然后從輪詢計數(shù)器表中獲取該組計數(shù)器的值；

所述根據(jù)查詢代價，將子查詢映射到相應(yīng)的組的具體步驟為：

4.1、設(shè)定查詢代價閾值范圍，判斷查詢代價與查詢代價閾值范圍的大小，若查詢代價大于或小于查詢代價閾值范圍，則直接根據(jù)查詢代價和第一次分組粒度計算所在組；

4.2、對于其他的范圍子查詢，由于其數(shù)量過多，所以將其做更細粒度的分組，則根據(jù)查詢代價、第一次分組粒度和第二次分組粒度計算所在組；

5)、根據(jù)計數(shù)器的值對下游worker的數(shù)量取模，得到目標worker id，并將目標workerid下發(fā)到下游。

2.根據(jù)權(quán)利要求1所述的面向Storm連續(xù)范圍查詢?nèi)重撦d均衡的分組方法，其特征在于，所述步驟2)中根據(jù)查詢范圍和網(wǎng)格重疊量，將范圍查詢分為多個子查詢具體包括：

2.1、設(shè)定分組數(shù)量，根據(jù)分組數(shù)量計算第一次分組粒度；

2.2、設(shè)定二次分組數(shù)量，根據(jù)第一次分組粒度和二次分組數(shù)量計算二次分組的粒度，計算公式為：

minGrain＝grain/minGroup

其中，所述minGrain為二次分組粒度，grain為第一次分組粒度，minGroup為二次分組數(shù)量。

3.根據(jù)權(quán)利要求1所述的面向Storm連續(xù)范圍查詢?nèi)重撦d均衡的分組方法，其特征在于，所述子查詢的代價公式為：

C(q)＝r×d

其中，所述r為子查詢的查詢范圍大小，d為網(wǎng)格中移動對象的密度。

4.根據(jù)權(quán)利要求1所述的面向Storm連續(xù)范圍查詢?nèi)重撦d均衡的分組方法，其特征在于，所述輪詢計算器存儲在Redis中。

5.一種面向Storm連續(xù)范圍查詢?nèi)重撦d均衡的查詢方法，其特征在于，包括：

1)、獲取范圍查詢信息，所述范圍查詢信息包括查詢范圍和網(wǎng)格重疊量；將范圍查詢按照查詢范圍與網(wǎng)格重疊情況，劃分為相應(yīng)的子查詢，將所述子查詢按照全局分組輪詢的分組策略分發(fā)到下游目標worker；

2)、執(zhí)行范圍查詢的子查詢，并以范圍查詢的時間戳為key，按照Fields Grouping的分組策略分發(fā)到下游worker，確保屬于同一個范圍查詢的子查詢被分發(fā)到同一個worker；

3)、將屬于同一個范圍查詢的子查詢的查詢結(jié)果合并，得到最終的查詢結(jié)果，最后將最終的查詢結(jié)果以Shuffle Grouping的分組方式分發(fā)到下游Bolt；

4)、將范圍查詢結(jié)果發(fā)布到Kafka，由客戶端訂閱；

所述將所述子查詢按照全局分組輪詢的分組策略分發(fā)到下游目標worker具體包括：

1.1、獲取范圍查詢信息，所述范圍查詢信息包括查詢范圍和網(wǎng)格重疊量；

1.2、根據(jù)查詢范圍和網(wǎng)格重疊量，將范圍查詢分為多個子查詢，每個子查詢的查詢范圍只和一個網(wǎng)格重疊；

1.3、讀取Redis中存儲的與子查詢查詢范圍重疊網(wǎng)格中移動對象的密度，并根據(jù)子查詢的查詢范圍以及網(wǎng)格中移動對象的密度，計算子查詢的代價；

1.4、根據(jù)查詢代價，將子查詢映射到相應(yīng)的組，然后從輪詢計數(shù)器表中獲取該組計數(shù)器的值；

1.5、根據(jù)計數(shù)器的值對下游worker的數(shù)量取模，得到目標worker id，并將目標workerid下發(fā)到下游。