一種基于Bitmap的活動(dòng)時(shí)間沖突查詢算法

沈瑛，陳望遠(yuǎn)，侯晨煜，徐錦婷，曹斌，董天陽(yáng)，范菁

?

一種基于Bitmap的活動(dòng)時(shí)間沖突查詢算法

沈瑛，陳望遠(yuǎn)，侯晨煜，徐錦婷，曹斌，董天陽(yáng)，范菁

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州，310023)

提出1種基于Bitmap的活動(dòng)時(shí)間沖突查詢算法。首先對(duì)原始數(shù)據(jù)預(yù)處理以構(gòu)建Bitmap索引結(jié)構(gòu)，然后構(gòu)建兩階段查詢算法：第1階段遍歷Bitmap索引得到滿足各個(gè)活動(dòng)持續(xù)時(shí)間的候選時(shí)間區(qū)間和候選用戶集合，并過(guò)濾其中的無(wú)效用戶、調(diào)整候選時(shí)間；第2階段完成沖突區(qū)間組合優(yōu)化，獲得不沖突條件下活動(dòng)組織的全局最優(yōu)方案；最后，以8 628個(gè)用戶的50 000條真實(shí)數(shù)據(jù)(時(shí)間跨度為1月)進(jìn)行實(shí)驗(yàn)，分為單活動(dòng)及多活動(dòng)場(chǎng)景，以用戶數(shù)量、時(shí)間范圍、活動(dòng)數(shù)量、持續(xù)時(shí)間等為測(cè)試指標(biāo)，對(duì)比本文算法與滑動(dòng)時(shí)間窗口法測(cè)試結(jié)果。研究結(jié)果表明：本文提出的算法能夠滿足大規(guī)模、涉及時(shí)間沖突的活動(dòng)組織查詢的時(shí)效性要求，該算法查詢速度比滑動(dòng)時(shí)間窗口法的查詢速度快，單活動(dòng)場(chǎng)景下其查詢響應(yīng)速度約為滑動(dòng)時(shí)間窗口法的100倍。

查詢服務(wù)；活動(dòng)時(shí)間沖突；Bitmap索引；全局最優(yōu)；時(shí)間區(qū)間

在旅行、系列會(huì)議組織等面向大規(guī)模、多用戶、多活動(dòng)的方案查詢應(yīng)用場(chǎng)景中，查詢效率依賴于支持時(shí)間沖突[1]協(xié)調(diào)的查詢算法，即給定多個(gè)用戶和對(duì)應(yīng)的空閑時(shí)間區(qū)間，有多個(gè)活動(dòng)要舉辦且每個(gè)活動(dòng)需要持續(xù)一定時(shí)間，查詢時(shí)間上不沖突且參與活動(dòng)總?cè)舜巫疃嗟暮侠砘顒?dòng)組織方案。一般可采用固定滑動(dòng)時(shí)間法[2]，通過(guò)設(shè)置固定的活動(dòng)持續(xù)時(shí)間窗口，然后沿著時(shí)間線逐步獲取每個(gè)時(shí)間區(qū)間及該區(qū)間內(nèi)的用戶，并優(yōu)化每個(gè)活動(dòng)的查詢結(jié)果，得到可行的活動(dòng)時(shí)間組合方案，但這種方法在時(shí)序數(shù)據(jù)量較大時(shí)查詢耗時(shí)較長(zhǎng)。Bitmap索引[3]是數(shù)據(jù)庫(kù)中常用的多維數(shù)據(jù)查詢處理技術(shù)，它將對(duì)象的索引信息采用游程編碼壓縮技術(shù)[4]存儲(chǔ)成一系列二進(jìn)制位向量[5]，具有空間開銷較小、查詢響應(yīng)速度快的優(yōu)勢(shì)。本文作者提出1種基于Bitmap的活動(dòng)時(shí)間沖突查詢算法；首先對(duì)用戶的有效時(shí)間區(qū)間數(shù)據(jù)進(jìn)行預(yù)處理，建立Bitmap索引結(jié)構(gòu)，然后遍歷索引結(jié)構(gòu)，獲取每個(gè)活動(dòng)的候選時(shí)間區(qū)間和對(duì)應(yīng)的候選用戶集合，最后對(duì)查詢結(jié)果進(jìn)行組合優(yōu)化得到無(wú)沖突的活動(dòng)全局最優(yōu)方案，基于真實(shí)的用戶時(shí)間數(shù)據(jù)，評(píng)估不同的影響因素對(duì)查詢算法的影響，驗(yàn)證算法的有效性。

1 相關(guān)工作

