利用k-d樹索引改進數據流skyline查詢算法

唐穎峰, 陳世平

1(上海理工大學 管理學院,上海 200093) 2(上海對外貿經貿大學 教務處,上海 201620)

1 引 言

作為一種重要的數據挖掘技術,skyline查詢[3]近來引起了研究者們的廣泛關注.面向數據流的skyline查詢在交通數據的分析中應用廣泛,如基于位置的服務、最佳路線規劃與推薦[4-9]等等.近年來,國內外研究者對數據流上的skyline查詢問題進行了研究,Lin等人[10]最早研究了數據流上的skyline查詢問題,針對數據流中最近的N個元素計算任意最近n(n≤N)個元素的skyline點集合.Tao等人[11]提出了兩種方法(Lazy和Eager)用于維持數據流滑動窗口的skyline,但是算法中組織數據點的R-樹[12]所產生MBR的重疊使得算法的搜索效率低下.Sun等人[13]對Eager算法進行了改進,提出了StreamSubsky算法,算法采用網格索引來組織數據點,提高了數據點的更新效率.此后,研究者們又針對不同的應用場景,從不同角度對面向數據流的skyline查詢問題進行了研究.Tian和Zhang等人[14,15]研究了任意順序隨機增刪的數據流上的skyline查詢;Zhan等人[16]對面向分布式數據流的K-Skyband連續查詢進行了研究;Zhao等人[17]對連續子空間的概率skyline查詢進行了研究;Liu等人[18]對不確定數據流上的概率skyline查詢進行了研究;Guo等人[19]面向數據流的skyline組查詢進行了研究.這些研究所提出的算法均采用網格索引或者R-樹索引.

現有的基于網格索引的算法存在較大不足:算法需要事先確定網格寬度K,算法的性能很大程度上依賴于K的合理取值,而實際應用時往往難以確定適合的初始K值;網格寬度K在算法初始時已經固定,網格大小不會隨到達數據點的分布情況動態變化,使得算法的自適應性和穩定性較差,難以應對數據點分布變化的高速數據流查詢的應用場景,如智能交通系統[1,2]中的數據流等.

本文對現有的面向數據流的skyline增量更新算法進行優化,提出一種基于k-d樹的算法kdStreamSky,以一種新型索引結構k-d樹來組織數據流對象,并針對此結構提出剪枝規則,來實現增量數據點的高效更新.k-d樹的組織無需預先指定空間劃分尺度,索引區域的劃分根據當前數據點的分布情況自動動態調整,以提高算法的自適應性、穩定性和計算效率,使算法適用于數據點分布變化的高速數據流查詢.

2 相關概念

令A1,A2,…,Ad是d個全序集,記全序關系為≤;S=A1×A2×…×Ad是一個d維數據空間,稱A1,A2,…,Ad為空間S的屬性或維;令包含n個數據點的集合D={p1,p2,…,pn},其中任意數據點pi均來自空間S,將pi在屬性Ai上的取值記為pi.ai.

定義1(支配).任意給定兩個數據點p,q∈D:如果對于?Ai∈A,有p.ai≤q.ai;且?Aj∈A,有p.aj

定義2(skyline).集合D中所有不被其他任意數據點所支配的數據點組成的集合稱作D上的skyline集合,若以SK(D)表示skyline集合,則有SK(D)={p∈D|?q∈D:q≮ p}.

定義3(有效數據點).將數據點p到達系統的時間戳記為p.tarr,不妨設p.tarr為整數,由0開始遞增.設一時間窗口大小為W,系統當前時間戳為tn,則當p.tarr∈[tn-W,tn]時,p為有效數據點,否則為過期數據點.

