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

来源期刊:中南大学学报(自然科学版)2018年第11期

论文作者:沈瑛 陈望远 侯晨煜 徐锦婷 曹斌 董天阳 范菁

文章页码:2738 - 2745

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

Key words:query service; activity time conflict; Bitmap index; global optimization; time interval

摘    要:提出1种基于Bitmap的活动时间冲突查询算法。首先对原始数据预处理以构建Bitmap索引结构,然后构建两阶段查询算法:第1阶段遍历Bitmap索引得到满足各个活动持续时间的候选时间区间和候选用户集合,并过滤其中的无效用户、调整候选时间;第2阶段完成冲突区间组合优化,获得不冲突条件下活动组织的全局最优方案;最后,以8 628个用户的50 000条真实数据(时间跨度为1月)进行实验,分为单活动及多活动场景,以用户数量、时间范围、活动数量、持续时间等为测试指标,对比本文算法与滑动时间窗口法测试结果。研究结果表明:本文提出的算法能够满足大规模、涉及时间冲突的活动组织查询的时效性要求,该算法查询速度比滑动时间窗口法的查询速度快,单活动场景下其查询响应速度约为滑动时间窗口法的100倍。

Abstract: 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.

相关论文

  • 暂无!

相关知识点

  • 暂无!

有色金属在线官网  |   会议  |   在线投稿  |   购买纸书  |   科技图书馆

中南大学出版社 技术支持 版权声明   电话:0731-88830515 88830516   传真:0731-88710482   Email:administrator@cnnmol.com

互联网出版许可证:(署)网出证(京)字第342号   京ICP备17050991号-6      京公网安备11010802042557号