活動(dòng)時(shí)間沖突問(wèn)題類似于時(shí)態(tài)數(shù)據(jù)庫(kù)中的時(shí)態(tài)聚集查詢問(wèn)題，主要包括時(shí)態(tài)查詢語(yǔ)言中對(duì)時(shí)態(tài)聚集的支持[6]、時(shí)態(tài)聚集索引[7]、時(shí)態(tài)聚集實(shí)例化、時(shí)態(tài)聚集查詢算法[8]等。其中，時(shí)態(tài)聚集查詢算法非常關(guān)鍵，它涉及時(shí)態(tài)分組的問(wèn)題，必須先把時(shí)間序列劃分為時(shí)間區(qū)間并分組計(jì)算聚集值。

典型的時(shí)態(tài)聚集查詢算法可根據(jù)有、無(wú)索引分為2類。無(wú)索引的算法通過(guò)預(yù)掃描數(shù)據(jù)在內(nèi)存中保存局部結(jié)果[9?11]：有的基于聚集樹求得聚集結(jié)果[9]，但節(jié)點(diǎn)插入時(shí)會(huì)影響算法整體性能；有的算法基于平衡樹[10]的葉節(jié)點(diǎn)存儲(chǔ)聚集結(jié)果，搜索效率和調(diào)整效率較高，但需要元組排序開銷較大；還有些基于并行算法[12]?；跁r(shí)態(tài)索引的算法一般將局部聚集計(jì)算結(jié)果以索引形式存于外存儲(chǔ)器中[13]。

然而，上述時(shí)態(tài)聚集查詢算法都不能直接應(yīng)用于解決活動(dòng)時(shí)間沖突問(wèn)題。這是因?yàn)榛顒?dòng)時(shí)間沖突問(wèn)題的場(chǎng)景與典型時(shí)態(tài)聚集查詢存在查詢目的、約束和處理邏輯上的差異。1) 查詢目的不同。傳統(tǒng)時(shí)態(tài)聚集查詢通常是針對(duì)某一時(shí)刻或時(shí)間區(qū)間的用戶聚合值，但活動(dòng)時(shí)間沖突問(wèn)題需要查詢的是活動(dòng)時(shí)間不發(fā)生沖突時(shí)，總用戶數(shù)最大的時(shí)間區(qū)間。2) 查詢約束不同?；顒?dòng)時(shí)間沖突問(wèn)題的約束為待查詢時(shí)間區(qū)間必須滿足的活動(dòng)持續(xù)時(shí)間和查詢時(shí)間范圍。3) 查詢處理邏輯不同?；顒?dòng)時(shí)間沖突查詢的最佳結(jié)果中的用戶存在時(shí)間區(qū)間必須完全覆蓋待查詢的最優(yōu)時(shí)間區(qū)間，而不僅是有交集。

2 問(wèn)題定義

2.1 數(shù)據(jù)說(shuō)明

1) 原始數(shù)據(jù)集。時(shí)序數(shù)據(jù)是以規(guī)律的時(shí)間順序采集的時(shí)間序列的集合[14]。本文所研究的原始用戶時(shí)序數(shù)據(jù)即為用戶在1個(gè)月內(nèi)的空閑時(shí)間區(qū)間。它的元素是一個(gè)二元組，第1分量為用戶的唯一標(biāo)識(shí)，第2分量為用戶的所有空閑時(shí)間區(qū)間的列表，每個(gè)空閑時(shí)間為從開始時(shí)刻到結(jié)束時(shí)刻的1個(gè)時(shí)間片。

2) 持續(xù)時(shí)間。持續(xù)時(shí)間是由活動(dòng)組織者預(yù)先設(shè)定的舉辦活動(dòng)需要的最短時(shí)長(zhǎng)。若某用戶存在空閑時(shí)間區(qū)間包含某個(gè)活動(dòng)持續(xù)時(shí)間的情形，即該用戶能參加該活動(dòng)，則認(rèn)為用戶對(duì)該活動(dòng)有效；否則為不能參加該活動(dòng)的無(wú)效用戶。

例如某晚會(huì)的持續(xù)時(shí)間設(shè)為2 h，而用戶A在2017?07?07T20:00:00—22:00:00有空，用戶B在2017?07?08T19:30:00—21:00:00有空，那么用戶A是該晚會(huì)的有效用戶之一，用戶B不能參與該晚會(huì)。

3) 時(shí)間范圍。時(shí)間范圍可看作是一個(gè)大的時(shí)間區(qū)間，在活動(dòng)查詢前設(shè)定，是所有要舉辦的活動(dòng)在時(shí)間上的約束。