定義4(活動數據點).若有效數據點p滿足條件p.tarr≥q.tarr,其中q∈{q |q∈D,q

定義5(影響時間).設任意活動數據點p∈D,活動數據點集合Q={q |q∈D,q

3 算法的概要設計

3.1 算法數據結構

在kdStreamSky算法中,活動數據點以列表的形式存儲,稱為活動點列表(active point list,簡稱APL),APL中每個點設置標識,標識該數據點當前是否屬于skyline集合;對于用戶提交的查詢請求,將返回APL中當前標識屬于skyline集合的數據點.

kdStreamSky算法沿用文獻[11]中Eager算法中所采用的事件鏈機制.該機制的優點在于,可以在當前窗口上的skyline數據點過期后,直接輸出其“繼任者”而避免計算其排它支配域上的skyline.事件鏈(event list,簡稱EL)是由按時間順序排列的節點構成的列表,事件鏈的節點存儲同一時間發生的若干事件,事件鏈處理函數依次對當前時間戳對應的事件鏈節點中的事件進行處理.事件e可表示為一個三元組e={p,t,o},其中p為事件對應數據點的地址,t為事件發生的時間戳,o為處理事件時要進行的操作方式.算法預先計算數據點p可以加入skyline集合的最早時間或其過期時間t(即影響時間),將p對應事件e加入到事件鏈對應時間t的節點中.事件鏈處理函數根據當前時間點中事件e的操作方式o,將對應數據點p加入skyline集合或將其淘汰.

kdStreamSky算法采用k-d樹對數據點進行索引.k-d樹是一棵滿二叉樹,樹的每個非葉節點代表空間的特定區域,該節點的左右孩子在某一維將該區域分割成兩部分;樹的每個葉節點代表一個數據點.

kdStreamSky算法中k-d樹的節點結構設計如下:

KD_tree

{ KD_tree LeftChild;

KD_tree RightChild;

List IncludedPoints;

Array UpperBound;

Array LowerBound;

Array AreaUpperBound;}

其中,LeftChild和RightChild存儲節點左、右子樹的地址,葉節點左、右子樹為空.IncludedPoints列表存儲當前節點區域中所包含的所有數據點的地址,列表中的數據點地址按照數據點到達的時間戳排序;特別地,當節點為葉節點時,列表中只包含一個數據點的地址.d維向量UpperBound存儲該節點所代表區域中全部數據點的最大屬性值;而LowerBound則存儲該節點所代表區域中全部數據點的最小屬性值.d維向量AreaUpperBound存儲區域分割所產生的該節點對應區域的最大邊界值.

根據k-d樹的構造規則,可以得到如下性質:

性質1.(完備性)k-d樹的任一非葉節點所代表的區域包含其左右孩子中所包含的全部數據點.

性質2.(互斥性)對于k-d樹任意一層,空間內的任意一點p只包含于這一層的其中一個節點.

性質3.(時序性)k-d樹上任意節點Q所包含數據點的最大時間戳不小于其任意一孩子所包含數據點的最大時間戳.

由性質1、性質2可知,完全訪問k-d樹的任意一層節點即可保證空間內的全部數據點均被訪問,且只被訪問一次.因此,采用k-d樹索引數據空間是完備且有效率的.

定理1.對于任意數據點p,k-d樹的任意節點Q,若p

證明:p

由定理1和性質3可以得到訪問及更新k-d樹的剪枝規則1-4.

剪枝規則1.設有新到達數據點p,k-d樹上任一節點Q,滿足p

剪枝規則2.設有新到達數據點p,k-d樹上任一節點Q,滿足p≮ Q.UpperBound,則Q及其子節點均無需從k-d樹上刪除.

剪枝規則3.若新到達數據點p被k-d樹上任一節點Q的屬性值上界支配,則更新p的影響時間為Q中時間戳最大數據點的過期時間.

剪枝規則4.若k-d樹上任一節點Q中數據點的最大時間戳不大于最近更新新到達數據點p影響時間的數據點的時間戳,則Q及其全部子節點都不更新p的影響時間.

綜上所述,算法的數據結構包括三部分:活動點列表APL,事件鏈EL以及k-d樹索引.

3.2 算法的處理流程

算法的總體流程分為三種情況進行相應的處理:

1)當新的數據點p到達時,先以p遍歷k-d樹,利用剪枝規則1和2對k-d樹進行剪枝,將非活動的點從系統中刪除;再利用剪枝規則3和4計算p的影響時間,同時可以得到p是否在skyline集合的標識;根據p的影響時間生成相應事件,并加入事件鏈中;最后將p的地址更新到k-d樹上.

2)當時間戳發生跳變時,調用時間處理函數對事件鏈中的相應事件進行處理.

3)當用戶提交查詢時,將當前時刻APL中當前標識為skyline集合內的數據點返回給用戶.

4 算法的詳細實現

4.1 k-d樹的剪枝

