[發明專利]一種云資源動態定價方法

在審

• 申請號: 201810329219.4
• 申請日: 2018-04-13
• 公開（公告）號: CN108537594A
• 公開（公告）日: 2018-09-14
• 發明（設計）人: 曹斌;王凱;侯晨煜;范菁
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06Q30/02
• 分類號: G06Q30/02
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵;黃美娟

1.一種云資源動態定價方法，包括下列步驟：

步驟1、建立索引結構；

該步驟的目的是在線下為所有用戶上網日志數據構建索引，以方便后續的線上實時定價查詢；本發明設計了一種樹型結構，結合了B-Tree和Segment-Tree的特點；該樹型索引結構的每個結點能存儲一定數量的時間區間，同時每個時間區間有其對應的用戶對該云資源的使用數量；

該樹型索引結構包含兩個參數：b和l；b為最大分支因子，表示內部結點最多能夠存儲b個時間區間，l為最大葉子容量，表示葉子結點最多能夠存儲l個時間區間，它們共同決定了決定了索引的結構；索引結構的詳細介紹如下：

1.1內部結點

一個內部結點可以存儲連續的b個時間區間，并且至少存個；若在某個結點N中我們要表示j個時間間隔N.I₁，N.I₂，N.I₃，……，N.I_j；那么j-1個不同的時刻以升序形式存儲在N中；第i個時刻，表示為N.t_i，表示第i個時間間隔N.I_i的結束時間，同時也表示第(i+1)個時間間隔N.I_i+1的開始時間；此外，N中的每個間隔(例如N.I_i)還與相應的使用量(表示為N.V_i)和指向子節點的指針(指示為N.c_i)關聯；

1.2葉子結點

葉子結點類似內部結點，除了葉子結點中的時間間隔不與指向子結點的指針相關聯即沒有N.c_i；葉子結點最多能夠存儲l個時間區間，并且至少有個時間區間；

1.3根結點

根結點的結構與內部結點相同，除了根節點僅需要至少兩個時間間隔，最多能夠存儲b個時間區間；

1.4結點構建規則

對于任何非葉子結點N，考慮第i個時刻N.t_i，出現在N.c_i指向的子結點中的所有時刻必須嚴格小于N.t_i，出現在N.c_i+1指向的子結點的所有時刻必須嚴格大于N.t_i；

步驟2、用戶數據新增與刪除等操作算法；

2.1新增數據

現有一條用戶使用記錄<I',V'>需要插入，I′表示用戶使用的時間區間，V'表示用戶的使用量；記插入操作為insert(<I',V'>，N)，即在以N為根的樹中插入<I',V'>，具體操作位為：從結點N開始，對于當前結點的時間區間N.I_i，若N.I_i與I'有交集，則再次對N.I_i的子結點調用insert(<I,V>，N.c_i)；若無交集則不做任何操作；當結點N為葉子結點時，若區間N.I_i被I'所包含，則將N.I_i的使用量N.V_i加上V'；若只僅僅有交集，則將要插入的記錄插入到該結點，并加上相應I′的V'的值；

2.2刪除數據

現有一條用戶使用記錄<I',V'>需要刪除，I′表示用戶使用的時間區間，V'表示用戶的使用量；記刪除操作為delete(<I,V>，N)，即在以N為根的樹中刪除<I',V'>，具體操作位為：從結點N開始，對于當前結點的時間區間N.I_i，若N.I_i與I'有交集，則再次對N.I_i的子結點調用delete(<I,V>，N.c_i)；若無交集則不做任何操作；當結點N為葉子結點時，若區間N.I_i被I'所包含，則將N.I_i的使用量N.V_i減去V'；若只僅僅有交集，則將要插入的記錄插入到該結點，并減去相應I′的V'的值；

2.3數據溢出時的操作

當某個結點的數據增加到一定數量，即該結點存儲的時間區間個數大于該結點的最大容量時，需要進行結點的分裂操作；由于數據的插入操作最終在葉子結點完成，所以葉子結點會首先發生溢出，這時對葉子結點進行分裂操作；當葉子結點分裂操作執行完后，可能會導致其父結點的數據溢出，同理對父結點進行分裂操作；