例如某個(gè)活動(dòng)要求在2017?07?07T09:00:00—21:00:00范圍內(nèi)舉辦，其時(shí)間范圍可描述為[2017?07?07T09:00:00, 2017?07?07T21:00:00]。

4) 預(yù)處理數(shù)據(jù)集。以1個(gè)活動(dòng)的持續(xù)時(shí)間對(duì)用戶時(shí)序數(shù)據(jù)進(jìn)行預(yù)處理后，可以構(gòu)建用戶信息表，如表1所示。用戶信息表存儲(chǔ)所有滿足持續(xù)時(shí)間的有效用戶和對(duì)應(yīng)的有效時(shí)間區(qū)間。

表1 用戶信息表

2.2 活動(dòng)時(shí)間問(wèn)題定義

基于上述基本概念，活動(dòng)時(shí)間沖突問(wèn)題可以定義下述概念。

活動(dòng)時(shí)間沖突問(wèn)題。給定1個(gè)數(shù)據(jù)集，包含了多個(gè)用戶的若干空閑時(shí)段。若有多個(gè)活動(dòng)(活動(dòng)總個(gè)數(shù)≥1)需在某時(shí)間范圍內(nèi)舉辦，則活動(dòng)的持續(xù)時(shí)間D(D＞0，?，={1, 2, 3, …,})及活動(dòng)的最優(yōu)活動(dòng)時(shí)間O(O＞0,?)應(yīng)滿足如下條件：

1)O≥D。

2) 對(duì)任意O,，O與其他O之間不發(fā)生沖突；,?{1, 2, 3, …,}。

3)覆蓋O的活動(dòng)的總參與人次最多。

3 基于Bitmap的活動(dòng)時(shí)間沖突查詢算法

為提高活動(dòng)沖突查詢算法的性能，本文作者以用戶信息表構(gòu)建Bitmap索引，使得每個(gè)有效用戶時(shí)間區(qū)間的時(shí)刻對(duì)應(yīng)1個(gè)Bitmap，并設(shè)計(jì)相應(yīng)的算法來(lái)支持活動(dòng)沖突查詢。

基于Bitmap的活動(dòng)時(shí)間沖突查詢算法需要2個(gè)輸入：一是用戶信息表中的所有用戶以及對(duì)應(yīng)的時(shí)間區(qū)間信息；二是查詢的時(shí)間范圍和根據(jù)多個(gè)活動(dòng)的查詢要求給定的多個(gè)持續(xù)時(shí)間。算法的輸出是能使全部活動(dòng)參與人次最大化的每個(gè)活動(dòng)的最優(yōu)活動(dòng)舉辦時(shí)間和參與所有活動(dòng)的總?cè)舜巍?/p>

在查詢之前先通過(guò)輸入的用戶信息表數(shù)據(jù)構(gòu)造Bitmap索引，基于Bitmap索引的查詢算法可以分為2個(gè)階段：第1階段遍歷Bitmap索引得到滿足各個(gè)活動(dòng)持續(xù)時(shí)間的候選時(shí)間區(qū)間和候選用戶集合；第2階段對(duì)各個(gè)活動(dòng)的候選時(shí)間區(qū)間進(jìn)行組合優(yōu)化，找出組合后所有活動(dòng)的用戶總?cè)舜巫畲蟛⑶視r(shí)間上互不發(fā)生沖突的最優(yōu)時(shí)間區(qū)間。

3.1 Bitmap索引結(jié)構(gòu)

本文中需要構(gòu)建的Bitmap索引由用戶信息表中用戶時(shí)間區(qū)間的某一時(shí)刻以及該時(shí)刻對(duì)應(yīng)的Bitmap位串2部分組成。先根據(jù)用戶信息表中的用戶輸入順序編制每個(gè)用戶在索引比特位串中的位置u。若u為1，則表示當(dāng)前時(shí)刻處于用戶的某個(gè)空閑區(qū)間內(nèi)；若用戶無(wú)空閑時(shí)間，則u為0。根據(jù)表1中的用戶信息可以得到Bitmap索引結(jié)構(gòu)，如表2所示(其中t為時(shí)間，?)。

表2 Bitmap索引結(jié)構(gòu)表

3.2 Bitmap索引初始構(gòu)造算法