此過程目的是在k-d樹中找出非活動數據點,并將其從系統中刪除.采用深度優先遍歷k-d樹的方式,找到被當前到達數據點p支配的區域,并刪除該區域內的全部數據點.遍歷過程中利用剪枝規則1和2,縮小搜索區域,以提高剪枝效率.k-d樹剪枝算法描述見算法1.

算法1.k-d樹剪枝算法

輸入:剪枝前的k-d樹及當前到達數據點p

輸出:剪枝后的k-d樹

步驟:

由根節點開始深度優先遍歷k-d樹,當前被訪問的節點為Q,其兄弟節點為B,父節點為P;

if p < Q.UpperBound

if p≮Q.LowerBound

繼續訪問Q.LeftChild及Q.RightChild;

if p

若Q為右孩子,則向下更新B對應子樹的

AreaUpperBound為P.AreaUpperBound;

用B替代P節點,并向上遞歸更新P.LowerBound

以及P.IncludedPoints;

刪除Q及其孩子;

刪除Q.IncludedPoints在APL中對應的數據點;

刪除事件鏈中Q.IncludedPoints數據點的對應事件;

if p≮Q.UpperBound

if Q為根節點

return;

else

繼續訪問Q.LeftChild及Q.RightChild;

4.2 計算影響時間

此過程用以計算新到達數據點p的影響時間,以深度優先方式遍歷k-d樹,找出所有支配數據點p的活動數據點中時間戳最大的數據點q,將q的過期時間作為p的影響時間.通過遍歷k-d樹,可以判別數據點p是否屬于skyline,若是,則p的影響時間為其過期時間.遍歷過程中利用剪枝規則3和4,縮小搜索區域,以提高計算.p的影響時間計算算法描述見算法2.

算法2.影響時間計算算法

輸入:當前到達數據點p

輸出:p的影響時間p.teff

步驟:

p.teff=p.tarr+W;

初始化對p的影響時間進行更新的數據點的時間戳t=0;

由根節點開始深度優先遍歷k-d樹,當前被訪問的節點為Q,其兄弟節點為B;

if max(Q.IncludedPoints.tarr)<=t

if Q為根節點或右孩子

return;

else 繼續訪問B;

else

if p

if Q為根節點或右孩子

return;

else 繼續訪問B;

if Q.UpperBound

t=max(Q.IncludedPoints.tarr);

p.teff=t+W;

if Q為根節點或右孩子

return;

else 繼續訪問B;

else

if Q為非葉節點

繼續訪問Q.LeftChild及Q.RightChild;

else

if Q為右孩子

return;

else 繼續訪問B;

4.3 事件鏈更新及事件處理

數據點影響時間計算完成后,生成相應的事件加入到事件鏈的相應位置.設事件為e,e的操作類型e.op分為兩種:ex代表將當前數據點過期操作;pm代表將當前數據點加入skyline集合操作.則時間鏈更新算法描述見算法3.

算法3.事件鏈更新算法

輸入:計算影響時間后的數據點p及更新前的事件鏈 EL

輸出:更新后的事件鏈EL

步驟:

if p.teff>= p.tarr+W

e={p,p.teff,ex};

else

e={p,p.teff,pm};

將事件e加入到EL[p.teffmod W];

當時間戳發生變化時,事件鏈處理過程即被觸發,并對事件鏈中當前時間戳的節點中的事件進行處理.設事件e對應的數據點為e.p,操作類型為e.op,算法描述見算法4.

算法4.事件處理算法

輸入:當前時間戳t,事件鏈EL

輸出:更新后的事件鏈EL

步驟:

while EL[t mod W]非空

從EL[t mod W]中取出事件e;

if e.op==ex

將e.p從APL中刪除;

將e.p從k-d樹中刪除;

if e.op==pm

將e.p在APL的skyline標識為設置為true;

新建一個事件e′={e.p,e.p.tarr+W,ex}加入到EL[e.p.tarr+W mod W]中;

將e從EL中刪除;

4.4 k-d樹更新

新到達數據點p的影響時間計算完成后,要將p更新到k-d樹上.k-d樹更新算法描述見算法5.

算法5.k-d樹更新算法

輸入:更新前的k-d樹及當前到達數據點p,p的各屬性 值記為p.attr

輸出:更新后的k-d樹

步驟:

從根節點深度優先遍歷k-d樹,當前被訪問的節點為Q,其兄弟節點為B,父節點為P;

if Q為空

新建節點Q,將p插入Q.IncludedPoints;

