[發明專利]一種基于位置的移動數據存儲系統

有效

• 申請號: 201811654923.3
• 申請日: 2018-12-29
• 公開（公告）號: CN109815303B
• 公開（公告）日: 2020-10-13
• 發明（設計）人: 廖清;丁燁;漆舒漢;蔣琳;王軒
• 申請（專利權）人: 哈爾濱工業大學（深圳）
• 主分類號: G06F16/29
• 分類號: G06F16/29
• 代理公司: 廣州三環專利商標代理有限公司 44202
• 代理人: 麥小嬋;郝傳鑫

1.一種基于位置的移動數據存儲系統，其特征在于，所述存儲系統包括：副本產生模塊，查詢成本評估模塊，副本選擇模塊；

所述副本產生模塊，根據查詢范圍及存儲系統中的原始數據，生成用于查詢的多個候選副本；

所述查詢成本評估模塊，在預設的負載、存儲預算和輸入查詢范圍情況下，對所述候選副本構成的所有副本集合的查詢成本進行評估；

所述副本選擇模塊，在預設的負載和存儲預算的情況下，設置一個空的副本集合R*；

在存儲預算被用完，或向副本集合R*中添加單個副本但負載成本ρ(W,R*)不再降低之前，遍歷所述副本產生模塊產生的所有副本，并使用下式對單個副本r進行評分，將該次遍歷中評分最高的副本增加到副本集合R*中：

當副本集合R*不在再增加副本時，R*內所有的副本即為副本產生模塊需要產生的副本集合；

其中，ρ(W,R*)為查詢集合W對副本集合R*查詢時所需的成本，ρ(W,R*∪{r})為查詢集合W對向副本集合R*增加副本r查詢時所需的成本，η(r)為副本r的存儲空間。

2.如權利要求1所述的存儲系統，其特征在于：所述存儲系統中的記錄以下面的格式進行存儲：(OID，TIME，LOC，A₁，……，A_m)；

其中，OID為目標ID，TIME為時間戳，LOC是目標ID在某個時間點上所處的位置，A₁……A_m為根據數據庫的應用場景變化的通用屬性。

3.如權利要求2所述的存儲系統，其特征在于：所述存儲系統采用分布式的大數據存儲構架。

4.如權利要求3所述的存儲系統，其特征在于：所述副本的編碼方案相同或不同。

5.如權利要求3或4所述的存儲系統，其特征在于：所述存儲系統可以為：TrajStore、PIST、CloSTridium、SpatialHadoop或SATO中的任意一種。

6.一種如權利要求1-5任一項所述的存儲系統的優化方法，其特征在于：

所述副本選擇模塊，通過以下步驟選擇最優或接近最優的副本集合：

1)設置一個空的副本集合R*；

2)在存儲預算被用完，或向副本集合R*中添加單個副本但負載成本ρ(W,R*)不再降低之前，遍歷所述副本產生模塊產生的所有副本，并使用下式對單個副本r進行評分，將該次遍歷中評分最高的副本增加到副本集合R*中：

3)當副本集合R*不再增加副本時，R*內所有的副本即為副本產生模塊需要產生的副本集合；

其中，ρ(W,R*)為查詢集合W對副本集合R*查詢時所需的成本，ρ(W,R*∪{r})為查詢集合W對向副本集合R*增加副本r查詢時所需的成本，η(r)為副本r的存儲空間。

7.一種如權利要求6所述的優化方法，其特征在于：

所述副本選擇模塊，還可以通過以下步驟選擇最優或接近最優的副本集合：

10)使用下方程組作為副本選擇問題的整數線性規劃方程組：

上式的約束為：

其中，w_i為查詢q_i特定負載情況下的權重值，x_j為表示副本r_j是否在最優副本集合中的副本中的0-1變量，c_ij＝ρ(q_i,r_j)，是指查詢q_i在副本r_j上的查詢成本，y_ij為表示查詢q_i是否需要在副本r_j上進行操作的0-1變量，n為查詢集合W中的查詢的個數，m為副本集合R中副本r的個數，b為存儲系統的存儲預算；

11)將約束放松為x_j≤1和y_ij≥0,并使用MIP求解器求解放松約束后的整數線性規劃方程；

12)舍入步驟11)求解出線性規劃方程的部分解，將其組合成為一個完整的解。