假設某結點N發生了溢出，且當前存儲了n個時間區間，若N為內部結點則n＞b，若N為葉結點，則n＞l，令split(N)為結點N的分裂操作，具體操作如下：

S1)原結點N分裂為N₁和N₂；結點N₁保留原結點N前一半的區間，即保留前個時刻和前個使用量，如果N是內部結點，N₁還保留指針N.c₁到結點N₂保留剩余的區間，即N₂包含時刻從到N.t_n-1以及對應的使用量到N.v_n；如果N是內部結點，N₂還包含指針到N.c_n；

S2)如果結點N是根結點，那么創建一個新的根結點N'為N₁和N₂的父結點，令N'.c₁＝N₁，N'.c₂＝N₂，N'.v₁＝N'.v₂＝0；

S3)如果結點N不是根結點，設N有父結點N'，且N′.c_j＝N，令N'的前j-1個區間不變，從第j+1個區間開始到最后，往右移一位；然后令N′.c_j＝N₁，N′.c_j+1＝N₂，N′.v_j不變，若結點N'溢出，再次調用split(N′)；

步驟3、基于樹型索引結構的動態定價查詢；

為了獲得用戶使用云資源的最優區間，需要進行以下操作：

3.1獲取所有時間區間；

遍歷該樹型索引結構的葉結點，可以得到所有時間區間以及各區間的云資源使用量；遍歷的方法為：從樹的根結點出發，遍歷當前結點的每一個子結點，如果是葉結點就把葉結點的每個區間信息存起來；這時候，得到的區間可能出現這種情況：相鄰區間的使用量相同；這時可以在遍歷葉結點時將當前區間與上一個相鄰區間比較，若滿足兩區間使用量相同則合并為一個，這樣只要遍歷一遍葉結點就能獲得所有區間，并且相鄰區間不會出現使用量相同的情況；

3.2獲得最優區間；

第一步已經得到了所有的時間區間；在所有的區間中快速查找出用戶使用量最大的一個或多個區間，即查找top k個區間，這里用最小堆實現；最小堆的規則是(1)是完全二叉樹(2)每個結點的關鍵字都小于他的兩個子結點；具體步驟如下；

T1)建立最小堆；

首先確定k，k表示要查找使用量排名前k的區間；設步驟3.1獲得的區間個數為n個，現從中取k個，構建最小堆；依次將這k個區間信息插入到最小堆中；插入方法為從根結點開始，依次到左子樹和右子樹；插入的同時要保證每個結點的關鍵字都要比字結點的關鍵字小；這里的關鍵字就是該區間的使用量；例如，當前結點為p，p的父結點為p’，將結點信息插入到p結點時，將p結點的關鍵字與它的父結點p’的關鍵字比較；若p結點的關鍵字大于父結點p’的關鍵字，則將兩者的區間交換；再將p’的關鍵字和p’的父結點p”的關鍵字進行比較，若p’的關鍵字大于p”的關鍵字，則再次交換，以此類推，直到滿足最小堆的條件；當k個區間插入完成后，最小堆建立完成，其中根結點為所有k個結點中關鍵字最小的結點；

T2)更新最小堆；

最小堆建立完成后，用剩余的n-k個區間來更新最小堆；基本方法就是只要遍歷一遍剩下的區間；當讀取一個區間時，將該區間的使用量與根結點的使用量相比較，若是小于根結點的使用量，則拋棄該區間；若大于根結點的使用量，則將根結點的區間信息更新為新的區間信息；同時調整最小堆，使之滿足每個結點的關鍵字都小于左右子結點的關鍵字；

在實際情況中可能遇到多個區間的使用量一樣，這時在更新最小堆時先檢查最小堆中是否有相同使用量的結點，若有則將新的區間信息存到該結點中；若沒有則再按照以上規則更新；

遍歷完所有區間后的最小堆內存放的區間就是top k區間，由于更新最小堆時比根結點小的區間都被拋棄了，所以免去了很大的數據量，這對于提升效率有很大幫助。