Q.LowerBound=p.attr;

Q.UpperBound=p.attr;

Q.AreaUpperBound=p.attr;

return;

if p

if Q非葉節點

將p插入Q.IncludedPoints;

Q.LowerBound=min(p.attr,Q.LowerBound);

Q.UpperBound=max(p.attr,Q.UpperBound);

繼續訪問Q.LeftChild;

if Q為葉節點

計算p與Q.IncludedPoints中數據點q各屬性的方差,找到方差最大的屬性a作為區域分割屬性;

新建兩個節點M和N;

M.AreaUpperBound=Q.AreaUpperBound;

N.AreaUpperBound=Q.AreaUpperBound;

M.AreaUpperBound.a=min(p.attr.a,q.attr.a);

M.UpperBound= p.attr.a>=q.attr.a? q.attr:p.attr;

M.LowerBound= p.attr.a>=q.attr.a? q.attr:p.attr;

N.UpperBound= p.attr.a<=q.attr.a? q.attr:p.attr;

N.LowerBound= p.attr.a<=q.attr.a? q.attr:p.attr;

M.UpperBound.a=min(p.attr.a,q.attr.a);

N.UpperBound.a=max(p.attr.a,q.attr.a);

將p插入Q.IncludedPoints;

Q.LowerBound=min(p.attr,q.attr);

Q.UpperBound=max(p.attr,q.attr);

Q.LeftChild=M;

Q.RightChild=N;

return;

if p≮Q.AreaUpperBound

if Q非根節點

則繼續訪問B節點;

if Q為根節點

找出p.attr比Q.AreaUpperBound大的屬性集A,計算p.attr與Q.AreaUpperBound在A上的方差,找到方差最大的屬性a作為分割屬性;

新建兩個節點M和N;

M.LowerBound=min(p.attr,Q.LowerBound);

M.UpperBound=max(p.attr,Q.UpperBound);

N.UpperBound= p.attr;

N.LowerBound= p.attr;

M.AreaUpperBound=max(p.attr,

Q.AreaUpperBound);

N.AreaUpperBound= max(p.attr,Q.

AreaUpperBound);

M.LeftChild= Q;

M.RightChild=N;

更新Q子樹在A上除屬性a之外AreaUpperBound為p.attr;

M.IncludedPoints=Q.IncludedPoints;

將p插入M.IncludedPoints及N.IncludedPoints;

return;

5 算法分析

本文將對比分析網格索引和k-d樹索引的訪問復雜度.以一次支配檢測的時間作為單位時間進行時間復雜度分析.

為方便比較,假設網格結構G為d維,每一維劃分為n等分,則G的網格總數為nd.k-d樹則假設為一個標準k-d樹,即從根節點開始向下,每一層順次以空間的一維對當前節點對應空間進行分半劃分,持續劃分直到葉節點總數為nd,此時k-d樹的層數為ln(nd).

在網格索引中,對于一個新到數據點p,若要確定p與已有數據點間的支配關系,需要進行兩部分的支配檢測:網格間的支配檢測和網格內數據點的支配檢測.網格間的支配檢測即是以p所在的網格g與其他網格進行支配檢測,排除與g中數據點可以確定支配關系的網格,找出無法確定支配關系的網格集合G*,其復雜的表示為Cg.網格內數據點的支配檢測即為p與網格集合G*內所包含的所有數據點逐一進行支配檢測,其復雜的表示為Cgp.設網格索引的訪問復雜度為CGI,則可表示為:

CGI=Cg+Cgp

(1)

定理2.設p所在網格g1={a1,a2,…,ad},若任意其他網格g2={b1,b2,…,bd},?i∈{1,2,…,d},使得ai=bi;則g2

∈G*.

由定理2可知,G*中的網格數量為nd-(n-1)d.

在網格索引中,要求出G*,需要用p所在網格與其他網格逐一進行支配檢測,因而Cg=O(nd);而網格內數據點的支配檢測則是用p與G*內的數據點逐一進行支配檢測,設數據點總數為M,則每個網格內的平均數據點數為M/nd,可得Cgp=O(M(nd-(n-1)d)/nd).

對于給定的k-d樹,確定p與已有數據點間的支配關系,也需要進行兩步操作:首先由根節點遍歷k-d樹,排除其中數據點可以與p確定支配關系的分枝,找出無法確定支配關系的葉節點集合L,其復雜的表示為Ct.然后再用p與L中所包含的數據點逐一進行支配檢測,其復雜的表示為Clp.因此給定k-d樹的訪問復雜度CKD可表示為:

CKD=Ct+Clp

(2)

由于給定k-d樹的葉節點數為nd,即給定k-d樹最終將數據空間均等劃分為nd個子空間,每個葉節點代表的子空間與網格結構中的每個網格一一重合,有L=G*,即Clp= Cgp=O(M(nd-(n-1)d)/nd),因此要比較CGI和CKD的大小,只需比較Cg和Ct的大小即可.

在k-d樹索引中,求集合L可以分為兩個過程:首先從根節點以深度優先遍歷k-d樹,標記k-d樹每一層中數據點p所在區域對應的節點;然后自頂向下層次遍歷k-d樹,對于k-d樹的每一層中的節點,以被標記節點對同層其余節點進行支配檢測,相當于k-d樹的每一層節點將空間劃分為一個網格結構,若被檢測節點滿足定理2的條件則保留,否則連同孩子一起刪去,依次遍歷到最底層,被保留的葉節點集合即為L.因此Ct即為檢測每一層滿足定理2條件的節點的時間總和.

設遍歷k-d樹的第i層為對空間第k維的第l次劃分,第i層滿足定理2條件的節點數量為Ni,則可將空間的各維分為兩類:

1)第l次未劃分的維,其數量為d-k;

2)第l次已劃分的維,其數量為k;

由此可得:

Ni=2(l-1)(d-k)*2lk-(2(l-1)-1)(d-k)*(2l-1)k

≤2ld-(2l-1)d≈d*2l(d-1)

(3)

而根據給定k-d樹的劃分規則,有:

l=?i/d」≤i/d

(4)

將式(4)代入式(3)可得:

(5)

設遍歷到最后一層所訪問的總節點數為N,則有:

(6)

將式(5)代入式(6)可得:

N≤d2lnn*n(d-1)

(7)

由式(7)可知,當滿足式(8)條件時有N≤nd,即有Ct≤Cg,進而有CKD≤CGI.而若將d2看做常數,當n充分大時,顯然總能找到一個數n′,使得當n≥n′時,滿足式(8)條件.因此可得,當n較大時,k-d樹索引在skyline計算問題上的訪問效率優于網格索引.

d2lnn≤n

(8)

以d=2為例,當n=256時,網格索引中Cg=2562=65536;而根據式(3)及式(6)計算可得,k-d樹索引中Ct=1769,k-d樹索引的訪問效率比網格索引高出近37倍.

6 實驗及結果分析

為了保證計算結果的準確性,本文討論的算法采取同步響應的方式,即每次查詢提交后,系統需將緩存中當前時間窗口內的數據點全部處理后,再響應查詢請求,返回計算結果.因此,新到達數據點的更新時間直接影響查詢響應時間,而查詢響應時間也是反映實時系統性能的重要指標.因此本文采用查詢響應時間作為標準來衡量算法的實際性能.

實驗環境為Intel Core i5 2.8GHz處理器,2GB內存,260GB磁盤空間,操作系統采用CentOS6.2.在上述實驗環境中對Eager、StreamSubsky和kdStreamSky三種算法進行了實現,并對實驗測定結果進行對比分析.

實驗數據分別采用標準數據和實際交通數據進行.標準數據采用文獻[3]中的標準數據生成工具生成.實際交通數據則采用北京市的真實道路網數據*數據來源: http://www.datatang.com/data/45422,共433391條路段信息,頂點數共計171504個.在此道路網上隨機生成30000個固定對象,并設置一個移動對象沿道路網移動,記錄移動對象500m半徑范圍內的固定對象與其的路徑長度以及其他隨機產生的3維非空間屬性值,形成一個4維點集數據流.由于移動對象半徑范圍內的固定對象數會隨著移動對象的移動而變化,因此對應數據流呈現出疏密分布隨時間變化的特點.

實驗中,標準數據流的流速保持恒定;實際交通數據流中,移動對象的移動速度保持恒定;查詢響應時間取相同條件下10次測定結果的平均值;由于StreamSubsky算法的性能與網格寬度相關,本文實驗中按照文獻[13]中的最優化規則對其網格寬度進行設置.

對于標準數據,在不同的數據維度、數據規模及數據流速條件下,對三種算法的查詢響應時間進行了測定.