構(gòu)建Bitmap索引的過(guò)程如下：讀取所有用戶的時(shí)間序列數(shù)據(jù)和持續(xù)時(shí)間窗口大小，給每個(gè)用戶標(biāo)記用戶位置u，得到用戶位置的映射表，并得到所有用戶區(qū)間的開始和結(jié)束時(shí)刻。給每個(gè)時(shí)刻建立1個(gè)Bitmap位串并賦值，若用戶的有效時(shí)間區(qū)間包含當(dāng)前時(shí)刻，則將位串中該用戶對(duì)應(yīng)的比特位置1，否則置0。最后得到每個(gè)用戶的1個(gè)時(shí)刻對(duì)應(yīng)1個(gè)Bitmap位串的索引映射表。

上面構(gòu)建好的Bitmap索引結(jié)構(gòu)存在存儲(chǔ)空間消耗巨大及索引長(zhǎng)度過(guò)長(zhǎng)的缺點(diǎn)。以50 000條記錄和近萬(wàn)用戶數(shù)為例，構(gòu)建Bitmap索引需要超過(guò)1 G的存儲(chǔ)空間。查詢算法中需要得到其中2個(gè)時(shí)刻對(duì)應(yīng)的Bitmap位串進(jìn)行按位與運(yùn)算，并提取“1”的比特位對(duì)應(yīng)的用戶，加入候選用戶集。如果不進(jìn)行壓縮處理，則需要遍歷近萬(wàn)個(gè)位置和用戶，會(huì)大大降低查詢的時(shí)間效率，因此，很有必要對(duì)上述Bitmap索引結(jié)構(gòu)進(jìn)行壓縮操作。下面將Bitmap位串按游程壓縮，即以連續(xù)相同的比特值和相同位的數(shù)量取代原始子串。

3.3 Bitmap查詢算法

3.3.1 遍歷Bitmap索引獲取中間結(jié)果

遍歷Bitmap索引獲取中間結(jié)果為查詢算法的第1階段，具體又分為3步。

步驟1：獲取候選時(shí)間區(qū)間和候選用戶集合。首先對(duì)所有用戶在線時(shí)間區(qū)間內(nèi)所有起始、結(jié)束時(shí)刻按時(shí)間排序，構(gòu)成時(shí)刻表。遍歷時(shí)刻表，若當(dāng)前時(shí)刻是某用戶在線時(shí)間區(qū)間的起始時(shí)刻，則從這個(gè)起始時(shí)刻往后搜尋第1個(gè)滿足活動(dòng)持續(xù)時(shí)間區(qū)間的終止時(shí)刻，從而以起始時(shí)刻、結(jié)束時(shí)刻構(gòu)成1個(gè)候選時(shí)間區(qū)間。將候選時(shí)間區(qū)間的起始、結(jié)束時(shí)刻對(duì)應(yīng)的用戶位串進(jìn)行壓縮，并2串進(jìn)行按位與運(yùn)算，遍歷結(jié)果串中所有值為1的比特位，提取對(duì)應(yīng)的用戶，加入候選用戶集。

步驟2：過(guò)濾候選用戶集中的無(wú)效用戶。步驟1得到的候選用戶集合中可能存在某些無(wú)效用戶，其空閑時(shí)間區(qū)間不能完全覆蓋候選區(qū)間。本步驟主要過(guò)濾無(wú)效用戶，處理邏輯如下：對(duì)每個(gè)候選用戶設(shè)置1個(gè)初值為0的計(jì)數(shù)器，從頭開始檢查該用戶的所有空閑區(qū)間集合，判斷是否能覆蓋候選區(qū)間的起始時(shí)刻。 1) 若當(dāng)前區(qū)間不能覆蓋候選區(qū)間的起始時(shí)刻，則計(jì)數(shù)器加1，并檢查當(dāng)前區(qū)間是否包含候選區(qū)間的結(jié)束時(shí)刻。若是，則判定該用戶為無(wú)效用戶，保存此時(shí)的計(jì)數(shù)器值，結(jié)束對(duì)該用戶的區(qū)間檢查。若否，則繼續(xù)檢查該用戶的下1個(gè)區(qū)間。2) 若當(dāng)前區(qū)間能覆蓋候選區(qū)間的起始時(shí)刻，則繼續(xù)判斷它是否覆蓋候選區(qū)間的結(jié)束時(shí)刻。若是，則該用戶不是無(wú)效用戶，保存此時(shí)的計(jì)數(shù)器值，結(jié)束對(duì)該用戶區(qū)間集合的遍歷。若否，則該用戶是無(wú)效用戶。

通過(guò)上述過(guò)濾方法，就能夠過(guò)濾掉候選用戶集合中的無(wú)效用戶。

