欢迎来到知嘟嘟! 联系电话:13095918853 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13095918853
知嘟嘟经纪人
收藏
专利号: 202110078248X
申请人: 中国地质大学(武汉)
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2024-01-05
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种分布式订阅发布模式下的空间范围‑关键字查询方法,其特征在于,包括:发布服务器接收地理文本流数据,其中,所述发布服务器上部署有每个订阅服务器的空间签名和文本签名组,其中,所述空间签名针对空间范围‑关键字查询的空间范围部分采用空间布谷鸟过滤器技术生成,所述文本签名组针对空间范围‑关键字查询的关键字集合部分采用单排序最小哈希算法和倒排文件四叉树方法生成;

所述发布服务器遍历每个所述空间签名和每个所述文本签名组,与所述地理文本流数据进行空间包含关系判断和文本相似性计算;

所述发布服务器基于所述空间包含关系判断和所述文本相似性计算结果,判断所述地理文本流数据是否命中至少一个所述订阅服务器;

若是,则由所述发布服务器把所述地理文本流数据转发到命中的订阅服务器上。

2.如权利要求1所述的分布式订阅发布模式下的空间范围‑关键字查询方法,其特征在于,在所述发布服务器接收地理文本流数据之前,还包括:把整个二维空间划分为多个等大小区域的集合ε,并对ε中的每个区域分配一个唯一的标记ID,一个区域的标记信息定义为r.ID,所述订阅服务器上的每个空间范围‑关键字查询的空间范围为ε的子集合,该子集合表示为△,子集合∆由至少一个区域组成;

在所述订阅服务器上初始化一个布谷鸟哈希表;

遍历空间范围‑关键字查询的每个区域,计算区域r.ID的指纹finger(r.ID),并基于第一预设公式计算所述区域r.ID在所述布谷鸟哈希表中对应的两个桶值,其中,所述第一预设公式包括:h1=hash(r.ID),h2=h1 hash(finger(r.ID)),其中, 是异或运算符号,h1与h2的计算结果为所述区域r.ID在所述布谷鸟哈希表中对应的两个桶值;

分别判断空间范围‑关键字查询中的所述区域r.ID在所述布谷鸟哈希表中对应的两个桶中是否有空闲位置,其中,所述两个桶表示为bucket[h1]和bucket[h2];

若是,则将空间范围‑关键字查询中的所述区域r.ID的指纹插入到所述空闲位置中;

若否,则使用空间范围‑关键字查询中的所述区域r.ID的指纹替换掉bucket[h1]或bucket[h2]的一个指纹;

得到最终的哈希表,所述最终的哈希表作为所述订阅服务器的所述空间签名。

3.如权利要求1所述的分布式订阅发布模式下的空间范围‑关键字查询方法,其特征在于,在所述发布服务器接收地理文本流数据之前,还包括:在所述订阅服务器上利用所述单排序最小哈希算法生成订阅关键字集合的签名,得到所述订阅服务器中四叉树所有叶子结点的关键字的签名,并把所述所有叶子结点的关键字的签名汇总到签名集合中;

当所有叶子节点所对应的文本签名组大于预设阈值时,把拥有同一个父节点的四个子节点的文本签名合并为一个新的文本签名,汇聚成新的签名集合,直到签名集合中签名的个数小于或等于所述预设阈值,并将此时的签名集合作为所述文本签名组。

4.如权利要求3所述的分布式订阅发布模式下的空间范围‑关键字查询方法,其特征在于,所述在所述订阅服务器上利用单排序最小哈希算法生成订阅关键字集合的签名包括:将所述订阅关键字集合进行哈希运算,得到由0和1组成的字符串;

将所述字符串进行分组,得到多个字符串组;

获取每个所述字符串组中第一个非零值所处的位置;

将每个所述字符串组中第一个非零值所处的位置所组成的集合作为所述订阅关键字集合的签名。

5.如权利要求2所述的分布式订阅发布模式下的空间范围‑关键字查询方法,其特征在于,所述发布服务器遍历每个所述空间签名和每个所述文本签名组,与所述地理文本流数据进行空间包含关系判断和文本相似性计算包括:获取所述地理文本流数据的地理位置所在区域rt,rt∈ε,计算所述区域rt的指纹f(rt.ID);

基于第二预设公式计算所述地理文本流数据的地理位置所在区域rt,在所述空间签名的布谷鸟哈希表中对应的两个桶值,其中,所述第二预设公式包括;

i = h1(rt.ID) ,j = h2(i,f(rt.ID)),其中,rt表示所述地理文本流数据的地理位置所在区域,rt∈ε,ε为将整个二维空间划分为多个等大小区域所得的区域集合,rt.ID表示区域rt所对应的唯一标记ID,h1和 h2表示两个哈希函数,f(rt.ID)是 rt.ID的指纹,i和j表示rt在所述空间签名的布谷鸟哈希表中对应的两个桶值;

判断所述空间签名的布谷鸟哈希表中的i桶或j桶中是否包含指纹f(rt.ID);

若是,则判定所述地理文本流数据的地理位置所在区域rt包含于所述空间签名。

6.如权利要求3或4所述的分布式订阅发布模式下的空间范围‑关键字查询方法,其特征在于,所述发布服务器遍历每个所述空间签名和每个所述文本签名组,与所述地理文本流数据进行空间包含关系判断和文本相似性计算包括:基于所述单排序最小哈希算法生成所述地理文本流数据的关键字集合对应的最小哈希签名;

基于第三预设公式计算所述最小哈希签名与所述文本签名组的相似度,其中,所述第三预设公式为:

其中, 表示所述地理文本流数据的关键字集合, 表示所述订阅关键字集合,表示所述地理文本流数据的关键字集合第 个字符串组的最小哈希值,表示所述订阅关键字集合第 个字符串组的最小哈希值, 表示所述最小哈希签名与所述文本签名组的相似度, 表示字符串分组个数, 表示第 个字符串组。

7.如权利要求6所述的分布式订阅发布模式下的空间范围‑关键字查询方法,其特征在于,所述基于所述空间包含关系判断和所述文本相似性计算结果,判断所述地理文本流数据是否命中至少一个订阅服务器包括:若所述地理文本流数据的地理位置所在区域的指纹包含于所述空间签名,且所述最小哈希签名与所述文本签名组的相似度大于或等于预设相似度阈值,则所述地理文本流数据命中至少一个订阅服务器,其中,所述预设相似度阈值为:。

8.如权利要求3至7中任一项所述的分布式订阅发布模式下的空间范围‑关键字查询方法,其特征在于,还包括:

由所述订阅服务器将所述空间签名和所述文本签名组部署到所述发布服务器上。

9.如权利要求8所述的分布式订阅发布模式下的空间范围‑关键字查询方法,其特征在于,在所述由所述订阅服务器将所述空间签名和所述文本签名组部署到所述发布服务器上之后,还包括:

当所述订阅服务器接收到新输入的空间范围‑关键字查询订阅时,更新带有倒排文件的四叉树索引;

基于更新后的倒排文件四叉树索引,更新签名集合;

将更新后的签名集合作为最新的文本签名组,将所述最新的文本签名组部署到所述发布服务器上。

10.一种空间范围‑关键字查询装置,其特征在于,包括存储有计算机程序的计算机可读存储介质和处理器,所述计算机程序被所述处理器读取并运行时,实现如权利要求1‑9任一项所述的分布式订阅发布模式下的空间范围‑关键字查询方法。