圖1所示為三種算法在不同數據維度下的查詢響應時間,其中數據規模為300K,數據流速為300點/秒.由于采用了效率較高的索引結構,StreamSubsky和kdStreamSky相比Eager,在不同數據維度下的性能都有著明顯的優勢,kdStreamSky比StreamSubsky在低維度上有更好的表現;隨著數據維度的增加,三種算法的性能逐漸接近且趨于穩定,這是因為在數據規模恒定條件下,當數據維度增加到一定程度,三種算法的索引結構都會逐漸失效,支配檢測時間接近于逐點檢測的時間.

圖1 三種算法在不同數據維度下的查詢響應時間Fig.1 Query response time with different dimesion

圖2所示為三種算法在不同數據規模下的查詢響應時間,其中數據維度d=4,數據流速為300點/秒.三種算法中,StreamSubsky和kdStreamSky的在不同數據規模下均比Eager存在較大的性能優勢;而相比StreamSubsky,kdStreamSky在數據規模較小時,由于需要花費更多的時間維護k-d樹索引,因而性能略差,但隨著數據規模的增大,其查詢響應時間的增長相對平緩,表現出較為明顯的優勢.

圖2 三種算法在不同數據規模下的查詢響應時間Fig.2 Query response time with different cardinality

圖3所示為三種算法在不同數據流速下的查詢響應時間,其中數據維度d=4,數據規模為300K.三種算法中,StreamSubsky和kdStreamSky同樣比Eager具有較大優勢.kdStreamSky比StreamSubsky在不同數據流速下均有更好的表現,且隨著數據流速增大,kdStreamSky的優勢更明顯.

圖3 三種算法在不同數據流速下的查詢響應時間Fig.3 Query response time with different data flow velocity

對于實際交通數據,在移動對象保持在5m/s的條件下每隔5s進行一次查詢,對三種算法的查詢響應時間進行測定;在移動對象不同的移動速度條件下,對三種算法的平均查詢響應時間進行了測定.

圖4所示為三種算法在移動對象保持恒定移動速度下的查詢響應時間.三種算法中,kdStreamSky算法的查詢響應時間優于另外兩種算法;StreamSubsky算法的響應時間呈現出較大的波動,這主要是因為StreamSubsky算法的索引采用固定的網格寬度,其查詢性能受到數據點疏密分布變化的影響較大,相比之下kdStreamSky則呈現出較好的自適應性,查詢響應時間基本保持穩定.

圖5所示為三種算法在移動對象不同的移動速度條件下的平均查詢響應時間.由于時間窗口內的數據點數量隨著移動對象的移動速度增大而增加, 因此三種算法的查詢響應時間均隨著移動對象的移動速度增大而增加.kdStreamSky算法相比另外兩種算法均保持較大的優勢.

圖4 三種算法在移動對象恒定移動時的查詢響應時間Fig.4 Query response time when main object keep uniform

圖5 三種算法在移動對象不同移動速度下的平均查詢響應時間Fig.5 Average query response time with different object moving speed

綜上所述,相比StreamSubsky算法和Eager算法,kdStreamSky算法在標準數據環境有著較好的性能表現;在實際交通數據環境下則呈現出良好的自適應性以及明顯的性能優勢,更適用于疏密分布變化較大的交通數據流skyline查詢任務.

7 結 論

本文提出一種基于k-d樹的數據流skyline增量更新算法kdStreamSky.該方法通過事件鏈機制對增量數據點的狀態轉換進行預計算,通過事件的處理對數據點的狀態進行更新;采用一種新型的索引結構k-d樹對數據點進行索引,該索引無需指定任何初始參數,且能夠根據數據流中數據點分布的變化自適應調整;并在k-d樹結構上提出多個剪枝規則來縮小搜索域,提高了搜索效率;算法能夠快速響應用戶的查詢請求,將數據流在任意時間窗口內的skyline點集合返回給用戶.kdStreamSky算法在較大規模及高速數據流有著較好的性能表現,能夠更好的適應疏密分布變化的高速數據流分析,適用于智能交通系統中數據流skyline查詢任務.

kdStreamSky算法與其他同類基于索引結構的算法在處理高維數據時均會遇到索引失效的情況,因此單機處理能力有限,算法并行化是必然趨勢;同時,智能交通系統中數據流也多為分布式數據流,因此下一步的工作是將算法擴展分布式數據流環境,并將算法進行并行擴展,以適應智能交通系統中數據流實時分析的需求.