步驟3：調(diào)整候選時(shí)間區(qū)間。當(dāng)完成前2個(gè)步驟后，遍歷排序后的時(shí)刻列表找到起始時(shí)刻后的第2個(gè)結(jié)束時(shí)刻。重復(fù)步驟1和步驟2，得到新的候選區(qū)間及候選用戶集合。比較前后2次的候選用戶集合，若元素個(gè)數(shù)相同，則將初次候選區(qū)間的結(jié)束時(shí)刻替換為新候選區(qū)間的結(jié)束時(shí)刻，然后，繼續(xù)找到時(shí)刻表候選區(qū)間起始時(shí)刻中的第3個(gè)結(jié)束時(shí)刻，繼續(xù)重復(fù)步驟1和步驟2，直到后1個(gè)候選用戶集合的元素個(gè)數(shù)小于前1個(gè)候選用戶集合的元素個(gè)數(shù)為止，最終得到優(yōu)化后的候選時(shí)間區(qū)間c和對(duì)應(yīng)的候選用戶集合c。候選區(qū)間和候選用戶集合映射表如表3所示。其中，c為不同的候選區(qū)間，c為不同的候選用戶，?。

表3 候選區(qū)間和候選用戶集合映射表

3.3.2 沖突區(qū)間組合優(yōu)化算法

第1階段查詢得到多個(gè)活動(dòng)的候選時(shí)間區(qū)間和對(duì)應(yīng)的候選用戶集合。為了在特定時(shí)間范圍內(nèi)得到所有活動(dòng)的具體舉辦時(shí)間段，并保證參與所有活動(dòng)的總?cè)舜巫畲蠡?，需要通過(guò)第2階段對(duì)結(jié)果組合優(yōu)化。

例如，有3個(gè)持續(xù)時(shí)間分別為1，2和3 h的活動(dòng)，首先需要進(jìn)行3次獨(dú)立查詢，通過(guò)遍歷Bitmap索引結(jié)構(gòu)分別得到3個(gè)活動(dòng)對(duì)應(yīng)的候選區(qū)間和候選用戶集合，然后對(duì)這3個(gè)活動(dòng)對(duì)應(yīng)的候選區(qū)間和候選用戶集合進(jìn)行組合優(yōu)化，即分別從3個(gè)活動(dòng)對(duì)應(yīng)的候選時(shí)間區(qū)間集合中選取3個(gè)候選區(qū)間，在保證所選3個(gè)候選時(shí)間區(qū)間在時(shí)間上不發(fā)生沖突的情況下，使得3個(gè)候選區(qū)間對(duì)應(yīng)的候選用戶集合中的用戶數(shù)加起來(lái)最大。

活動(dòng)沖突組合優(yōu)化算法流程如下。

算法1：活動(dòng)沖突組合優(yōu)化算法

輸入：每個(gè)活動(dòng)的候選區(qū)間和候選用戶集合映射表ci(=1, 2, 3, …)，表中每個(gè)候選區(qū)間對(duì)應(yīng)覆蓋它的候選用戶數(shù)量。

輸出：結(jié)果映射表op，表中多個(gè)不沖突活動(dòng)的具體舉辦時(shí)間對(duì)應(yīng)這些活動(dòng)的最大的總參與人次。

FORcINc

Iadd(c)

=+Tget(c)

IFax

IF notConflicted(I)

put(I)

ax

op

FORIN

IFget()ax

opput(ax)

RETURNop

其中，為方案中間結(jié)果；ax為最大總參與人數(shù)；為當(dāng)前最大總參與人數(shù)；c為第個(gè)活動(dòng)的候選時(shí)間區(qū)間；I為候選活動(dòng)列表，?。

4 實(shí)驗(yàn)評(píng)估

下面針對(duì)基于Bitmap索引的活動(dòng)沖突查詢算法的性能指標(biāo)進(jìn)行實(shí)驗(yàn)評(píng)估。本實(shí)驗(yàn)的原始數(shù)據(jù)來(lái)自用戶行為日志，包括8 628個(gè)用戶的50 000條時(shí)間序列數(shù)據(jù)(時(shí)間跨度為1個(gè)月)。在實(shí)驗(yàn)過(guò)程中，根據(jù)實(shí)驗(yàn)的影響因素對(duì)原始數(shù)據(jù)進(jìn)行調(diào)整。首先在單個(gè)活動(dòng)查詢請(qǐng)求的情況下，將Bitmap索引算法與傳統(tǒng)的滑動(dòng)時(shí)間窗口方法進(jìn)行比較。采用控制變量的方法即改變其中1個(gè)影響因素并保持其他影響因素不變，對(duì)2種查詢算法進(jìn)行實(shí)驗(yàn)對(duì)比分析。然后，通過(guò)活動(dòng)數(shù)量、活動(dòng)持續(xù)時(shí)間和時(shí)間范圍這幾個(gè)因素來(lái)研究基于Bitmap的活動(dòng)時(shí)間沖突查詢算法在活動(dòng)沖突查詢請(qǐng)求下的性能，探究其在不同影響因素下的效果以及算法在不同階段所消耗的時(shí)間。本實(shí)驗(yàn)硬件如下：2.70 GHz雙核英特爾酷睿i5處理器，8 GB內(nèi)存，128 GB的固態(tài)硬盤，操作系統(tǒng)為MacOS Sierra 10.12.1。

