基于Bitmap时间区间查...及其在智能会议管理中的应用_李光华.pdf
《基于Bitmap时间区间查...及其在智能会议管理中的应用_李光华.pdf》由会员分享,可在线阅读,更多相关《基于Bitmap时间区间查...及其在智能会议管理中的应用_李光华.pdf(5页珍藏版)》请在咨信网上搜索。
1、计算机与通信技术Computer and Communication Technology自动化技术与应用2023 年第 42 卷第 6 期Techniques ofAutomation&Applications基于Bitmap时间区间查询算法及其在智能会议管理中的应用李光华1,张洪涛2(1.国能大渡河大数据服务有限公司,四川 成都 610016;2.国能大渡河流域水电开发有限公司,四川 成都 610016)摘要:为了解决时间区间查询算法耗时较长的问题,提出一种基于Bitmap时间区间查询算法。首先对时间区间序列数据编码得到有界Bitmap,分析其相似性度量,并优化搜索终止条件,然后基于S-t
2、ree索引结构设计了最佳优先搜索算法。实验结果表明,与现有的滑动时间窗口算法和传统Bitmap查询算法相比,本文算法查询耗时较少,具有良好的有效性和高效性。关键词:时间区间序列;Bitmap编码;S-tree索引中图分类号:TP301.6文献标识码:A文章编号:1003-7241(2023)06-0108-05Time Interval Query Algorithm Based on Bitmap and Applicationin Intelligent Conference ManagementLI Guang-hua1,ZHANG Hong-tao2(1.Guoneng Dadu Ri
3、ver Big Data Service Co.,Ltd.,Chengdu 610016 China;2.Guoneng Dadu River Basin Hydropower Development Co.,Ltd.,Chengdu 610016 China)Abstract:In order to solve the time-consuming problem of time interval query algorithm,a time interval query algorithm based on bitmap isproposed.Firstly,the time interv
4、al sequence is transformed into bitmaps of fixed length by a bin-bitmap method,and through ana-lyzing its similarity measure the search conditions are given.Then,the best priority search algorithm is designed based on S-treeindex structure.The experimental results show that compared with the existin
5、g sliding time window algorithm and traditional bit-map query algorithm,this method has good effectiveness and efficiency with a short time consuming.Keywords:time interval sequence;Bitmap encoding;S-tree index收稿日期:2021-11-25DOI:10.20033/j.1003-7241.(2023)06-0108-05.1引言时间区间序列是一个基于时间数据的区间值集合,描述了某个特定事
6、件发生时间范围,如环境监测中空气指数超标时间段、医疗健康中心电监护时间范围。当前,如何提升时间区间查询方法的效率是时间区间序列研究的一个热点。Chan等采用滑动时间窗口法得到可行的时间设置方案。该方法需要遍历每1个粒度的时间点,当用户数据量较大时查询效率较低1。安籽鹏等基于时间约束网络提出一种时间冲突检测算法,解决了作战行动时间规划问题2。沈瑛等3基于Bitmap索引4提出一种活动时间查询算法,采用Bitmap索引得到候选时间区间和用户集合,并通过组合优化获得全局最优方案。该方法需要给每1个时刻建立1个Bitmap,且遍历所有用户的Bitmap索引,存在索引结构长度和查询耗时较长的问题。相似性
7、搜索是时间区间序列数据查询研究常用的一种方法5-6。在Roh等7对时间区间序列相似性度量研究的基础上,设计了一种时间区间序列数据查询算法。该方法将时间区间序列数据进行Bitmap编码,通过相似性度量搜索相似的区间序列,并基于S-tree设计了最佳优先搜索算法。最后,采用某企业智能会议管理系统提供的时间区间序列数据进行实验,验证算法的有效性和高效性。2基于Bitmap时间区间查询算法时间区间序列是一个基于时间数据的区间值集合,每个数据点都是由时间起点(区间上限)和时间终点(区间下限)表示的区间数。下面给出一些与时间区间序列和相似性度量相关概念和术语7。定义1:一个长度为n时间区间序列X=X1,X
8、n,其中Xi表示一个由开始时间和结束时间限定的时间区间,记为Xi=,为开始时间,为结束时间,且,。设X和Y是2个时间区间序列,常用集合运算符定义如下:1)XY,表示X和Y的子区间交集;2)X-Y,表示X的子区间与Y补集的子区间交集;108自动化技术与应用2023 年第 42 卷第 6 期计算机与通信技术Computer and Communication TechnologyTechniques ofAutomation&Applications3)|X|,表示集合X的总长度。定义2:设Xi和Yi分别是2个时间区间序列中的第i个元素,其Lp范数为定义3:设X=X1,Xn和Y=Y1,Ym分别为2
9、个时间区间序列,其相似性度量为其中,|为L1范数。基于Bitmap时间区间查询算法分为3步:Step1:将时间区间序列数据进行Bitmap编码,得到对应的有界Bitmap;Step2:依据时间区间序列的相似性度量,给出有界Bitmap的相似度计算公式和基于相似度的搜索终止条件;Step3:基于S-tree设计索引结构有效组织Bitmap信息,并利用最大相似度设计最佳优先搜索算法,得到查询结果。2.1时间区间序列的Bitmap编码Bitmap编码是将数据信息采用固定长度的二进制位向量来表示,通过bit位置0或1记录信息的两种状态,再结合bit位的位置实现数据映射8。时间区间序列数据的Bitmap
10、编码方法如下:对于时间区间序列编码,理论上将事件发生时间区间中的每个时刻采用1个位向量(Bitmap)表示。但在实际应用中,每个时刻对应1个Bitmap的编码方式将造成过高的存储开销。为此,采用时间粒度r来调节Bitmap编码精度,以降低存储开销。设U为时间域,按照时间粒度r将整个时间域划分为多个子域u,每个子域用一个bit位表示,根据子域占位情况形成2种编码方式:1)上边界编码:当uX,该子域对应位置为“1”,反之,则置“0”,记为(X);2)下边界编码:当uX=X,该子域对应位将置为“1”,反之,则置“0”,记为(X)。图1时间区间序列Bitmap编码最后所得编码结果统称为有界Bitmap
11、,记为Br(X)。图1为某时间区间序列的Bitmap编码(r=4,U=32)。可见,r取值越小,Bitmap编码精度越高。r取值不仅决定了编码精度,还直接影响存储开销。2.2相似性度量在时间区间序列相似性度量的基础上进行扩展,得到有界Bitmap的相似性度量计算公式,并优化了相似序列的搜索终止条件。定义3给出了时间区间序列相似性度量的计算公式,对其进行扩展得到传统 Bitmap 相似性度量的计算公式。对于定义3计算公式中的交集运算XY、差集运算X-Y和Y-X分别用B(X)B(Y),B(X)B(Y)和B(X)B(Y)替代,集合长度用Bitmap中“1”的数目替代,得到传统Bitmap相似性度量定
12、义如下:定义47:设B(X)和B(Y)分别为2个Bitmap,其相似性度量为其中,|为1数目。采用有界Bitmap的上边界编码和下边界编码对定义4进行改造,得到有界Bitmap相似度界限值的计算公式如下:(1)由上边界编码原理得出:r|(X)|X|,r|(Y)|Y|;于是,r|(X)(Y)|XY|。由下边界编码原理得出:r|(X)|X|和r|(Y)|U-Y|。于是,r|(X)(Y)|X-Y|。同理可得,r|(X)(Y)|Y-X|。由此得知Sim(Br(X),Br(Y)Sim(X,Y)即2个时间序列X和Y的相似性度量值必然不会超过其有界Bitmap相似度界限值。依据这一结论,采用阈值法优化了相似
13、区间序列的搜索终止条件。设为相似度阈值,当样本数据集X中存在与查询时间相重合的数据集,那么2者的相似性度量值大于或等于,即Sim(q,X)。根据上面分析可知其有界Bitmap相似性界限值也必然大于或等于,即Sim(Br(q),Br(X)。反之,若 Sim(Br(q),Br(X),则必然存在Sim(q,X)。为此,首先判断样本数据与查询时间的有界Bitmap是否满足阈值条件,若不满足,则无需进一步检查时间区间序列的相似度,从而减少计算开销,优化了搜索终止条件。2.3查询算法为解决时间区间查询算法的耗时问题,基于S-tree9109计算机与通信技术Computer and Communicatio
14、n Technology自动化技术与应用2023 年第 42 卷第 6 期Techniques ofAutomation&Applications设计一种索引结构组织各种Bitmap信息,并采用Bitmap最大相似度设计最佳优先搜索算法。下面介绍索引结构的构建过程。2.3.1S-tree索引结构S-tree是一颗平衡树,它与适用于多维空间数据索引的R-tree10的构建过程类似。每一个叶子节点的信息以(userid,Br(X)的形式记录,其中userid是用户的唯一标识,Br(X)是时间区间序列基于时间粒度r编码所得的有界Bitmap。非叶子节点的信息则以(ei,pi)的形式记录,其中pi指向
15、后代节点,ei是后代节点包含所有对象的有界Bitmap 的重叠编码。对于新节点的插入,S-tree 采用Bitmap最小权重准则进行分层重组,其中Bitmap权重定义为“1”元素的数目。图2(a)为一系列时间区间序列原始数据,图2(b)为采用上边界编码所构建的S-tree索引结构,其中U=64,r=8。(a)时间区间序列原始数据(b)S-tree索引结构图2S-tree索引结构的构建2.3.2S-tree查询算法通常S-tree搜索算法首先遍历根节点,再迭代访问其后代节点,需要检查每一个遍历节点来做进一步判断,这将花费很大的时间代价。利用非叶节点的Bitmap最大相似度设计一种高效剪枝的最佳优
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 Bitmap 时间 区间 及其 智能 会议 管理 中的 应用 光华
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。