[發明專利]一種面向數據廣播的位置相關skyline查詢處理方法

在審

• 申請號: 201510998927.3
• 申請日: 2015-12-25
• 公開（公告）號: CN105608206A
• 公開（公告）日: 2016-05-25
• 發明（設計）人: 肖迎元;申艷;郝剛;劉里;焦旭
• 申請（專利權）人: 天津理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 天津佳盟知識產權代理有限公司 12002
• 代理人: 侯力

1.一種面向數據廣播的位置相關skyline查詢處理方法，其特征在于該方法具體包括：

第1、服務器端(Server端)的廣播信道中數據對象集的有效組織；

第1.1、在廣播服務器端，首先采用現有的Skyline查詢算法將待查詢的多維數據對象 集S劃分成兩部分：Skyline數據對象集S₁和非Skyline數據對象集S₂；然后，將S₂中的數據對 象按位置鄰近關系進行排序；進一步，將排序好的S₂中數據對象劃分成m×k個小的數據段： S₁與S_2，1,S_2，2,…,S_2，m×k-1,S_2，m×k，其中m和k通常取1到10間的整數；最后，將S₁與S_2，1,S_2，2,…, S_2，m×k-1,S_2，m×k按(k,m)交錯模式組織成一個廣播周期，即每k個連續的S_2，i+1,S_2，i+2,…,S_2，i+k之前插入一個完整的S₁，構成一個完整的廣播周期，其中，1≤i≤m×(k—1)；

第1.2、將上述排列好的廣播數據集進一步組織成帶索引的數據段，按照數據段包含數 據對象的不同，帶索引的數據段被分成如下兩類:確定性數據段和待定數據段，其中確定性 數據段包含一個完整的數據對象集S₁，而待定數據段包含數據對象集S₂中m×k個小的數據 段：S_2，1,S_2，2,…,S_2，m×k-1,S_2，m×k中的一個；

第1.2.1、一個確定數據段包括存儲控制信息的header部分和存儲數據對象集S₁的數據 部分，其中，header部分包括如下內容：(1)type字段：用來指示數據段的類型，type取值1代 表是確定數據段，而取0則代表為待定數據段；(2)MBR(S₁)：包含S₁中所有數據對象的最小包 含矩陣；(3)size：表示數據對象的大小；(4)number：表示S₁中包含的數據對象的個數；(5) (k,m)：表示一個確定數據段后鄰接k個連續的待確定數據段，一個廣播周期中包含m個確定 數據段，k和m的具體取值由用戶根據應用的需求來指定，通常取1到10間的整數；(6)next- p：指向該廣播周期中下一個確定數據段的指針；

第1.2.2、類似地，一個待定數據段也包括存儲控制信息的header部分和存儲非 Skyline數據對象的數據部分，header部分包括如下內容：(1)type字段：用來指示數據段的 類型，type取值1代表是確定數據段，而取0則代表為待定數據段；(2)MBR(S_2,i)：包含S_2,i中 所有數據對象的最小包含矩陣；(3)number：表示S_2,i中包含的數據對象的個數；(4)next-p： 指向該廣播周期中下一個確定數據段的指針；(5)near-p：指向該廣播周期中下一個待定數 據段的指針；(6)D-bit：為待定數據段的每個數據對象t設定的一個位，對數據對象t，若其 D-bit為1，則表示在所有待定數據段中至少存在一個數據對象支配t；

第2、客戶端(Client端)的位置相關skyline查詢算法，具體包括如下步驟：

第2.1、當一個Client接收到用戶發起的位置相關skyline查詢請求，將計數器counter 設置為1并通過GPS定位系統獲取Client當前位置Loc；

第2.2、Client調諧、偵聽廣播信道，讀取廣播信道中當前廣播周期中的數據段，當首個 確定數據段出現，Client下載該確定數據段的header信息和全部數據對象(S₁)到本地緩存 中，為鏈表Result-list分配存儲空間；

第2.3、對本地緩存中的每一個數據對象t∈S₁，其位置屬性表示為L(t)，計算Loc和L(t) 間的距離，記為d(Loc,L(t))，將<t,d(Loc,L(t))>按距離d(Loc,L(t))值的升序插入鏈表 Result-list中；

第2.4、對每一個后續的待定數據段S_2,i，執行如下操作，直到counter>m×k；

第2.4.1、counter←counter+1；

第2.4.2、從廣播信道中讀取該待定數據段header信息到本地緩存中；

第2.4.3、若Mindist(Loc,MBR(S_2,i))>Maxdist(Loc,MBR(S₁))，Client切換到休眠模式， 直到下一個待定數據段到來；

其中，Mindist(Loc,MBR(S_2,i))表示Client當前位置Loc到數據對象集S_2,i的最小包含 矩陣MBR(S_2,i)的最小距離，Maxdist(Loc,MBR(S₁))表示Client當前位置Loc到數據對象集S₁的最小包含矩陣MBR(S₁)的最大距離；

第2.4.4、若Mindist(Loc,MBR(S_2,i))>Maxdist(Loc,MBR(S₁))不成立，讀取該待定數據 段的全部數據對象(S_2,i)到本地緩存中，對其中的每一個數據對象u執行位置相關支配關系 檢查，若數據對象u通過位置相關支配關系檢查，則將<u,d(Loc,L(u))>按距離d(Loc,L(u)) 值的升序插入加入結果集Result-list中，若數據對象u不通過位置相關支配關系檢查則將 u從緩存中刪除；

第2.5、將Result-list作為結果集返回給用戶。