4.1 單活動(dòng)場(chǎng)景下2種查詢算法性能比較

活動(dòng)數(shù)量為1個(gè)是活動(dòng)沖突問(wèn)題的特殊情況，此時(shí)活動(dòng)不發(fā)生沖突。為了比較Bitmap查詢算法與普通的滑動(dòng)時(shí)間窗口算法，本文研究在單活動(dòng)查詢請(qǐng)求情況下不同數(shù)據(jù)量(用戶記錄)和活動(dòng)持續(xù)時(shí)間對(duì)2種查詢算法的影響。

單活動(dòng)場(chǎng)景下不同數(shù)據(jù)量及不同持續(xù)時(shí)間下滑動(dòng)時(shí)間窗口算法和基于Bitmap索引算法的性能比較分別如圖1和圖2所示。算法運(yùn)行時(shí)間單位為ms，由于2種算法耗時(shí)相差過(guò)大，取運(yùn)行時(shí)間的對(duì)數(shù)lg進(jìn)行比較。

1—滑動(dòng)時(shí)間窗口算法；2—Bitmap查詢算法。

1—滑動(dòng)時(shí)間窗口算法；2—Bitmap查詢算法。

從圖1可以看出：隨著用戶數(shù)據(jù)量不斷增大，2種查詢算法的查詢耗時(shí)都逐漸增加。但Bitmap查詢算法耗時(shí)約為滑動(dòng)時(shí)間窗口算法耗時(shí)的1/100。這是因?yàn)槠胀ǖ幕瑒?dòng)窗口算法需要遍歷每1個(gè)粒度的時(shí)間點(diǎn)。例如，當(dāng)時(shí)間粒度為1 s時(shí)，用戶信息表中的時(shí)序數(shù)據(jù)范圍從12:11:00到12:12:00，滑動(dòng)時(shí)間窗口將會(huì)進(jìn)行60次移動(dòng)。然而，Bitmap索引算法中最外面的循環(huán)只需要遍歷用戶信息表所有開始時(shí)間，因此，耗時(shí)較少。然而，隨著數(shù)據(jù)量增加，用戶信息表的用戶時(shí)間區(qū)間數(shù)量也會(huì)增加，從而導(dǎo)致2種查詢算法的耗時(shí)增加。

從圖2可以看出：滑動(dòng)時(shí)間窗口算法對(duì)活動(dòng)持續(xù)時(shí)間的變化不敏感，而Bitmap查詢算法的耗時(shí)則隨著活動(dòng)持續(xù)時(shí)間增加而緩慢增加。然而，Bitmap索引算法的查詢時(shí)間還是比滑動(dòng)時(shí)間窗口算法的查詢時(shí)間小2個(gè)數(shù)量級(jí)。

4.2 活動(dòng)沖突場(chǎng)景下2種查詢算法性能比較

在實(shí)驗(yàn)中，活動(dòng)持續(xù)時(shí)間窗口和查詢時(shí)間范圍固定，僅逐步增加活動(dòng)數(shù)量來(lái)探究2種算法執(zhí)行1次查詢所需的運(yùn)行時(shí)間。不同活動(dòng)數(shù)量下2種查詢算法的性能對(duì)比如圖3所示。從圖3可以看出：隨著活動(dòng)數(shù)量不斷增大，Bitmap查詢算法的查詢耗時(shí)緩慢增加，而滑動(dòng)時(shí)間窗口查詢算法的查詢時(shí)間則在某個(gè)活動(dòng)數(shù)量后急劇增加。最終，Bitmap查詢算法的查詢耗時(shí)比普通的滑動(dòng)時(shí)間窗口算法的查詢耗時(shí)快近2個(gè)數(shù)量級(jí)。當(dāng)活動(dòng)數(shù)量較少時(shí)，2種算法的運(yùn)行耗時(shí)都很短并且很接近，滑動(dòng)時(shí)間窗口算法的耗時(shí)比Bitmap查詢算法的要少，這是因?yàn)榇藭r(shí)沖突時(shí)間組合部分的耗時(shí)會(huì)隨著活動(dòng)數(shù)量不斷增加而增加?；瑒?dòng)時(shí)間窗口算法在沖突組合部分得到的候選時(shí)間要比Bitmap查詢的算法更多，因此，候選區(qū)間匹配的次數(shù)也更多，這會(huì)增加耗時(shí)。

