DOI: 10.11817/j.issn.1672-7207.2018.11.014
一种基于Bitmap的活动时间冲突查询算法
沈瑛，陈望远，侯晨煜，徐锦婷，曹斌，董天阳，范菁
(浙江工业大学 计算机科学与技术学院，浙江 杭州，310023)
摘 要：
itmap的活动时间冲突查询算法。首先对原始数据预处理以构建Bitmap索引结构，然后构建两阶段查询算法：第1阶段遍历Bitmap索引得到满足各个活动持续时间的候选时间区间和候选用户集合，并过滤其中的无效用户、调整候选时间；第2阶段完成冲突区间组合优化，获得不冲突条件下活动组织的全局最优方案；最后，以8 628个用户的50 000条真实数据(时间跨度为1月)进行实验，分为单活动及多活动场景，以用户数量、时间范围、活动数量、持续时间等为测试指标，对比本文算法与滑动时间窗口法测试结果。研究结果表明：本文提出的算法能够满足大规模、涉及时间冲突的活动组织查询的时效性要求，该算法查询速度比滑动时间窗口法的查询速度快，单活动场景下其查询响应速度约为滑动时间窗口法的100倍。
关键词：
查询服务；活动时间冲突；Bitmap索引；全局最优；时间区间；
中图分类号：TP391.1 文献标志码：A 文章编号：1672-7207(2018)11-2738-07
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
在旅行、系列会议组织等面向大规模、多用户、多活动的方案查询应用场景中，查询效率依赖于支持时间冲突[1]协调的查询算法，即给定多个用户和对应的空闲时间区间，有多个活动要举办且每个活动需要持续一定时间，查询时间上不冲突且参与活动总人次最多的合理活动组织方案。一般可采用固定滑动时间法[2]，通过设置固定的活动持续时间窗口，然后沿着时间线逐步获取每个时间区间及该区间内的用户，并优化每个活动的查询结果，得到可行的活动时间组合方案，但这种方法在时序数据量较大时查询耗时较长。Bitmap索引[3]是数据库中常用的多维数据查询处理技术，它将对象的索引信息采用游程编码压缩技术[4]存储成一系列二进制位向量[5]，具有空间开销较小、查询响应速度快的优势。本文作者提出1种基于Bitmap的活动时间冲突查询算法；首先对用户的有效时间区间数据进行预处理，建立Bitmap索引结构，然后遍历索引结构，获取每个活动的候选时间区间和对应的候选用户集合，最后对查询结果进行组合优化得到无冲突的活动全局最优方案，基于真实的用户时间数据，评估不同的影响因素对查询算法的影响，验证算法的有效性。
1 相关工作
活动时间冲突问题类似于时态数据库中的时态聚集查询问题，主要包括时态查询语言中对时态聚集的支持[6]、时态聚集索引[7]、时态聚集实例化、时态聚集查询算法[8]等。其中，时态聚集查询算法非常关键，它涉及时态分组的问题，必须先把时间序列划分为时间区间并分组计算聚集值。
典型的时态聚集查询算法可根据有、无索引分为2类。无索引的算法通过预扫描数据在内存中保存局部结果[9-11]：有的基于聚集树求得聚集结果[9]，但节点插入时会影响算法整体性能；有的算法基于平衡树[10]的叶节点存储聚集结果，搜索效率和调整效率较高，但需要元组排序开销较大；还有些基于并行算法[12]。基于时态索引的算法一般将局部聚集计算结果以索引形式存于外存储器中[13]。
然而，上述时态聚集查询算法都不能直接应用于解决活动时间冲突问题。这是因为活动时间冲突问题的场景与典型时态聚集查询存在查询目的、约束和处理逻辑上的差异。1) 查询目的不同。传统时态聚集查询通常是针对某一时刻或时间区间的用户聚合值，但活动时间冲突问题需要查询的是活动时间不发生冲突时，总用户数最大的时间区间。2) 查询约束不同。活动时间冲突问题的约束为待查询时间区间必须满足的活动持续时间和查询时间范围。3) 查询处理逻辑不同。活动时间冲突查询的最佳结果中的用户存在时间区间必须完全覆盖待查询的最优时间区间，而不仅是有交集。
2 问题定义
2.1 数据说明
1) 原始数据集。时序数据是以规律的时间顺序采集的时间序列的集合[14]。本文所研究的原始用户时序数据即为用户在1个月内的空闲时间区间。它的元素是一个二元组，第1分量为用户的唯一标识，第2分量为用户的所有空闲时间区间的列表，每个空闲时间为从开始时刻到结束时刻的1个时间片。
2) 持续时间。持续时间是由活动组织者预先设定的举办活动需要的最短时长。若某用户存在空闲时间区间包含某个活动持续时间的情形，即该用户能参加该活动，则认为用户对该活动有效；否则为不能参加该活动的无效用户。
例如某晚会的持续时间设为2 h，而用户A在2017-07-07T20:00:00—22:00:00有空，用户B在2017-07-08T19:30:00—21:00:00有空，那么用户A是该晚会的有效用户之一，用户B不能参与该晚会。
3) 时间范围。时间范围可看作是一个大的时间区间，在活动查询前设定，是所有要举办的活动在时间上的约束。
例如某个活动要求在2017-07-07T09:00:00—21:00:00范围内举办，其时间范围可描述为[2017-07-07T09:00:00, 2017-07-07T21:00:00]。
4) 预处理数据集。以1个活动的持续时间对用户时序数据进行预处理后，可以构建用户信息表，如表1所示。用户信息表存储所有满足持续时间的有效用户和对应的有效时间区间。
表1 用户信息表
Table 1 User Table
2.2 活动时间问题定义
基于上述基本概念，活动时间冲突问题可以定义下述概念。
冲突。若2个时间区间IA和IB满足IA∩IB≠
，则认为这2个时间区间发生冲突。
活动时间冲突问题。给定1个数据集，包含了多个用户U的若干空闲时段I。若有多个活动(活动总个数n≥1)需在某时间范围R内举办，则活动的持续时间Di(Di＞0，i∈N，N={1, 2, 3, …, n})及活动的最优活动时间Oi (Oi＞0, i∈N)应满足如下条件：
1) Oi≥Di。
2) 对任意Ok,，Ok与其他Oi之间不发生冲突；i, k∈{1, 2, 3, …, n}。
3) 覆盖Oi的活动的总参与人次最多。
3 基于Bitmap的活动时间冲突查询算法
为提高活动冲突查询算法的性能，本文作者以用户信息表构建Bitmap索引，使得每个有效用户时间区间的时刻对应1个Bitmap，并设计相应的算法来支持活动冲突查询。
基于Bitmap的活动时间冲突查询算法需要2个输入：一是用户信息表中的所有用户以及对应的时间区间信息；二是查询的时间范围和根据多个活动的查询要求给定的多个持续时间。算法的输出是能使全部活动参与人次最大化的每个活动的最优活动举办时间和参与所有活动的总人次。
在查询之前先通过输入的用户信息表数据构造Bitmap索引，基于Bitmap索引的查询算法可以分为2个阶段：第1阶段遍历Bitmap索引得到满足各个活动持续时间的候选时间区间和候选用户集合；第2阶段对各个活动的候选时间区间进行组合优化，找出组合后所有活动的用户总人次最大并且时间上互不发生冲突的最优时间区间。
3.1 Bitmap索引结构
本文中需要构建的Bitmap索引由用户信息表中用户时间区间的某一时刻以及该时刻对应的Bitmap位串2部分组成。先根据用户信息表中的用户输入顺序编制每个用户在索引比特位串中的位置Bu。若Bu为1，则表示当前时刻处于用户的某个空闲区间I内；若用户无空闲时间，则Bu为0。根据表1中的用户信息可以得到Bitmap索引结构，如表2所示(其中ti为时间，i∈N)。
表2 Bitmap索引结构表
Table 2 Bitmap index structure
3.2 Bitmap索引初始构造算法
构建Bitmap索引的过程如下：读取所有用户的时间序列数据和持续时间窗口大小，给每个用户标记用户位置Bu，得到用户位置的映射表，并得到所有用户区间的开始和结束时刻。给每个时刻建立1个Bitmap位串并赋值，若用户的有效时间区间包含当前时刻，则将位串中该用户对应的比特位置1，否则置0。最后得到每个用户的1个时刻对应1个Bitmap位串的索引映射表。
上面构建好的Bitmap索引结构存在存储空间消耗巨大及索引长度过长的缺点。以50 000条记录和近万用户数为例，构建Bitmap索引需要超过1 G的存储空间。查询算法中需要得到其中2个时刻对应的Bitmap位串进行按位与运算，并提取“1”的比特位对应的用户，加入候选用户集。如果不进行压缩处理，则需要遍历近万个位置和用户，会大大降低查询的时间效率，因此，很有必要对上述Bitmap索引结构进行压缩操作。下面将Bitmap位串按游程压缩，即以连续相同的比特值和相同位的数量取代原始子串。
3.3 Bitmap查询算法
3.3.1 遍历Bitmap索引获取中间结果
遍历Bitmap索引获取中间结果为查询算法的第1阶段，具体又分为3步。
步骤1：获取候选时间区间和候选用户集合。首先对所有用户在线时间区间内所有起始、结束时刻按时间排序，构成时刻表。遍历时刻表，若当前时刻是某用户在线时间区间的起始时刻，则从这个起始时刻往后搜寻第1个满足活动持续时间区间的终止时刻，从而以起始时刻、结束时刻构成1个候选时间区间。将候选时间区间的起始、结束时刻对应的用户位串进行压缩，并2串进行按位与运算，遍历结果串中所有值为1的比特位，提取对应的用户，加入候选用户集。
步骤2：过滤候选用户集中的无效用户。步骤1得到的候选用户集合中可能存在某些无效用户，其空闲时间区间不能完全覆盖候选区间。本步骤主要过滤无效用户，处理逻辑如下：对每个候选用户设置1个初值为0的计数器，从头开始检查该用户的所有空闲区间集合，判断是否能覆盖候选区间的起始时刻。1) 若当前区间不能覆盖候选区间的起始时刻，则计数器加1，并检查当前区间是否包含候选区间的结束时刻。若是，则判定该用户为无效用户，保存此时的计数器值，结束对该用户的区间检查。若否，则继续检查该用户的下1个区间。2) 若当前区间能覆盖候选区间的起始时刻，则继续判断它是否覆盖候选区间的结束时刻。若是，则该用户不是无效用户，保存此时的计数器值，结束对该用户区间集合的遍历。若否，则该用户是无效用户。
通过上述过滤方法，就能够过滤掉候选用户集合中的无效用户。
步骤3：调整候选时间区间。当完成前2个步骤后，遍历排序后的时刻列表找到起始时刻后的第2个结束时刻。重复步骤1和步骤2，得到新的候选区间及候选用户集合。比较前后2次的候选用户集合，若元素个数相同，则将初次候选区间的结束时刻替换为新候选区间的结束时刻，然后，继续找到时刻表候选区间起始时刻中的第3个结束时刻，继续重复步骤1和步骤2，直到后1个候选用户集合的元素个数小于前1个候选用户集合的元素个数为止，最终得到优化后的候选时间区间Ic和对应的候选用户集合Uc。候选区间和候选用户集合映射表如表3所示。其中，Ici为不同的候选区间，Uci为不同的候选用户，i∈N。
表3 候选区间和候选用户集合映射表
Table 3 Candidate interval and candidate user set map
3.3.2 冲突区间组合优化算法
第1阶段查询得到多个活动的候选时间区间和对应的候选用户集合。为了在特定时间范围内得到所有活动的具体举办时间段，并保证参与所有活动的总人次最大化，需要通过第2阶段对结果组合优化。
例如，有3个持续时间分别为1，2和3 h的活动，首先需要进行3次独立查询，通过遍历Bitmap索引结构分别得到3个活动对应的候选区间和候选用户集合，然后对这3个活动对应的候选区间和候选用户集合进行组合优化，即分别从3个活动对应的候选时间区间集合中选取3个候选区间，在保证所选3个候选时间区间在时间上不发生冲突的情况下，使得3个候选区间对应的候选用户集合中的用户数加起来最大。
活动冲突组合优化算法流程如下。
算法1：活动冲突组合优化算法
输入：每个活动的候选区间和候选用户集合映射表Tci(i=1, 2, 3, …)，表中每个候选区间对应覆盖它的候选用户数量。
输出：结果映射表Top，表中多个不冲突活动的具体举办时间对应这些活动的最大的总参与人次。
P=, LI=, max=0, S=0
FOR Ici IN Tci
LI.add(Ici)
S=S +Tci.get(Ici)
IF S > max
IF not Conflicted(LI)
P.put(LI, S)
max = S
Top=
FOR l IN P
IF P.get(l) == max
Top.put(l, max)
RETURN Top
其中，P为方案中间结果；max为最大总参与人数；S为当前最大总参与人数；Ici为第i个活动的候选时间区间；LI为候选活动列表，i∈N。
4 实验评估
下面针对基于Bitmap索引的活动冲突查询算法的性能指标进行实验评估。本实验的原始数据来自用户行为日志，包括8 628个用户的50 000条时间序列数据(时间跨度为1个月)。在实验过程中，根据实验的影响因素对原始数据进行调整。首先在单个活动查询请求的情况下，将Bitmap索引算法与传统的滑动时间窗口方法进行比较。采用控制变量的方法即改变其中1个影响因素并保持其他影响因素不变，对2种查询算法进行实验对比分析。然后，通过活动数量、活动持续时间和时间范围这几个因素来研究基于Bitmap的活动时间冲突查询算法在活动冲突查询请求下的性能，探究其在不同影响因素下的效果以及算法在不同阶段所消耗的时间。本实验硬件如下：2.70 GHz双核英特尔酷睿i5处理器，8 GB内存，128 GB的固态硬盘，操作系统为MacOS Sierra 10.12.1。
4.1 单活动场景下2种查询算法性能比较
活动数量为1个是活动冲突问题的特殊情况，此时活动不发生冲突。为了比较Bitmap查询算法与普通的滑动时间窗口算法，本文研究在单活动查询请求情况下不同数据量(用户记录)和活动持续时间对2种查询算法的影响。
单活动场景下不同数据量及不同持续时间下滑动时间窗口算法和基于Bitmap索引算法的性能比较分别如图1和图2所示。算法运行时间单位为ms，由于2种算法耗时相差过大，取运行时间的对数lg t进行比较。
图1 不同数据量下2种查询算法性能对比
Fig. 1 Performance comparison of two kind of query algorithms with different data size
图2 不同持续时间下2种查询算法性能对比
Fig. 2 Performance comparison of two kind of query algorithms with different duration time
从图1可以看出：随着用户数据量不断增大，2种查询算法的查询耗时都逐渐增加。但Bitmap查询算法耗时约为滑动时间窗口算法耗时的1/100。这是因为普通的滑动窗口算法需要遍历每1个粒度的时间点。例如，当时间粒度为1 s时，用户信息表中的时序数据范围从12:11:00到12:12:00，滑动时间窗口将会进行60次移动。然而，Bitmap索引算法中最外面的循环只需要遍历用户信息表所有开始时间，因此，耗时较少。然而，随着数据量增加，用户信息表的用户时间区间数量也会增加，从而导致2种查询算法的耗时增加。
从图2可以看出：滑动时间窗口算法对活动持续时间的变化不敏感，而Bitmap查询算法的耗时则随着活动持续时间增加而缓慢增加。然而，Bitmap索引算法的查询时间还是比滑动时间窗口算法的查询时间小2个数量级。
4.2 活动冲突场景下2种查询算法性能比较
在实验中，活动持续时间窗口和查询时间范围固定，仅逐步增加活动数量来探究2种算法执行1次查询所需的运行时间。不同活动数量下2种查询算法的性能对比如图3所示。从图3可以看出：随着活动数量不断增大，Bitmap查询算法的查询耗时缓慢增加，而滑动时间窗口查询算法的查询时间则在某个活动数量后急剧增加。最终，Bitmap查询算法的查询耗时比普通的滑动时间窗口算法的查询耗时快近2个数量级。当活动数量较少时，2种算法的运行耗时都很短并且很接近，滑动时间窗口算法的耗时比Bitmap查询算法的要少，这是因为此时冲突时间组合部分的耗时会随着活动数量不断增加而增加。滑动时间窗口算法在冲突组合部分得到的候选时间要比Bitmap查询的算法更多，因此，候选区间匹配的次数也更多，这会增加耗时。
图3 不同活动数量下2种查询算法的性能对比
Fig. 3 Performance comparison of two kind of algorithms with different numbers of activities
当活动数量固定为3个时，在不同活动持续时间下，2种查询算法的耗时比较如图4所示。从图4可以看出：当活动持续时间不断增加时，Bitmap查询算法的运行耗时一直维持在很小的范围内。而在活动持续时间较短时，滑动时间窗口算法耗时较长，随着活动时间增加，滑动时间窗口算法的耗时也不断减少，但还是略多于Bitmap查询算法的耗时。这是因为当活动持续时间比较短时，满足它的有效用户时间区间数量会比活动持续时间长时的要多。而单次活动查询情况下滑动时间窗口的遍历过程是按每个时间粒度来遍历的，由于Bitmap查询算法索引结构逻辑与运算速度较快，且其遍历的是每个有效用户的开始时间点，因此，运行耗时会比滑动时间窗口算法的耗时要少。
图5所示为不同查询时间范围下2种查询算法的性能比较。从图5可以看出：随着时间范围不断扩大， 滑动时间窗口的运行耗时急剧增加，而Bitmap查询算法的运行耗时缓慢增加。当时间范围扩大到一定程度后，Bitmap查询算法的性能明显优于滑动时间窗口算法的性能。查询时间范围扩大会导致有效用户时间区间数量增多，这会增加2种算法的耗时。随着时间范围增大，Bitmap查询算法中遍历Bitmap索引阶段的时间增长速度远小于比滑动时间窗口法的增长速度。
图4 不同活动持续时间下2种查询算法的性能对比
Fig. 4 Performance comparison of two kind of algorithms in different activity duration
图5 不同查询时间范围下2种查询算法的性能对比
Fig. 5 Performance comparison of two kind of algorithms in different query time range
4.3 不同因素对基于Bitmap的活动时间冲突查询算法性能的影响
下面研究不同因素对Bitmap查询算法执行1次查询过程中遍历Bitmap索引阶段和冲突区间组合优化阶段运行时间的影响。在该算法的实际应用中，Bitmap索引的是在线下提前构造的，当接收1个活动冲突查询请求时，Bitmap查询算法再根据构造好的Bitmap索引结构进行查询，因此，在算法的查询过程中不考虑Bitmap索引的构造时间。下面针对活动数量、活动的持续时间和查询时间这3个因素对Bitmap查询算法性能的影响进行分析。
图6所示为活动数量对Bitmap查询算法性能的影响。从图6可以看出：随着活动数量不断增多，Bitmap查询算法的运行耗时也缓慢增加。图6中遍历Bitmap索引的时间先逐渐增加后减少也说明活动数量对Bitmap索引遍历阶段(第1阶段)的影响不大。而当活动数量超过4个时，冲突区间组合优化阶段(第2阶段)耗时急剧增加，说明该阶段对活动数量的变化非常敏感。这是因为，活动数量增多会直接导致冲突区间组合优化的循环次数增加，影响算法的整体查询时间。
图6 活动数量对Bitmap查询算法性能的影响
Fig. 6 Effect of activity number on performance of Bitmap query algorithm
图7所示为不同活动持续时间对Bitmap查询算法性能的影响。从图7可以看出：随着活动持续时间不断增加，算法的运行耗时迅速减少，同时第1阶段的耗时也迅速减少。而第2阶段的运行耗时基本不变。在活动持续时间较短时，由于满足活动持续时间的有效用户时间区间会增加，所以，每个活动得到的候选时间区间个数会增加。而这将导致第2阶段的冲突判定次数增加，从而使查询时间增加。
图8所示为不同查询时间对Bitmap查询算法性能的影响。从图8可以看出：随着查询时间范围不断扩大，Bitmap查询算法的运行耗时也不断增加。第1阶段的耗时也不断增加，而且该阶段在整个查询耗时的占比也不断提高；而第2阶段的运行耗时基本稳定不变。查询时间范围扩大会导致有效用户时间区间数量增大，直接导致第1阶段得到的候选时间区间变多，所以，第2阶段的冲突判定次数也会变多，从而影响查询性能。
图7 不同活动持续时间对Bitmap查询算法性能的影响
Fig. 7 Effects of different activity time duration on performance of Bitmap query algorithms
图8 不同查询时间范围对Bitmap查询算法性能的影响
Fig. 8 Effects of different query time range on performance of Bitmap query algorithms
5 结论
1) 提出基于Bitmap的活动时间冲突查询算法。该方法底层采用Bitmap数据结构对用户区间信息数据构建索引；通过遍历索引并结合冲突区间组合优化来提高查询性能，得到活动时间的全局最优化方案。
2) 利用真实用户数据集，通过控制变量法对Bitmap索引算法和滑动时间窗口算法的运行效率进行比较。在单活动场景下，Bitmap索引算法比滑动时间查询算法约快100倍。
3) 基于Bitmap索引的活动时间冲突解决方法能够更好地满足含冲突的大规模活动组织查询的时效性要求。
参考文献：
[1] 李永峰, 周兴社, 杜可君, 等. 基于时间约束网络的智能活动规划[J]. 计算机科学, 2011, 38(2): 179-183.
LI Yongfeng, ZHOU Xin, DU Kejun, et al. Activity planning based on temporal constraint network[J]. Computer Science, 2011, 38(2): 179-183.
[2] CHAN H L, LAM T W, LEE L K, et al. Continuous monitoring of distributed data streams over a time-based sliding window[J]. Algorithmica, 2012, 62(3/4): 1088-1111.
[3] CHAN C Y, IOANNIDIS Y E. Bitmap index design and evaluation[J]. ACM SIGMOD Record, 1998, 27(2): 355-366.
[4] Chen Zhen, Wen Yuhao, Cao Junwei, et al. A survey of bitmap index compression algorithms for big data[J]. Tsinghua Science and Technology, 2015, 20(1): 100-115.
[5] SESHADRI V, HSIEH K, BOROUM A, et al. Fast bulk bitwise AND and OR in DRAM[J]. IEEE Computer Architecture Letters, 2015, 14(2): 127-131.
[6] Feng Wei, Zhang Chao, Zhang Wei, et al. STREAMCUBE: hierarchical spatio-temporal hashtag clustering for event exploration over the twitter stream[C]//International Conference on Data Engineering (ICDE). Seoul, South Korea: IEEE, 2015: 1561-1572.
[7] FENG Jun, LU Chunyan, WANG Ying, et al. Sketch RR-tree: a spatio-temporal aggregation index for network-constrained moving objects[C]// Proceedings of the 3rd International Conference on Innovative Computing Information and Control(ICICIC). Washington D C, USA: IEEE Computer Society, 2008: 1899-1903.
[8] John A, Sugumaran M, Rajesh R S. Indexing and query processing techniques in spatio-temporal data[J]. ICTACT Journal on Soft Computing, 2016, 6(3): 1198-1217.
[9] KLINE N, SNODGRASS R T. Computing temporal aggregates[C]// Proceedings of the Eleventh International Conference on Data Engineering(ICDE). Washington D C, USA: IEEE Computer Society, 1995: 222-231.
[10] KLINE R N. Aggregation in temporal databases[D]. Tucson, USA :University of Arizona, Department of Computer Science , 1999:213.
[11] KIM J S, KANG S T, KIM M H. On temporal aggregate processing based on time points[J]. Information Processing Letters, 1999, 71(5/6): 213-220.
[12] MOON B, LOPEZ I F V, IMMANUEL V. Efficient algorithms for large-scale temporal aggregation[J]. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(3): 744-759.
[13] LIAO T W. Clustering of time series data—a survey[J]. Pattern Recognition, 2005, 38(11): 1857-1874.
[14] LI Yinan, HE Bingsheng, LUO Qiong, et al. Tree indexing on flash disks[C]// Proceedings of the 25th International Conference on Data Engineering(ICDE).Washington D C, USA: IEEE Computer Society, 2009: 1303-1306.
(编辑 伍锦花)
收稿日期：2018-01-08；修回日期：2018-04-16
基金项目(Foundation item)：国家重点研发计划项目(2016YFB1001403)；国家自然科学基金资助项目(61602411)；浙江省重大科技专项重点工业项目(2015C01034, 2017C01013)；杭州市重大科技创新项目(20152011A03)(Project(2016YFB1001403) supported by the National Key Research & Development Program of China; Project(61602411) supported by the National Natural Science Foundation of China; Projects(2015C01034, 2017C01013) supported by Key Research and Development Program of Zhejiang Province; Project(20152011A03) supported by Major Science and Technology Innovation Program of Hangzhou)
通信作者：沈瑛，副教授，从事时序数据挖掘和可视化、信息安全研究；E-mail:shenying@zjut.edu.cn
摘要：提出1种基于Bitmap的活动时间冲突查询算法。首先对原始数据预处理以构建Bitmap索引结构，然后构建两阶段查询算法：第1阶段遍历Bitmap索引得到满足各个活动持续时间的候选时间区间和候选用户集合，并过滤其中的无效用户、调整候选时间；第2阶段完成冲突区间组合优化，获得不冲突条件下活动组织的全局最优方案；最后，以8 628个用户的50 000条真实数据(时间跨度为1月)进行实验，分为单活动及多活动场景，以用户数量、时间范围、活动数量、持续时间等为测试指标，对比本文算法与滑动时间窗口法测试结果。研究结果表明：本文提出的算法能够满足大规模、涉及时间冲突的活动组织查询的时效性要求，该算法查询速度比滑动时间窗口法的查询速度快，单活动场景下其查询响应速度约为滑动时间窗口法的100倍。
