[發明專利]基于空間時序數據流應用的Skyline查詢方法

有效

• 申請號: 201611156393.0
• 申請日: 2016-12-14
• 公開（公告）號: CN106708989B
• 公開（公告）日: 2021-03-26
• 發明（設計）人: 季長清;秦靜;謝雨婧;李媛媛
• 申請（專利權）人: 大連大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2457;G06F16/9537;G16H40/67
• 代理公司: 大連智高專利事務所(特殊普通合伙) 21235
• 代理人: 胡景波

1.一種基于空間時序數據流應用的Skyline查詢方法，其特征在于，包括如下步驟：

S1.基于空間時序劃分，按時間窗口將連續的時間序列分割成若干時間片段；

S2.對于每一個時間片段，對其生成網格倒排索引；

S3.將時刻查詢點映射到相應的Skyline網格當中，然后使用全局Skyline格計算方法得到全局Skyline格作為侯選集，接著對侯選集里的網絡節點數據按時間序列作動態Skyline查詢，計算得到有效的全局Skyline結果；

使用云計算技術來并行處理，一個d維數據空間S＝{s₁,s₂,...,s_d}，P是在數據空間S上的數據集合P＝{p₁,p₂,...,p_n}，一個查詢對象ref根據動態支配關系對向量按時間進行動態支配的計算，計算得到Skyline的結果集，數據對象b動態支配a，當且僅當b在所有屬性上都不比a距離ref遠，且至少有一維比a近，如果查詢點是按時間動態變化的，索引與查詢操作也動態按時間流順序進行處理；

設定一個監控時間范圍并設定一個閾值，如果查詢超出了指定的時間范圍，則需要跨多個時間窗，此時對需要跨的時間窗大小進行評估，如果超過閾值，在查詢時則直接查詢失敗，如果時間窗口過小，數據量積累不大的情況，采用批量流緩存的方法，將數據流進行緩存再批量定期發送；如果時間窗口大，且數據量比較大的情況，將數據流按窗口進行拆分，拆分的粒度由實際應用場景決定。

2.如權利要求1所述的基于空間時序數據流應用的Skyline查詢方法，其特征在于，空間時序劃分的具體步驟是：給定一個對象集合P，每個數據點p_k的時間屬性值(t)在一個有界的區間[T_min,T_max]，構造一個均勻的劃分{t₀,...,t_B}，t_i的定義

t_i＝T_min+l×i，l＝(T_max-T_min)/B,i＝0,...,B

形成一個時間片段集合{b₀,...,b_B-1}，每個時間片b_i＝[t_i,t_i+1)，固定長度為l，B為有界區間均勻劃分的個數；每個點的時間屬性值為t映射到時間片b_s(t)∈{b₀,...,b_B-1}，其中s(t)的定義如下：

3.如權利要求1所述的基于空間時序數據流應用的Skyline查詢方法，其特征在于，對于每一個時間片段而言，其網格倒排索引的生成過程如下：假設一個給定的d維空間對象集合P＝{p₁,...,p_n}，P中每個數據點p_k即p_k∈P都有d維屬性{p_k.x₁,...,p_k.x_d}，d維數據空間被劃分等寬的網格，每個單元格的寬度為(δ₁,...,δ_d)；單元格的寬度要根據每維取值情況而定，使得映射后的數據點能均勻地分布其中，掃描同一時間片內的所有點，點p_k映射成網格坐標坐標映射如

4.如權利要求1所述的基于空間時序數據流應用的Skyline查詢方法，其特征在于，步驟S3中，全局Skyline格計算方法是：查詢點q被映射到相應的網格單元c_q當中，整個網格區域就被分成了影響區域和被支配區域，影響區域包含c_q周邊非空的格以及與網格c_q處于同一水平或垂直線上的網格；被支配區域是指被影響區域支配的區域，對于影響區域的查找，采用象限輪詢法，通過逐步擴展，計算查詢點周邊各個象限中非空Skyline格的支配關系，根據支配關系比較得到全局Skyline格和格中的數據點。