1—滑動(dòng)時(shí)間窗口算法；2—Bitmap查詢算法。

當(dāng)活動(dòng)數(shù)量固定為3個(gè)時(shí)，在不同活動(dòng)持續(xù)時(shí)間下，2種查詢算法的耗時(shí)比較如圖4所示。從圖4可以看出：當(dāng)活動(dòng)持續(xù)時(shí)間不斷增加時(shí)，Bitmap查詢算法的運(yùn)行耗時(shí)一直維持在很小的范圍內(nèi)。而在活動(dòng)持續(xù)時(shí)間較短時(shí)，滑動(dòng)時(shí)間窗口算法耗時(shí)較長(zhǎng)，隨著活動(dòng)時(shí)間增加，滑動(dòng)時(shí)間窗口算法的耗時(shí)也不斷減少，但還是略多于Bitmap查詢算法的耗時(shí)。這是因?yàn)楫?dāng)活動(dòng)持續(xù)時(shí)間比較短時(shí)，滿足它的有效用戶時(shí)間區(qū)間數(shù)量會(huì)比活動(dòng)持續(xù)時(shí)間長(zhǎng)時(shí)的要多。而單次活動(dòng)查詢情況下滑動(dòng)時(shí)間窗口的遍歷過(guò)程是按每個(gè)時(shí)間粒度來(lái)遍歷的，由于Bitmap查詢算法索引結(jié)構(gòu)邏輯與運(yùn)算速度較快，且其遍歷的是每個(gè)有效用戶的開始時(shí)間點(diǎn)，因此，運(yùn)行耗時(shí)會(huì)比滑動(dòng)時(shí)間窗口算法的耗時(shí)要少。

圖5所示為不同查詢時(shí)間范圍下2種查詢算法的性能比較。從圖5可以看出：隨著時(shí)間范圍不斷擴(kuò)大，滑動(dòng)時(shí)間窗口的運(yùn)行耗時(shí)急劇增加，而Bitmap查詢算法的運(yùn)行耗時(shí)緩慢增加。當(dāng)時(shí)間范圍擴(kuò)大到一定程度后，Bitmap查詢算法的性能明顯優(yōu)于滑動(dòng)時(shí)間窗口算法的性能。查詢時(shí)間范圍擴(kuò)大會(huì)導(dǎo)致有效用戶時(shí)間區(qū)間數(shù)量增多，這會(huì)增加2種算法的耗時(shí)。隨著時(shí)間范圍增大，Bitmap查詢算法中遍歷Bitmap索引階段的時(shí)間增長(zhǎng)速度遠(yuǎn)小于比滑動(dòng)時(shí)間窗口法的增長(zhǎng)速度。

1—滑動(dòng)時(shí)間窗口算法；2—Bitmap查詢算法。

1—滑動(dòng)時(shí)間窗口算法；2—Bitmap查詢算法。

4.3 不同因素對(duì)基于Bitmap的活動(dòng)時(shí)間沖突查詢算法性能的影響

下面研究不同因素對(duì)Bitmap查詢算法執(zhí)行1次查詢過(guò)程中遍歷Bitmap索引階段和沖突區(qū)間組合優(yōu)化階段運(yùn)行時(shí)間的影響。在該算法的實(shí)際應(yīng)用中，Bitmap索引的是在線下提前構(gòu)造的，當(dāng)接收1個(gè)活動(dòng)沖突查詢請(qǐng)求時(shí)，Bitmap查詢算法再根據(jù)構(gòu)造好的Bitmap索引結(jié)構(gòu)進(jìn)行查詢，因此，在算法的查詢過(guò)程中不考慮Bitmap索引的構(gòu)造時(shí)間。下面針對(duì)活動(dòng)數(shù)量、活動(dòng)的持續(xù)時(shí)間和查詢時(shí)間這3個(gè)因素對(duì)Bitmap查詢算法性能的影響進(jìn)行分析。

