一种基于Bitmap的活动时间冲突查询算法  

A bitmap index based activities conflict query algorithm

作　　者：沈瑛[1] 陈望远 侯晨煜 徐锦婷[1] 曹斌[1] 董天阳[1] 范菁[1] SHEN Ying;CHEN Wangyuan;HOU Chenyu;XU Jinting;CAO Bin;DONG Tianyang;FAN Jing(College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China)

机构地区：[1]浙江工业大学计算机科学与技术学院,浙江杭州310023

出　　处：《中南大学学报（自然科学版）》2018年第11期2738-2744,共7页Journal of Central South University:Science and Technology

基　　金：国家重点研发计划项目(2016YFB1001403);国家自然科学基金资助项目(61602411);浙江省重大科技专项重点工业项目(2015C01034;2017C01013);杭州市重大科技创新项目(20152011A03)~~

摘　　要：提出1种基于Bitmap的活动时间冲突查询算法。首先对原始数据预处理以构建Bitmap索引结构,然后构建两阶段查询算法:第1阶段遍历Bitmap索引得到满足各个活动持续时间的候选时间区间和候选用户集合,并过滤其中的无效用户、调整候选时间;第2阶段完成冲突区间组合优化,获得不冲突条件下活动组织的全局最优方案;最后,以8 628个用户的50 000条真实数据(时间跨度为1月)进行实验,分为单活动及多活动场景,以用户数量、时间范围、活动数量、持续时间等为测试指标,对比本文算法与滑动时间窗口法测试结果。研究结果表明:本文提出的算法能够满足大规模、涉及时间冲突的活动组织查询的时效性要求,该算法查询速度比滑动时间窗口法的查询速度快,单活动场景下其查询响应速度约为滑动时间窗口法的100倍。A Bitmap index based activities conflict query algorithm was proposed.Firstly,original data was preprocessed by the algorithm to construct Bitmap index structure,then the two-phase query algorithm was constructed.During the first phase,the Bitmap index was traversed using the query algorithm to pick out candidates of time ranges and users which meet the activity duration requirements.Then invalid users were filtered and time ranges were adjusted.During the second phase,time intervals were optimized to find out non-conflict global optimized activity schemes.Experiments in single activity and multiple activities scenes with variations in user number,activity number,and time range and time duration were conducted on a dataset with 50 000 records of 8 628 users collected in one month.The performance of the proposed algorithm and sliding time window algorithm were compared.The results show that the proposed algorithm can meet time efficiency requirement of large-scale conflicted activity organization query.The proposed Bitmap based algorithm has an obvious advantage over sliding time window algorithm in query speed.In single activity scene,the query speed of the proposed algorithm is nearly 100 times faster than that of sliding time window algorithm.

关 键 词：查询服务 活动时间冲突 Bitmap索引 全局最优 时间区间 

分 类 号：TP391.1[自动化与计算机技术—计算机应用技术]