[發明專利]一種面向精準廣告投放的時間聚合查詢方法

在審

• 申請號: 201711338950.5
• 申請日: 2017-12-14
• 公開（公告）號: CN108090171A
• 公開（公告）日: 2018-05-29
• 發明（設計）人: 曹斌;陳望遠;侯晨煜;沈瑛
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06Q30/02
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵;黃美娟

1.一種面向精準廣告投放的時間聚合查詢方法，包括如下步驟：

步驟1.建立bitmap索引結構

首先通過輸入所有用戶的在線區間數據和廣告投放時長，給每個用戶標記一個用戶序號，并得到所有用戶區間的開始時刻和結束時刻集合；給每個時刻分配一個bitmap，判斷每一個用戶的在線時間區間是否包含該時刻，如果該用戶的某一在線時間區間能夠覆蓋該時刻，那么就把該用戶的序號位置上的bit值記為true，如果不包含，則記為false；關于bitmap索引結構的詳細描述如下：

表1列舉了索引結構構建過程中使用的符號，如下所示：

符號意義Time某一用戶的在線區間的開始時刻或者結束時刻Bitmap某一時刻對應的bitmapi]]>某一bitmap的第i個bit值i]]>第i個用戶i.I_j]]>第i個用戶的第j個在線時間區間

表1

1.1建立所有時刻集合：

所有時刻集合包含了所有用戶在線時間區間的I.start和I.end.并且集合中的每個時刻有且只有一個；這樣可以避免在給每個時刻構建bitmap索引時，發生重復構建，造成構建索引結構效率底下的情況；

1.2建立用戶序號

用戶序號主要用來作為bitmap上每個bit的位置；某一時刻的bitmap的下標對應的bit值表示該序號位置上的用戶是否存在某個在線時間區間包含這一時刻；存在則記為true，不存在則記為false；

步驟2.壓縮bitmap索引結構

上一個步驟中構建好的bitmap索引結構存在如下缺點；(1)存儲空間消耗巨大，對50000條用戶在線時間記錄構建bitmap索引所消耗的存儲空間大概是1個G以上；(2)會拖慢接下去的查詢算法的時間；查詢算法中需要得到其中兩個時刻的bitmap做按位與(&)操作的結果resBitMap；并取出resBitMap中bit值為true的bit位置上的用戶，加入候選用戶集；如果不做壓縮操作，則需要對resBitMap的上萬個bit做一次遍歷，而這樣會大大降低查詢的時間效率；

基于此，很有必要對步驟1中構建好的bitmap索引結構進行步驟2的壓縮bitmap索引結構操作；在壓縮過程中，把bitmap中的連續bit值相同的部分作為一個壓縮單元，每個壓縮單元由bit值和bit值的數量構成；關于壓縮bitmap索引結構的詳細描述如下表所示：

表2列舉了壓縮bitmap索引結構過程中使用的符號，如下所示：

符號意義Time某一用戶的在線區間的開始時刻或者結束時刻CompBitmap某一時刻對應的壓縮后的bitmapi]]>CompBitmap中的第i個壓縮單元i.bit]]>第i個壓縮單元的bit值i.count]]>第i個壓縮單元的bit值的數量

表2

步驟3.查詢

表3列舉了查詢步驟中使用的符號，如下所示：

表3

為了精準確定最佳廣告時間段，進行以下四個步驟的操作：

3.1獲取候選時間區間和候選用戶集合

這一步中，首先對包含所有用戶在線時間區間的開始時刻和終止時刻集合allTimeArray按時間順序，從小到大進行排序Time1、Time2、…、Timen；再對排好序的所有時刻sortedTimeArray進行遍歷，當遍歷到的時刻是某用戶時間區間的開始時刻startTime時，從這個開始時刻startTime往后找到滿足最小廣告持續時間duration的第一個時刻afterTime；

那么候選時間區間就是I＝[startTime,afterTime],對這兩個時刻對應的CompBitMap做壓縮與操作，得到與操作的結果resBitMap；最后遍歷resBitMap的每一個bit值，找到bit值為true用戶，將其加入候選用戶集合preUserSet；

3.2過濾候選用戶集合中的假用戶

當完成第一個步驟后，需要通過計算來判斷候選用戶集合preUserSet中每個用戶是否有區間完全覆蓋候選區間I，如果其中的某個用戶沒有區間能夠完全覆蓋候選區間I＝[startTime,afterTime],那么這個用戶就是假用戶fakeUser,需要從候選用戶集合preUserSet中把它過濾掉；

這一步中的過濾方法是：

首先給候選用戶集合preUserSet中的每一個用戶添加一個index變量,并把它初始化為0；對每一個用戶的區間集合intervals，從索引號為index的區間userInterval開始，判斷它是否能覆蓋I.startTime，(1)若userInterval不能覆蓋I.startTime，index計數加一，并判斷userInterval是否整個都在I.afterTime的后面；若是，則該用戶是假用戶，改變User.index＝index，然后結束對該用戶的區間集合的遍歷；若否，繼續對該用戶的下一個userInterval進行判斷；(2)若userInterval能覆蓋I.startTime,繼續判斷它能否覆蓋I.afterTime；若能，則該用戶是真用戶,改變User.index＝index，結束對該用戶的區間集合的遍歷；若不能，則該用戶是假用戶；

通過上述過濾方法，就能夠過濾掉候選用戶集合preUserSet中的假用戶；

3.3優化候選時間區間

當完成前兩個步驟后，接下去遍歷找到sortedTimeArray中startTime后的第二個時刻afterTime2；重復步驟一和步驟二的計算，再次得到[startTime,afterTime2]的候選用戶集合folUserSet；

比較folUserSet和preUserSet；如果folUserSet.size＝preUserSet.size,那么將I.afterTime1替換成I.afterTime2,然后繼續找到sortedTimeArray中startTime后的第三個時刻afterTime3,重復步驟一和步驟二的運算；直到候選用戶集合folUserSet.size<preUserSet.size；結束比較步驟，確定優化后的時間區間I；

然后再對優化后的時間區間做調整，對那些候選用戶集合preUserSet相同并且存在交集的時間區間I進行區間合并；

由上述步驟可以確定以startTime作為開始時刻的最優區間I和其對應的候選用戶集合preUserSet；

3.4最優方案選擇

通過第三步得到所有候選方案后，再判斷所有方案中的候選用戶集合的用戶數量是否最大，進一步確定最優的廣告投放時間方案；同時也可以根據廣告主的需要，確定前k個在線用戶數量最大的廣告投放時間方案。