利用k-d樹索引改進數(shù)據(jù)流skyline查詢算法

唐穎峰, 陳世平

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

1 引 言

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

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

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

2 相關概念

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

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

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

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

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

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

3 算法的概要設計

3.1 算法數(shù)據(jù)結構

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

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

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

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

KD_tree

{ KD_tree LeftChild;

KD_tree RightChild;

List IncludedPoints;

Array UpperBound;

Array LowerBound;

Array AreaUpperBound;}

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

根據(jù)k-d樹的構造規(guī)則,可以得到如下性質:

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

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

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

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

定理1.對于任意數(shù)據(jù)點p,k-d樹的任意節(jié)點Q,若p

證明:p

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

剪枝規(guī)則1.設有新到達數(shù)據(jù)點p,k-d樹上任一節(jié)點Q,滿足p

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

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

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

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

3.2 算法的處理流程

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

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

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

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

4 算法的詳細實現(xiàn)

4.1 k-d樹的剪枝

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

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

輸入:剪枝前的k-d樹及當前到達數(shù)據(jù)點p

輸出:剪枝后的k-d樹

步驟:

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

if p < Q.UpperBound

if p≮Q.LowerBound

繼續(xù)訪問Q.LeftChild及Q.RightChild;

if p

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

AreaUpperBound為P.AreaUpperBound;

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

以及P.IncludedPoints;

刪除Q及其孩子;

刪除Q.IncludedPoints在APL中對應的數(shù)據(jù)點;

刪除事件鏈中Q.IncludedPoints數(shù)據(jù)點的對應事件;

if p≮Q.UpperBound

if Q為根節(jié)點

return;

else

繼續(xù)訪問Q.LeftChild及Q.RightChild;

4.2 計算影響時間

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

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

輸入:當前到達數(shù)據(jù)點p

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

步驟:

p.teff=p.tarr+W;

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

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

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

if Q為根節(jié)點或右孩子

return;

else 繼續(xù)訪問B;

else

if p

if Q為根節(jié)點或右孩子

return;

else 繼續(xù)訪問B;

if Q.UpperBound

t=max(Q.IncludedPoints.tarr);

p.teff=t+W;

if Q為根節(jié)點或右孩子

return;

else 繼續(xù)訪問B;

else

if Q為非葉節(jié)點

繼續(xù)訪問Q.LeftChild及Q.RightChild;

else

if Q為右孩子

return;

else 繼續(xù)訪問B;

4.3 事件鏈更新及事件處理

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

算法3.事件鏈更新算法

輸入:計算影響時間后的數(shù)據(jù)點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];

當時間戳發(fā)生變化時,事件鏈處理過程即被觸發(fā),并對事件鏈中當前時間戳的節(jié)點中的事件進行處理.設事件e對應的數(shù)據(jù)點為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樹更新

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

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

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

輸出:更新后的k-d樹

步驟:

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

if Q為空

新建節(jié)點Q,將p插入Q.IncludedPoints;

Q.LowerBound=p.attr;

Q.UpperBound=p.attr;

Q.AreaUpperBound=p.attr;

return;

if p

if Q非葉節(jié)點

將p插入Q.IncludedPoints;

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

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

繼續(xù)訪問Q.LeftChild;

if Q為葉節(jié)點

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

新建兩個節(jié)點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非根節(jié)點

則繼續(xù)訪問B節(jié)點;

if Q為根節(jié)點

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

新建兩個節(jié)點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的網格總數(shù)為nd.k-d樹則假設為一個標準k-d樹,即從根節(jié)點開始向下,每一層順次以空間的一維對當前節(jié)點對應空間進行分半劃分,持續(xù)劃分直到葉節(jié)點總數(shù)為nd,此時k-d樹的層數(shù)為ln(nd).

在網格索引中,對于一個新到數(shù)據(jù)點p,若要確定p與已有數(shù)據(jù)點間的支配關系,需要進行兩部分的支配檢測:網格間的支配檢測和網格內數(shù)據(jù)點的支配檢測.網格間的支配檢測即是以p所在的網格g與其他網格進行支配檢測,排除與g中數(shù)據(jù)點可以確定支配關系的網格,找出無法確定支配關系的網格集合G*,其復雜的表示為Cg.網格內數(shù)據(jù)點的支配檢測即為p與網格集合G*內所包含的所有數(shù)據(jù)點逐一進行支配檢測,其復雜的表示為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*中的網格數(shù)量為nd-(n-1)d.

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

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

CKD=Ct+Clp

(2)

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

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

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

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

2)第l次已劃分的維,其數(shù)量為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)

而根據(jù)給定k-d樹的劃分規(guī)則,有:

l=?i/d」≤i/d

(4)

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

(5)

設遍歷到最后一層所訪問的總節(jié)點數(shù)為N,則有:

(6)

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

N≤d2lnn*n(d-1)

(7)

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

d2lnn≤n

(8)

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

6 實驗及結果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖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算法在標準數(shù)據(jù)環(huán)境有著較好的性能表現(xiàn);在實際交通數(shù)據(jù)環(huán)境下則呈現(xiàn)出良好的自適應性以及明顯的性能優(yōu)勢,更適用于疏密分布變化較大的交通數(shù)據(jù)流skyline查詢任務.

7 結 論

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

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

[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] 王國鋒,宋鵬飛,張?zhí)N靈.智能交通系統(tǒng)發(fā)展與展望[J].公路,2012,5(5):217-222.

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

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

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

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

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