一種基于Bitmap的活動時間沖突查詢算法

沈瑛，陳望遠，侯晨煜，徐錦婷，曹斌，董天陽，范菁

?

一種基于Bitmap的活動時間沖突查詢算法

沈瑛，陳望遠，侯晨煜，徐錦婷，曹斌，董天陽，范菁

(浙江工業大學 計算機科學與技術學院，浙江 杭州，310023)

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

查詢服務；活動時間沖突；Bitmap索引；全局最優；時間區間

在旅行、系列會議組織等面向大規模、多用戶、多活動的方案查詢應用場景中，查詢效率依賴于支持時間沖突[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 用戶信息表

2.2 活動時間問題定義

基于上述基本概念，活動時間沖突問題可以定義下述概念。

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

1)O≥D。

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

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

3 基于Bitmap的活動時間沖突查詢算法

為提高活動沖突查詢算法的性能，本文作者以用戶信息表構建Bitmap索引，使得每個有效用戶時間區間的時刻對應1個Bitmap，并設計相應的算法來支持活動沖突查詢。

基于Bitmap的活動時間沖突查詢算法需要2個輸入：一是用戶信息表中的所有用戶以及對應的時間區間信息；二是查詢的時間范圍和根據多個活動的查詢要求給定的多個持續時間。算法的輸出是能使全部活動參與人次最大化的每個活動的最優活動舉辦時間和參與所有活動的總人次。

在查詢之前先通過輸入的用戶信息表數據構造Bitmap索引，基于Bitmap索引的查詢算法可以分為2個階段：第1階段遍歷Bitmap索引得到滿足各個活動持續時間的候選時間區間和候選用戶集合；第2階段對各個活動的候選時間區間進行組合優化，找出組合后所有活動的用戶總人次最大并且時間上互不發生沖突的最優時間區間。

3.1 Bitmap索引結構

本文中需要構建的Bitmap索引由用戶信息表中用戶時間區間的某一時刻以及該時刻對應的Bitmap位串2部分組成。先根據用戶信息表中的用戶輸入順序編制每個用戶在索引比特位串中的位置u。若u為1，則表示當前時刻處于用戶的某個空閑區間內；若用戶無空閑時間，則u為0。根據表1中的用戶信息可以得到Bitmap索引結構，如表2所示(其中t為時間，?)。

表2 Bitmap索引結構表

3.2 Bitmap索引初始構造算法

構建Bitmap索引的過程如下：讀取所有用戶的時間序列數據和持續時間窗口大小，給每個用戶標記用戶位置u，得到用戶位置的映射表，并得到所有用戶區間的開始和結束時刻。給每個時刻建立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個候選用戶集合的元素個數為止，最終得到優化后的候選時間區間c和對應的候選用戶集合c。候選區間和候選用戶集合映射表如表3所示。其中，c為不同的候選區間，c為不同的候選用戶，?。

表3 候選區間和候選用戶集合映射表

3.3.2 沖突區間組合優化算法

第1階段查詢得到多個活動的候選時間區間和對應的候選用戶集合。為了在特定時間范圍內得到所有活動的具體舉辦時間段，并保證參與所有活動的總人次最大化，需要通過第2階段對結果組合優化。

例如，有3個持續時間分別為1，2和3 h的活動，首先需要進行3次獨立查詢，通過遍歷Bitmap索引結構分別得到3個活動對應的候選區間和候選用戶集合，然后對這3個活動對應的候選區間和候選用戶集合進行組合優化，即分別從3個活動對應的候選時間區間集合中選取3個候選區間，在保證所選3個候選時間區間在時間上不發生沖突的情況下，使得3個候選區間對應的候選用戶集合中的用戶數加起來最大。

活動沖突組合優化算法流程如下。

算法1：活動沖突組合優化算法

輸入：每個活動的候選區間和候選用戶集合映射表ci(=1, 2, 3, …)，表中每個候選區間對應覆蓋它的候選用戶數量。

輸出：結果映射表op，表中多個不沖突活動的具體舉辦時間對應這些活動的最大的總參與人次。

FORcINc

Iadd(c)

=+Tget(c)

IFax

IF notConflicted(I)

put(I)

ax

op

FORIN

IFget()ax

opput(ax)

RETURNop

其中，為方案中間結果；ax為最大總參與人數；為當前最大總參與人數；c為第個活動的候選時間區間；I為候選活動列表，?。

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進行比較。

1—滑動時間窗口算法；2—Bitmap查詢算法。

1—滑動時間窗口算法；2—Bitmap查詢算法。

從圖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查詢的算法更多，因此，候選區間匹配的次數也更多，這會增加耗時。

1—滑動時間窗口算法；2—Bitmap查詢算法。

當活動數量固定為3個時，在不同活動持續時間下，2種查詢算法的耗時比較如圖4所示。從圖4可以看出：當活動持續時間不斷增加時，Bitmap查詢算法的運行耗時一直維持在很小的范圍內。而在活動持續時間較短時，滑動時間窗口算法耗時較長，隨著活動時間增加，滑動時間窗口算法的耗時也不斷減少，但還是略多于Bitmap查詢算法的耗時。這是因為當活動持續時間比較短時，滿足它的有效用戶時間區間數量會比活動持續時間長時的要多。而單次活動查詢情況下滑動時間窗口的遍歷過程是按每個時間粒度來遍歷的，由于Bitmap查詢算法索引結構邏輯與運算速度較快，且其遍歷的是每個有效用戶的開始時間點，因此，運行耗時會比滑動時間窗口算法的耗時要少。

圖5所示為不同查詢時間范圍下2種查詢算法的性能比較。從圖5可以看出：隨著時間范圍不斷擴大，滑動時間窗口的運行耗時急劇增加，而Bitmap查詢算法的運行耗時緩慢增加。當時間范圍擴大到一定程度后，Bitmap查詢算法的性能明顯優于滑動時間窗口算法的性能。查詢時間范圍擴大會導致有效用戶時間區間數量增多，這會增加2種算法的耗時。隨著時間范圍增大，Bitmap查詢算法中遍歷Bitmap索引階段的時間增長速度遠小于比滑動時間窗口法的增長速度。

1—滑動時間窗口算法；2—Bitmap查詢算法。

1—滑動時間窗口算法；2—Bitmap查詢算法。

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查詢算法性能的影響

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

圖7 不同活動持續時間對Bitmap查詢算法性能的影響

圖8 不同查詢時間范圍對Bitmap查詢算法性能的影響

圖8所示為不同查詢時間對Bitmap查詢算法性能的影響。從圖8可以看出：隨著查詢時間范圍不斷擴大，Bitmap查詢算法的運行耗時也不斷增加。第1階段的耗時也不斷增加，而且該階段在整個查詢耗時的占比也不斷提高；而第2階段的運行耗時基本穩定不變。查詢時間范圍擴大會導致有效用戶時間區間數量增大，直接導致第1階段得到的候選時間區間變多，所以，第2階段的沖突判定次數也會變多，從而影響查詢性能。

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 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

國家重點研發計劃項目(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