圖6所示為活動(dòng)數(shù)量對(duì)Bitmap查詢算法性能的影響。從圖6可以看出：隨著活動(dòng)數(shù)量不斷增多，Bitmap查詢算法的運(yùn)行耗時(shí)也緩慢增加。圖6中遍歷Bitmap索引的時(shí)間先逐漸增加后減少也說(shuō)明活動(dòng)數(shù)量對(duì)Bitmap索引遍歷階段(第1階段)的影響不大。而當(dāng)活動(dòng)數(shù)量超過(guò)4個(gè)時(shí)，沖突區(qū)間組合優(yōu)化階段(第2階段)耗時(shí)急劇增加，說(shuō)明該階段對(duì)活動(dòng)數(shù)量的變化非常敏感。這是因?yàn)?，活?dòng)數(shù)量增多會(huì)直接導(dǎo)致沖突區(qū)間組合優(yōu)化的循環(huán)次數(shù)增加，影響算法的整體查詢時(shí)間。

圖6 活動(dòng)數(shù)量對(duì)Bitmap查詢算法性能的影響

圖7所示為不同活動(dòng)持續(xù)時(shí)間對(duì)Bitmap查詢算法性能的影響。從圖7可以看出：隨著活動(dòng)持續(xù)時(shí)間不斷增加，算法的運(yùn)行耗時(shí)迅速減少，同時(shí)第1階段的耗時(shí)也迅速減少。而第2階段的運(yùn)行耗時(shí)基本不變。在活動(dòng)持續(xù)時(shí)間較短時(shí)，由于滿足活動(dòng)持續(xù)時(shí)間的有效用戶時(shí)間區(qū)間會(huì)增加，所以，每個(gè)活動(dòng)得到的候選時(shí)間區(qū)間個(gè)數(shù)會(huì)增加。而這將導(dǎo)致第2階段的沖突判定次數(shù)增加，從而使查詢時(shí)間增加。

圖7 不同活動(dòng)持續(xù)時(shí)間對(duì)Bitmap查詢算法性能的影響

圖8 不同查詢時(shí)間范圍對(duì)Bitmap查詢算法性能的影響

圖8所示為不同查詢時(shí)間對(duì)Bitmap查詢算法性能的影響。從圖8可以看出：隨著查詢時(shí)間范圍不斷擴(kuò)大，Bitmap查詢算法的運(yùn)行耗時(shí)也不斷增加。第1階段的耗時(shí)也不斷增加，而且該階段在整個(gè)查詢耗時(shí)的占比也不斷提高；而第2階段的運(yùn)行耗時(shí)基本穩(wěn)定不變。查詢時(shí)間范圍擴(kuò)大會(huì)導(dǎo)致有效用戶時(shí)間區(qū)間數(shù)量增大，直接導(dǎo)致第1階段得到的候選時(shí)間區(qū)間變多，所以，第2階段的沖突判定次數(shù)也會(huì)變多，從而影響查詢性能。

5 結(jié)論

1) 提出基于Bitmap的活動(dòng)時(shí)間沖突查詢算法。該方法底層采用Bitmap數(shù)據(jù)結(jié)構(gòu)對(duì)用戶區(qū)間信息數(shù)據(jù)構(gòu)建索引；通過(guò)遍歷索引并結(jié)合沖突區(qū)間組合優(yōu)化來(lái)提高查詢性能，得到活動(dòng)時(shí)間的全局最優(yōu)化方案。

2) 利用真實(shí)用戶數(shù)據(jù)集，通過(guò)控制變量法對(duì)Bitmap索引算法和滑動(dòng)時(shí)間窗口算法的運(yùn)行效率進(jìn)行比較。在單活動(dòng)場(chǎng)景下，Bitmap索引算法比滑動(dòng)時(shí)間查詢算法約快100倍。

3) 基于Bitmap索引的活動(dòng)時(shí)間沖突解決方法能夠更好地滿足含沖突的大規(guī)?；顒?dòng)組織查詢的時(shí)效性要求。

[1] 李永峰, 周興社, 杜可君, 等. 基于時(shí)間約束網(wǎng)絡(luò)的智能活動(dòng)規(guī)劃[J]. 計(jì)算機(jī)科學(xué), 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 onData 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.

(編輯 伍錦花)

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)

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.

query service; activity time conflict; Bitmap index; global optimization; time interval

10.11817/j.issn.1672-7207.2018.11.014

TP391.1

A

1672?7207(2018)11?2738?07

2018?01?08；

2018?04?16

國(guó)家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(2016YFB1001403)；國(guó)家自然科學(xué)基金資助項(xiàng)目(61602411)；浙江省重大科技專項(xiàng)重點(diǎn)工業(yè)項(xiàng)目(2015C01034, 2017C01013)；杭州市重大科技創(chuàng)新項(xiàng)目(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)

沈瑛，副教授，從事時(shí)序數(shù)據(jù)挖掘和可視化、信息安全研究；E-mail: shenying@zjut.edu.cn