自然科学版 英文版
自然科学版 英文版
自然科学版 英文版
自然科学版 英文版
英文版编委
自然科学版 英文版
英文版首届青年编委

您目前所在的位置:首页 - 期刊简介 - 详细页面

中南大学学报(自然科学版)

Journal of Central South University

第49卷    第11期    总第291期    2018年11月

[PDF全文下载]    [Flash在线阅读]

    

文章编号:1672-7207(2018)11-2738-07
一种基于Bitmap的活动时间冲突查询算法
沈瑛,陈望远,侯晨煜,徐锦婷,曹斌,董天阳,范菁

(浙江工业大学 计算机科学与技术学院,浙江 杭州,310023)

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

 

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

A bitmap index based activities conflict query algorithm
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

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.

 

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

中南大学学报(自然科学版)
  ISSN 1672-7207
CN 43-1426/N
ZDXZAC
中南大学学报(英文版)
  ISSN 2095-2899
CN 43-1516/TB
JCSTFT
版权所有:《中南大学学报(自然科学版、英文版)》编辑部
地 址:湖南省长沙市中南大学 邮编: 410083
电 话: 0731-88879765(中) 88836963(英) 传真: 0731-88877727
电子邮箱:zngdxb@csu.edu.cn 湘ICP备09001153号