[1] Ichiro Masaki.A brief history of ITS[R].USA:Massachusetts Institute of Technology,1999.

[2] Wang Guo-feng,Song Peng-fei,Zhang Yun-ling.Review on development status and future of intelligent transportion system[J].Highway,2012,5(5):217-222.

[3] Borzsonyi S,Kossmann D,Stocker K.The skyline operator[C].Proceedings of the 17th International Conference on Data Engineering,2001:421-430

[4] Fu X,Miao X,Xu J,et al.Continuous range-based skyline queries in road networks[J].World Wide Web：Internet and Web Information Systems,2017，20(6):1443-1467.

[5] Chen Y,Lee C.Skyline path queries with aggregate attributes[J].IEEE Access,2016,4(9):4690-4706.

[6] Xie Jia-meng,Peng Hong,Zhou Bing,et al.Analysis of intelligent traffic information and research on decision support based on data mining techniques [J].Highway,2004,4(4):154-158.

[7] Kriegel H P,Renz M,Schubert M.Route skyline queries:a multi-preference pathplanning approach[C].Proceedings of the 26th International Conference on Data Engineering,2010.

[8] Zheng B,Lee K,Lee W.Location-dependent skyline query[C].Proceedings of the International Conference on Mobile Data Management MDM,2008.

[9] Kodama K,Iijima Y,Guo X,et al.Skyline queries based on user locations and preferences for making location-based recommendations[C].Proc of the 1st ACM SIGSPATIAL Int Workshop on Location Based Social Networks,2009.

[10] Lin X,Yuan Y,Wang W,et al.Stabbing the sky:efficient skyline computation over sliding windows[C].Proceedings of the 25th International Conference on Data Engineering,2005:502-513.

[11] Tao Y,Papadias D.Maintaining sliding window skylines on data streams[J].IEEE Transactions on Knowledge and Data Engineering,2006,18(3):377-391.

[12] Guttman A.R-tree:a dynamic index structure for spatial searching[J].Proc.ACM-CIGMOD Int.Conf.on Management of Data,1994,14(2):47-57.

[13] Sun Sheng-li,Huang Zhen-hua,et al.Efficient computation of subspace skylines over data streams[J].Chinese Journal of Computers,2007,30(8):1418-1428.

[14] Tian Li,Zou Peng,et al.Grid index based algorithm for continuous skyline computation[J].Chinese Journal of Computers,2008,31(6):998-1012.

[15] Zhuang Li,Zou Peng,et al.Continuous dynamic skyline queries over data stream[J].Journal of Computer Research and Development,2011,48(1):77-85.

[16] Zhan Yan-pu,Zhao Lei.Grid index based continuous k-skyband query algorithm over distributed data streams[J].Journal of Chinese Computer Systems,2014,35(2):233-238.

[17] Zhao L,Yang Y,et al.Continuous probabilistic subspace skyline query processing using grid projections[J].Journal of Computer Science & Technology,2014,29(2):332-344.

[18] Liu C,Tang S.An effective probabilistic skyline query process on uncertain data streams[J].Procedia Computer Science,2015,63(2):40-47.

[19] Guo X,Li H,Wulamu A,et al.Efficient processing of skyline group queries over a data stream[J].Tsinghua Science and Technology,2016,21(1):29-39.

附中文參考文獻：

[2] 王國鋒,宋鵬飛,張蘊靈.智能交通系統發展與展望[J].公路,2012,5(5):217-222.

[6] 謝嘉孟,彭 宏,周 兵,等.基于數據挖掘技術的智能交通信息分析與決策研究[J].公路,2004,4(4):154-158.

[13] 孫圣力,黃震華,等.數據流上高效計算子空間Skyine的算法[J].計算機學報,2007,30(8):1418-1428.

[14] 田 李,鄒 鵬,等.基于網格索引的連續Skyline計算方法[J].計算機學報,2008,31(6):998-1012.

[15] 張 麗,鄒 鵬,等.數據流上連續動態skyline查詢研究[J].計算機研究與發展,2011,48(1):77-85.

[16] 詹彥溥,趙 雷.使用網格索引的分布式數據流上K-Skyband連續查詢算法[J].小型微型計算機系統,2014,35(2):233-238.