基于Bitmap时间区间查...及其在智能会议管理中的应用_李光华.pdf

计算机与通信技术Computer and Communication Technology自动化技术与应用2023 年第 42 卷第 6 期Techniques ofAutomation&Applications基于Bitmap时间区间查询算法及其在智能会议管理中的应用李光华1,张洪涛2（1.国能大渡河大数据服务有限公司，四川 成都 610016；2.国能大渡河流域水电开发有限公司，四川 成都 610016）摘要:为了解决时间区间查询算法耗时较长的问题，提出一种基于Bitmap时间区间查询算法。首先对时间区间序列数据编码得到有界Bitmap，分析其相似性度量，并优化搜索终止条件，然后基于S-tree索引结构设计了最佳优先搜索算法。实验结果表明，与现有的滑动时间窗口算法和传统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 River 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 interval 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 existing 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引言时间区间序列是一个基于时间数据的区间值集合，描述了某个特定事件发生时间范围，如环境监测中空气指数超标时间段、医疗健康中心电监护时间范围。当前，如何提升时间区间查询方法的效率是时间区间序列研究的一个热点。Chan等采用滑动时间窗口法得到可行的时间设置方案。该方法需要遍历每1个粒度的时间点，当用户数据量较大时查询效率较低1。安籽鹏等基于时间约束网络提出一种时间冲突检测算法，解决了作战行动时间规划问题2。沈瑛等3基于Bitmap索引4提出一种活动时间查询算法，采用Bitmap索引得到候选时间区间和用户集合，并通过组合优化获得全局最优方案。该方法需要给每1个时刻建立1个Bitmap，且遍历所有用户的Bitmap索引，存在索引结构长度和查询耗时较长的问题。相似性搜索是时间区间序列数据查询研究常用的一种方法5-6。在Roh等7对时间区间序列相似性度量研究的基础上，设计了一种时间区间序列数据查询算法。该方法将时间区间序列数据进行Bitmap编码，通过相似性度量搜索相似的区间序列，并基于S-tree设计了最佳优先搜索算法。最后，采用某企业智能会议管理系统提供的时间区间序列数据进行实验，验证算法的有效性和高效性。2基于Bitmap时间区间查询算法时间区间序列是一个基于时间数据的区间值集合，每个数据点都是由时间起点（区间上限）和时间终点（区间下限）表示的区间数。下面给出一些与时间区间序列和相似性度量相关概念和术语7。定义1：一个长度为n时间区间序列X=X1,Xn,其中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个时间区间序列,其相似性度量为其中，|为L1范数。基于Bitmap时间区间查询算法分为3步：Step1：将时间区间序列数据进行Bitmap编码，得到对应的有界Bitmap；Step2：依据时间区间序列的相似性度量，给出有界Bitmap的相似度计算公式和基于相似度的搜索终止条件；Step3：基于S-tree设计索引结构有效组织Bitmap信息，并利用最大相似度设计最佳优先搜索算法，得到查询结果。2.1时间区间序列的Bitmap编码Bitmap编码是将数据信息采用固定长度的二进制位向量来表示，通过bit位置0或1记录信息的两种状态，再结合bit位的位置实现数据映射8。时间区间序列数据的Bitmap编码方法如下：对于时间区间序列编码，理论上将事件发生时间区间中的每个时刻采用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，记为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相似性度量定义如下：定义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相似度界限值。依据这一结论，采用阈值法优化了相似区间序列的搜索终止条件。设为相似度阈值，当样本数据集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 Communication 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指向后代节点，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最大相似度设计一种高效剪枝的最佳优先搜索算法。定义57：给定一个查询时间q和一个非叶节点Ni，其Bitmap最大相似性度量为式中，ei表示节点Ni中所有对象的有界Bitmap的重叠编码。显然易见,maxSim(Br(q),ei)Sim(Br(q),Br(X),即查询时间q与Ni的相似度必然大于（或等于）查询时间q与Ni中任一叶子节点的相似度。为此，利用最大相似度设计了最佳优先搜索算法。即当maxSim(Br(q)ei)时，表明Ni中所有对象与查询q之间的相似度必然小于，Ni所有对象应被直接剪枝。反之，再进一步判断Ni中是否包含候选对象。可见，利用最大相似度可极大缩小查询范围，有效提升搜索效率。算法详细过程如算法1所示。算法首先初始化一个优先级队列H和结果集RS，并将根节点放进队列H中（1行）。然后将H中的第一个元素N出队列，如果N是一个非叶节点，通过定义5计算该节点与查询时间q的最大相似度maxSim(Br(q),eN),如果maxSim(Br(q),eN),将该节点包含的所有对象加入到队列H中，否则，根据定义5将其直接剪枝（2-5行）。对于加入队列H的每一个对象ei，首先获得该对象的对应时间序列xi，通过定义4和定义3计算其与查询时间q之间的相似度（7-10行）。一旦找到某个对象满足条件Sim(Br(q),Br(ei)且Sim(q,xi),搜索算法停止，算法返回结果集RS（11行）。算法的复杂度为O(|RS(q)|logN)，其中N为时间区间序列数据的个数，|RS(q)|为查询结果的数据长度。算法1：最佳优先搜索算法输入：查询时间区间q，相似度下限阈值，S-treeT输出：结果集RS1:Br(q)bitmap of q with bin sizer;RS，Hroot of T2：While H is not empty do3：NH.pop()4：if N is not a leaf node then5:if maxSim(Br(q),eN)thenH.push(children of N)6：else7:for each eiN do8:xi=ei.sequence;9:if Sim(Br(q),Br(ei)and Sim(q,xi)the10:RSRSxi11:return RS3实验结果分析为了验证查询算法的有效性，选用某企业智能会议管理系统提供的数据进行实验。智能会议管理系统的基110自动化技术与应用2023 年第 42 卷第 6 期计算机与通信技术Computer and Communication TechnologyTechniques ofAutomation&Applications本功能包括会议预定、会议安排和会议通知，其中会议安排需要查询用户的空闲时间区间来合理安排会议时间，才能避免时间上的冲突11。文中采用了8 000条时间区间序列数据进行实验，首先通过改变有界Bitmap|B|的长度来研究查询算法的性能，分析不同|B|长度对查询算法性能的影响。然后，将查询算法与其他查询算法进行比较。本实验软硬环境为Win10 64位操作系统，2.5 GHz英特尔酷睿双核i5处理器，8 GB内存，编译器为MAT-LAB 2020a。3.1性能分析算法中|B|的长度是影响算法性能的一个重要因素。|B|长度过长将增加S-tree结构的规模，降低算法的响应特性，但时间粒度r更小，编码精度更高，有利于提高算法精度。选取U=1 024，|B|长度依次为96、128、192、256、512（|B|=|U|/r）进行实验。对于S-tree结构特性的评价采用平均响应时间和剪枝效率2个指标，对于算法性能的评价指标通常为精确率P、召回率R和F1值，其中F1值表示精确率和召回率的调和平均，采用F1值进行评价，计算公式如下：(2)式中，,。实验结果如图3图5所示。从图3可知当|B|=256时，算法的平均响应时间逐渐增加；从图4可知随着|B|的长度增加，算法的剪枝效率逐渐提高，当|B|=256趋于平稳；从图5可知随着|B|的长度增加，算法的F1值逐渐增大。由此进一步表明了|B|长度对S-tree结构特性和算法性能的影响，在时间域U=1 024时，|B|长度取值为256，可确保S-tree结构特性和算法性能均良好。图3平均响应时间变化曲线图4剪枝效率变化曲线3.2查询时间对比分析为了验证查询算法的优越性，分别与滑动时间窗口算法1、文献3中的传统 Bitmap 查询算法进行对比实验。在上一节实验结果的基础上，参数设置如下：|B|=256，=1.2，U=1 024。图5F1值变化曲线图6不同算法的查询耗时对比图6给出了3种算法的随着数据量增加查询耗时的变化曲线。分析图6可知，随着数据量逐渐增加，3种查询算法的查询耗时都在增加，但本查询算法的耗时较少，且增加缓慢。4结束语在信息技术时代，环境监测、智能会议管理等诸多应用都面临着时间区间数据的查询问题。采用Bitmap编码和S-tree索引结构设计了一种时间区间查询算法。该方法利用S-tree管理时间区间数据转换的Bitmap信息，根据非叶节点Bitmap进行有效剪枝，提升了查询响应时间。实验结果表明，方法能够更好的解决查询耗时问题，具有良好的有效性和高效性。参考文献:1 Chan H L,Lam T W,Lee L K,et al.Continuous mon-itoring of distributed data streams over a time-based slidingwindowJ.Algorithmica,2012(62):1088-1111.2 安籽鹏,李锋,万刚,等.基于时间约束网的作战行动时间冲突检测J.系统仿真学报,2017,29(S1):171-176.3 沈瑛,陈望远,侯晨煜,等.一种基于Bitmap的活动时间冲突查询算法J.中南大学学报(自然科学版),2018,49(11):102-108.4 CHAN C Y,IOANNIDIS Y E.Bitmap Index Designand EvaluationJ.ACM SIGMOD Record,1998,27(2):355-366.5 Afalg J,Kriegel H P,Krger P,et al.Similarity Searchon Time Series Based on Threshold QueriesC.EDBT 2006Lecture Notes in Computer Science,Springer,Berlin,Heidel-berg,2006(3896):276-294.(下转第149页)111自动化技术与应用2023 年第 42 卷第 6 期行业应用与交流Industrial Applications and CommunicationsTechniques ofAutomation&Applications程度，信用误差度是指衡量遵约守信程度结果与参考值之间的误差，其中参考值由约定量值来体现。将信誉误差度作为测试指标，对方法1、方法2和方法3进行测试，通过图2表征上述方法的测试结果。通过图2中的数据可知，方法1的信誉误差度远远低于方法2和方法3的信誉误差度，因为方法1对众包系统多维信誉进行评估之前，对众包系统中存在的不同维度的信誉信息进行了整合处理，提高了信誉度计算结果的精准度，降低了方法1的信誉度误差。采用方法1、方法2和方法3对众包系统的信誉进行评估，对比不同方法的评估精准度，测试结果如图3所示。图3评估精准度测试结果由图3可知，在多次迭代中采用方法2和方法3对众包系统的信誉进行评估的精准度，远远低于方法1对众包系统信誉进行评估的精准度，因为方法1通过数据整合处理后可获得高精度的众包系统多维信誉数据，利用高精度的多维信誉数据可准确地完成众包系统的多维信誉评估，提高了方法的评估精准度。5结束语目前大部分众包系统的规章制度还不完善，容易受到蓄意破坏，影响众包系统的稳定性，因此需要对众包系统的信誉进行评估。目前众包系统信誉评估方法存在评估时延大、信誉误差度高和评估精准度低的问题，提出基于模糊理论的众包系统多维信誉智能评估方法，可在较短时延下，精准地完成信誉度计算和信誉评估，解决了目前方法中存在的问题，为众包系统的应用提供了保障。参考文献:1 易校石,刘念.山地电力架空线路运维质量的智能评估J.西南大学学报:自然科学版,2020(1):124-133.2 徐刚,张磊,田磊.航空弹药技术保障模拟训练智能评估J.系统仿真学报,2020,32(6):133-146.3 刘迎春,谢年春,李佳.虚拟学习社区中基于用户行为的知识贡献者信誉评价研究J.现代情报,2020,40(3):117-125.4 史雪艳,张周胜,董娜,等.基于自适应PSO-LSSVM多维开关柜数据的状态评估方法J.水电能源科学,2019,37(1):141,185-188.5 陈赵懿,高秀峰,王帅,等.基于信誉评估的Ad hoc分布式入侵检测J.火力与指挥控制,2020,45(9):8-13.6 霍星,张阳洋,景永俊,等.MAS环境中一种基于反馈可信度的多维信誉计算方法J.软件学报,2020,31(2):132-152.7 方修琦,赵琬一,张成鹏,等.全球历史LUCC数据集数据可靠性的评估方法及评估案例J.中国科学:地球科学,2020,50(7):149-160.8 杨铮宇,田园,李申章.基于主成分分析和层次分析的高压电力用户信用评价模型研究J.云南大学学报(自然科学版),2020,42(2):12-18.作者简介:郝晓英（1989-），女，硕士，助教，研究方向：数学专业，模糊数学。6 Roh J W,Yi B K.Efficient indexing of interval timesequencesJ.Information Processing Letters,2008,109(1):1-12.7 Jong-won Roh,Seung-won Hwang,Byoung-Kee Yi.Efficient bitmap-based indexing of time-based interval se-quencesJ.Information Sciences,2012,194(5):38-56.8 V.Seshadri et al.,Fast Bulk Bitwise AND and OR inDRAM,IEEE Computer Architecture Letters,2015,14(2):127-131.9 DeppischU.S-tree:A dynamic balanced signature indexfor office retrievalC.Proceeding of special interest group oninformation retrieval conference.NewYork:ACM,1986:77-87.10 N.Beckmann,HP.Kriegel,R.Schneider,B.Seeger.TheR*-tree:An efficient and robust access method for points andrectanglesC.Proceeding of special interest group on man-agement of data conference.Atlantic city,1990:322-331.11 徐进.交互式多点视频会议系统的纯软件实现J.计算机工程与设计,2003,24(9):19-21.作者简介:李光华(1985-)，男，硕士，中级工程师，从事大数据应用与研究工作。(上接第111页)149