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

摘要:

权利要求书:

1.一种数据流相似性的连接方法,其特征在于,包括:

根据预设时间跨度值P在数据流R上构建B+树森林集合索引;

当所述数据流R和数据流S上的数据元组的时间戳在当前滑动窗口的时间范围内时,基于所述B+树森林集合索引,进行滑动窗口语义下基于地球移动距离EMD距离的所述数据流R和所述数据流S之间的相似性连接;

所述根据预设时间跨度值P在数据流R上构建B+树森林集合索引包括:

根据预设时间跨度值P把时间域划分为T个互相不重叠的时间区间,T大于等于1;

为所述R数据流上每个所述时间区间内达到的所述数据元组构建一个R数据流B+树森林索引,得到所述R数据流所述时间域上T个B+树森林索引,所述T个B+树森林索引构成所述R数据流的B+树森林集合索引;

在根据预设时间跨度值P在数据流R上构建B+树森林集合索引之后,还包括:

当所述B+树森林集合索引中所包含的数据元组的个数大于等于c*P的值且

Factive.maxTime-Factive.minTime>=P时,新建一个B+树森林索引Fnew,并将所述B+树森林索引Fnew设定为当前的活跃索引Factive;

其中,Factive.maxTime为当前活跃索引所维护的数据元组的最大时间戳,Factive.minTime为当前活跃索引所维护的数据元组的最小时间戳,c为预设的B+树森林索引的容量系数;

在基于所述B+树森林集合索引,进行滑动窗口语义下基于EMD距离的所述数据流R和所述数据流S之间的相似性连接之前,还包括:当接收到所述数据流S上的数据元组s之后,计算所述B+树森林集合索引中的每个所述时间区间上构建的B+树森林索引Fi中数据元组的最小时间戳和所述元祖s的时间戳之间的差值;

当所述差值大于所述滑动窗口大小和最大网络延迟之和时,删除所述B+树森林索引Fi;

还包括:设置所述预设时间跨度值

其中,|W|为所述滑动窗口大小。

2.根据权利要求1所述的数据流相似性的连接方法,其特征在于,所述基于所述B+树森林集合索引,进行滑动窗口语义下基于EMD距离的所述数据流R和所述数据流S之间的相似性连接,包括:基于所述数据流S中的数据元组si的时间戳,从B+树森林集合F中找到时间跨度区间和所述数据元组si要查询的时间滑动窗口有交集的所述B+树森林集合F';

当所述B+树森林集合F中的B+树森林Fj∈F'满足si.timestamp-Fj.maxTime≤|W|时,返回Fj中和si间的EMD距离不大于θ且时间戳落在si的滑动窗口范围内的所述R数据流上的数据元组R'{rj}和元组si构成的相似性连接结果元组对,将所述元组对存入结果集RSi。

3.根据权利要求2所述的数据流相似性的连接方法,其特征在于,所述返回Fj中和si间的EMD距离不大于θ且时间戳落在si的滑动窗口范围内的所述R数据流上的数据元组R'{rj}包括:满足公式1规定的区间范围的数据元组R'{rj},所述公式1规定的区间范围为[min(Фl)+key(s,Фl)-θ,θ-ckey(s,Фl)],min(Фl)是和EMD距离对偶线性规划问题的可行解Фl相关的实数,key(s,Фl)是s基于可行解Фl计算得到的键值,ckey(s,Фl)是s基于可行解Фl计算得到的反键值。

4.根据权利要求2所述的数据流相似性的连接方法,其特征在于,在返回Fj中和si间的EMD距离不大于θ且时间戳落在si的滑动窗口范围内的所述R数据流上的数据元组R'{rj}和元组si构成的相似性连接结果元组对之前,还包括:如果数据元组rj和数据元组si之间EMD距离的上界值小于或等于相似性阈值θ,则将所述元组对存入结果集RSupperbound。

5.根据权利要求2所述的数据流相似性的连接方法,其特征在于,在返回Fj中和si间的EMD距离不大于θ的所述R数据流上的数据元组R’{rj}和元组对之前,还包括:如果数据元组rj和数据元组si之间EMD距离的下界值大于相似性阈值θ,则将删除数据元组rj。

6.根据权利要求2所述的数据流相似性的连接方法,其特征在于,所述进行滑动窗口语义下基于EMD距离的所述数据流R和所述数据流S之间的相似性连接包括:将所述结果集RSi和所述结果集RSupperbound的并集作为所述相似性连接的结果。