支持室內障礙空間的DSP-Topk查詢優化算法研究

李博涵 張 潮 李東靜 許建秋,2 夏 斌 秦小麟,2

1(南京航空航天大學計算機科學與技術學院 南京 210016)2(江蘇省軟件新技術與產業化協同創新中心 南京 210016)3 (江蘇易圖地理信息科技股份有限公司 江蘇揚州 225000) (bhli@nuaa.edu.cn)

支持室內障礙空間的DSP-Topk查詢優化算法研究

李博涵1,2,3張 潮1李東靜1許建秋1,2夏 斌1秦小麟1,2

1(南京航空航天大學計算機科學與技術學院 南京 210016)2(江蘇省軟件新技術與產業化協同創新中心 南京 210016)3(江蘇易圖地理信息科技股份有限公司 江蘇揚州 225000) (bhli@nuaa.edu.cn)

多目標優化查詢是目前移動對象數據管理的研究熱點.多目標優化查詢過程中，用戶關心的目標對象屬性可能依賴于其他移動對象，因此移動對象之間的相互影響將導致目標對象屬性存在不確定性.已有的多目標優化算法需要遍歷所有目標對象，且不能有效支持目標對象屬性的動態變化.基于以上問題，提出了一種有效的應用于障礙空間的多目標優化算法DSP-Topk (dynamic and support pruning Topk),該算法采用可視區域模型處理障礙空間中移動對象的距離計算，利用基于最大夾角差的可視區域方法，提高了計算距離的效率.進而，利用動態調整機制解決目標對象屬性的不確定性，預處理的裁剪策略提高了算法效率.實驗結合商場真實商品數據集進行測試，與已有的Topk和DS-Topk算法對比表明：所提算法在查詢效率上有顯著提高，驗證了算法的有效性.

移動對象;多目標優化;不確定性;裁剪;動態調整

隨著定位技術和無線傳感器網絡技術的不斷發展，位置服務在人們的日常生活中扮演著越來越重要角色[1].位置服務的質量依賴于對移動對象數據的有效管理，這里的移動對象是廣義上的移動對象，指含有不斷變化屬性的數據對象，屬性包含空間屬性和非空間屬性[2].多目標優化查詢是移動對象數據管理中的研究熱點，如Topk[3]，Skyline[4]，NN[5]，KNN[6]等.多目標優化查詢可以幫助用戶解決在一定條件約束下，希望查詢結果在多個目標下達到最優的問題[7].

已有的移動對象數據管理研究主要集中在室外，包括自由空間中的移動對象和基于路網約束的移動對象[8-9].然而有數據統計表明人們活動的區域和時間約有80%處于室內環境，如辦公樓、商場、地鐵站等，因此針對移動對象在室內環境下的研究具有現實意義[10].在室內環境中移動對象多目標優化查詢具有眾多的應用場景.比如眾多的大型商場和購物中心，如南京萬達廣場占地面積達39萬m2、一站式購物中心達27萬m2、商場內的店鋪多達1 000家.如何在眾多店鋪中幫助顧客找到距離近、優惠多、顧客評價好的店鋪；在火車站、機場、醫院等人群密集的場所發生意外情況時，幫助人們在距離、安全系數等目標約束下選擇1個最佳的逃生方式和路線.這些都屬于室內移動對象多目標優化查詢的研究范疇.還有一些多目標優化查詢的過程中，用戶對某些關心的目標屬性設置了約束條件.如在進行店鋪推薦過程中用戶希望所推薦的店鋪距離自己當前位置100 m以內，在這里100 m就是用戶針對距離這個目標提出的閾值.

室內環境相對于室外，空間拓撲結構更加復雜，移動對象之間的距離計算難度更大，傳統的距離算法已不能很好地適應于室內環境[11].近年來，針對障礙空間中的移動對象數據管理已經取得了一定的成果，提出了3D幾何網絡模型(3D geometric network model)[12]和基于連通圖(accessibility base graph)的門模型[13]等代表性模型，這些模型很好地將現實物理世界抽象為簡單易懂的幾何模型，但是這些模型忽略了移動對象與障礙空間的位置關系，導致沒有障礙物阻擋的移動對象之間的距離也需要通過復雜的計算得到結果，降低了算法的性能.可視區域模型區分了移動對象與障礙空間的位置關系，但是已有的可視區域生成算法(如多次穿越障礙算法MTO)[14]需要連續掃描，重復穿越障礙空間導致可視區域生成算法效率較低.

在移動對象多目標優化查詢研究方面，已有的移動對象多目標優化算法只能返回1個最優解候選集(如Skyline查詢)或者需要遍歷所有目標對象(如Topk查詢)從而導致效率較低.另外在查詢過程中，移動對象之間的互相影響可能導致目標對象的屬性值發生改變，存在著不確定性，因此使用靜態的原始數據會導致查詢結果的不準確.如何將移動對象多目標優化查詢適應于室內障礙環境，特別當目標對象屬性發生動態改變時還能準確提供最優化查詢結果成為研究的出發點.針對這些問題，提出了一種改進的適用于障礙空間的移動對象多目標優化查詢算法DSP-Topk(dynamic and support pruning Topk).算法利用基于最大夾角差的可視區域算法計算移動對象之間的最短距離，確定移動對象的空間屬性，此外DSP-Topk支持目標對象屬性值的動態變化，采用預處理的裁剪策略避免對所有目標對象進行遍歷，提高算法效率.

本文主要貢獻有3點：

1) 采用預處理的裁剪策略和對候選集的動態調整方法得到改進的多目標優化查詢算法DSP-Topk；

2) 為更好地適應室內障礙環境，利用基于最大夾角差的可視區域算法，提高了移動對象之間距離計算的性能，使得DSP-Topk算法能很好地解決室內障礙環境中移動對象多目標優化查詢問題；

3) 結合商場真實的商品數據集進行測試，檢驗了算法的有效性.

1 相關工作

1.1 障礙空間中的距離計算

室內環境的空間方向、拓撲和距離關系由于障礙物的存在而變得更加復雜.不同于室外環境，在室內環境下移動對象之間距離相對較近，移動對象的距離之間受到障礙物的約束，當移動對象之間有障礙物的阻擋時，不能簡單地將距離抽象為2點之間的歐氏距離進行近似計算[15].文獻[13]提出基于連通圖的室內空間模型，以門作為節點記錄各個門之間最短距離，計算2個對象最短距離時，只需找到與目標對象最近的1扇門，將移動對象與門之間的距離和門所記錄的距離相加就是2個移動對象之間的最短距離.文獻[16]在歐氏空間中提出了確定對象的安全區域概念，所謂安全區域即空間中某一些目標對象結果集對應的1個空間范圍，1個室內空間可以有多個安全區域.在安全區域內，所有查詢對象具有相同的最近鄰查詢結果.當查詢點在安全區域內移動時，不再需要重復查詢.因而預先生成安全區域可以節省大量的實時計算開銷，但不足之處是對于那些空間位置范圍變化較大的移動對象需要不斷更新安全區域.文獻[14,17-18]提出可視區域的概念，在可視區域內查詢對象與目標對象之間的最短距離不受障礙空間的影響，但是傳統的可視區域算法效率較低.如多次穿越障礙算法MTO需要連續掃描查詢對象和障礙空間，重復穿越障礙空間導致算法效率較低.

1.2 多目標優化查詢

生活中，許多問題都是有相互沖突和影響的多個目標組成.人們經常會遇到使多個目標在給定區域同時盡可能最佳的優化問題，也就是多目標優化問題.優化問題存在的優化目標超過1個并需要同時處理，就成為多目標優化問題.傳統的移動對象多目標優化的問題通常有3種解決方法[19]：

1) Pareto方法(Skyline查詢)[20]，改進的Skyline查詢算法，如NN[5]，BBS[21-22]等.Skyline查詢返回1個最優解的候選集，但是當返回的結果規模較大時，并不能很好地為用戶提供決策.

2) 詞典序的方法，它為目標對象的不同屬性設置了不同級別的優先級，在進行選擇的過程中，按照優先級從高到低進行比較，如果高級別屬性值相同，再比較低一級的屬性值，直到得到結果.這種方法的優點在于最終能給用戶1個確定的結果，但是在某些特殊情況下，這種方法并不能返回理想結果.比如有A，B兩個待比較對象，它們分別有a，b，c三個屬性，屬性的優先級為a>b>c.其中A對象只是在a屬性上略優于B對象，但在b和c屬性上遠遠差于B，此刻詞典序的方法仍然認為最優選擇是A，但是在現實中用戶可能更加傾向于選擇B.

3) 將多目標優化問題轉化為單目標優化問題，將不同的屬性用一種統一的參考量來描述，用戶可以對不同的屬性依據自己的偏好設置不同的權值，然后對不同對象之間進行計算，找出最佳選擇.后續有學者不斷改進Topk算法，如DS-Topk相比于Topk只在最終對候選目標對象進行排序選擇，DS-Topk在前期進行一部分排序裁剪，減少了查詢對象的規模，提高了算法的效率.雖然DS-Topk算法進行了預裁剪，但是不支持用戶提出的閾值二次裁剪，且當查詢過程中存在移動對象之間的互相影響導致目標對象的屬性發生動態變化時也不適用.

在提高多目標優化算法的查詢效率上，也有2類解決方法：1)通過不斷改進索引結構來提高查詢效率，文獻[23]提出了一種基于索引的高效k-支配的Skyline查詢；2)通過減少IO訪問次數來提高查詢效率.文獻[24]基于排序機理的算法提出了一種新的度量空間中的Skyline查詢MkRS(metric Topk reverse Skyline)；文獻[25]利用Topk和Skyline各自的特點，提出了包括Topk-TBBST，Topk-dMBBS，Topk-wMBBS算法.這些算法可以有效提高Cache的命中率并減少IO數，但是都忽略了目標對象屬性的不確定性對查詢結果的影響.基于以上問題，提出了一種支持目標對象動態調整的、可裁剪的多目標最優化算法DSP-Topk算法.它通過對目標對象的裁剪，減小目標對象集合的規模，從而降低算法執行的時空開銷；通過改進算法實現動態調整機制，使其適應于目標對象屬性的動態變化.

2 基礎知識

2.1 問題描述

給出2個不同的室內環境下移動對象多目標優化的查詢實例.在圖書館內，學生希望找到距離自己最近的空位且該座位附近有可用的電源插座；某大型商場內，購物區內的顧客查找餐館，希望餐館距離近、價格實惠、排隊人數少.在這2個查詢中其他學生的離開或者提前使用插座會改變目標對象座位的屬性值；商場內其他顧客進出餐館，使目標對象餐館在排隊人數這個屬性上發生動態變化.通過這些實例甚至更多的室內場景查詢實例可知，看似與查詢無關的其他移動對象，可能使目標對象在用戶關心的某些屬性上發生動態變化，從而使目標對象的屬性具有不確定性.

將室內障礙環境和支持移動對象屬性動態調整的多目標優化查詢相結合將面臨2個挑戰:

1) 現有的室內障礙環境中移動對象距離計算模型，沒有區分移動對象與障礙空間的位置關系，導致沒有障礙物阻擋的移動對象之間的距離也需要通過復雜的計算得到結果；

2) 現有的移動對象多目標最優化算法以某一時刻的靜態數據作為查詢依據，缺乏考慮在查詢過程中目標對象的屬性值發生改變導致查詢結果不確定的情況.

針對上述問題，利用為顧客作餐館推薦為例，解決思路主要分為3步：

1) 對商場空間布局建立模型，利用可視區域的算法，確定顧客和所有餐館的空間距離，將這個距離作為餐館的空間屬性；

2) 對所有餐館進行預處理，利用裁剪策略縮小餐館查詢的規模；

3) 根據餐館屬性的實際動態變化情況采取動態調整策略和閾值二次裁剪重新生成新的候選集合，最后對候選集合進行排序得到最優推薦對象.

2.2 障礙空間中多目標優化查詢的形式化定義

為便于問題描述，利用為顧客作餐館推薦為查詢實例，結合餐館所在的商場的室內拓撲結構，給出移動對象多目標優化和室內場景下基于可視區域的距離計算的相關形式化定義.

將移動對象多目標優化查詢引入到室內障礙場景，移動對象之間距離計算成為1個難以規避的問題.室內障礙環境下，空間拓撲結構更加復雜，距離計算的好壞直接影響了移動對象多目標優化查詢算法的性能.為解決距離計算的復雜性，DSP-Topk算法采用最大夾角差的可視區域方法計算移動對象之間的距離.其中可視區域模型構造如下:

假設室內空間為I，具有n個移動對象構成集合Q={q1,q2,…,qn},2

將查詢對象與移動對象統一抽象為同一平面上的點，對于現實世界中移動對象之間的空間距離表示為平面上點之間的距離.移動對象作為多目標優化的目標對象，其空間距離包含2種情況：1)如果移動對象分布在同一平面上，則空間距離可直接計算；2)反之需要加上移動對象之間所在平面的距離(如樓梯的長度和電梯的高度).

DSP-Topk算法采用可視區域(visible area)的方法計算障礙空間中移動對象之間的最短距離.查詢對象p的可視區域利用最大夾角差的方法確定，其中關于a,b兩點與原點之間的夾角

(1)

查詢對象p的可視區域記為VISA(p)，其定義如下：

定義1. 可視區域. 在室內環境下，每個查詢對象p都有1個可視區域VISA(p)與之對應，區域VISA(p)中任意一點與點p的連線都不與障礙物相交,其中VISA(p)具有3個性質：

性質1.VISA(p)是1個封閉的空間，是由室內空間的邊界和障礙物的邊界所組成的.

性質2. 在二維平面下VISA(p)的面積小于等于室內空間的橫截面積，在3維空間下VISA(p)的體積小于等于室內空間的體積.

性質3. 根據目標對象是否在可視區域內，可分為2種情況：1)在VISA(p)中的目標對象qi與查詢對象p的最短距離是二者之間的歐氏距離即mindis=|p,qi|；2)不在VISA(p)的目標對象qi與查詢對象p的最短路徑通過障礙物所對應的多邊形Si的一些頂點，即

mindis=|p,Vi|+|Vi,Vj|+…+|Vn,p|.

例如前面提到的顧客在商場中希望找到這樣1個餐館，它距離自己較近、價格實惠以及排隊人數少.該場景可以用圖1表示，整個平面就是商場，查詢點p就是顧客，目標對象集合{q1,q2,…,q10}是餐館所抽象的點集合，餐館具有的空間屬性就是與顧客之間的距離，非空間屬性就是價格、排隊人數.圖1中的淺色陰影區域就是顧客p的可視區域VISA(p)，可以發現部分餐館在可視區域VISA(p)中，如q1，q2，也有部分餐館不在VISA(p)中如q4，q5.

Fig. 1 VISA of query object p on single obstacle圖1 單個障礙物下查詢對象p的可視區域

如圖2、圖3所示，當障礙空間內具有多個障礙物時，需要對每個多邊形的可視區域VISA(Si)求交集得到可視區域VISA(p).

在圖2中障礙空間中有多邊形S1，S2，S3.這種情況下VISA(p)=VISA(S1)∩VISA(S2)∩VISA(S3)其中VISA(S1)，VISA(S2)和VISA(S3)是查詢對象p相對于每個多邊形所求的可視區域如圖3所示.

Fig. 2 VISA of query object p on multi-obstacles圖2 多個障礙物下查詢對象p的可視區域

Fig. 3 VISA of single convex polygon on multi-obstacles圖3 多障礙物下單個多邊形可視區域示意圖

移動對象多目標優化查詢可以幫助用戶解決在一定條件約束下希望查詢結果在多個目標下達到最優的問題.用戶關心的多個目標對應于目標對象的多個屬性，關于目標對象多屬性的定義如下:

定義2. 目標對象多屬性.移動對象多目標優化查詢的對象稱為目標對象，目標對象具有的屬性包含的空間屬性和非空間屬性.空間屬性是指目標對象與查詢對象在障礙空間中的最短距離；非空間屬性是指對象除空間信息外含有的其他屬性.

當目標對象的規模較大時，對初始的候選集合進行裁剪處理能提高查詢效率.DSP-Topk算法的裁剪處理是利用R-樹中父節點空間包含子節點的思想.在DSP-Topk算法中，目標對象在插入到R-樹的過程中，每個對象都對應1個節點，節點對應1個最小屬性矩形(MBR).節點之間的層次關系通過矩形的包含關系來描述，對于節點有如下定義：

定義3. 最小屬性矩形MBR.每個目標對象在坐標軸上的投影對應于該對象在某一個屬性上的值.在二維平面內，即對象點qi在x,y軸上的投影與x,y軸構成的矩形為最小屬性矩形，記為MBRi.

定義4. 屬性矩形包含關系.對于qi對應的最小屬性矩形MBRi和qj對應的最小屬性矩形MBRj.如果S(MBRi)≥S(MBRj)，且MBRj與MBRi重疊且重疊面積等于MBRj則稱MBRj包含于MBRi，記為MBRj?MBRi.

DSP-Topk的裁剪處理如圖4所示，在考慮二維屬性的情況下，集合Q={q1,q2,…,q10}分布在平面上且認為目標對象的屬性值越小越優.對于qi所對應的MBRi來說如果MBRi包含其他對象的最小矩形，則易知該對象并非最優解，故可以舍棄，如q4對應的MBR4?MBR8.當MBRi不包含其他目標對象的最小矩形時，說明該對象為最優解的候選對象，如MBR2和MBR9.

Fig. 4 DSP-Topk pruning processing schematic圖4 DSP-Topk裁剪處理示意圖

DSP-Topk算法在進行多目標優化時對于目標對象的總體評價公式為

(2)

其中，q.value[i]是記錄目標對象在第i個屬性上的評價值，w[i]是用戶自定義的在第i個屬性上的影響因子.對于目標對象中用戶關心屬性的評價值可參照用戶自定義或者經驗公式統一量化.

3 支持裁剪和動態調整的DSP-Topk算法

在障礙空間中移動對象之間的距離計算復雜性增加，對象的屬性具有不確定性，所以對算法的適應性提出了更高的要求.當目標對象數量較小時，傳統的多目標優化算法可以滿足要求，但是目標對象集合大小超過一定量級，傳統的算法就不再適用.更為重要的是已有研究中的多目標優化算法沒有考慮到實際場景中移動對象屬性發生變化的情況，只是針對某一時刻的靜態數據進行查詢.由于移動對象的屬性具有不確定性，時刻t1移動對象的屬性可能在時刻t2發生改變.因此為了更好地給用戶提供推薦，需要在查詢時考慮移動對象屬性發生改變的可能.針對以上所提到的問題，提出一種改進的應用于障礙空間的多目標優化算法DSP-Topk，該算法能夠高效地計算移動對象之間的最短距離，對目標對象進行預處理裁剪，并且在查詢的過程中對候選集合根據目標對象屬性的實際變化進行動態調整.

3.1 DSP-Topk算法的空間距離計算方法

算法1. 可視區域生成算法.

輸入：查詢對象p、多邊形的頂點數組Obstacles;

輸出：可視區域VISA(p).

子函數說明：Calc_angle(pointA， pointB)函數輸入平面內2個點A，B輸出A，B與x軸構成的夾角；Judge(pointA， pointB，pointC) 函數輸入平面內3個點A，B，C，其中A是多邊形最高點，B是多邊形最低點，判斷C點是否在A的上方或者B的下方，如果是，就輸出true；反之，則輸出false.

變量定義：頂點個數obstacles_num、頂點數組Obstacles，Angle= 180°、最佳頂點:best_A和best_B.

①max_angle←0°；

② fori←0 toobstacles_numdo

③ forj←0 toobstacles_numdo

④ ifi=jthen

⑤ continue；

⑥ else

⑦angle_a←Calc_angle(Obstacles[i]，target)；

⑧angle_b←Calc_angle(Obstacles[j]，target)；

⑨less_angle←(angle_a>angle_b?angle_a-angle_b:angle_b-angle_a)；

⑩ end if

算法2. 夾角計算算法.

輸入：目標對象點qi、查詢對象點p；

輸出：qi相對于以查詢對象點p為原點與x軸構成的夾角.

變量定義：Angle=180°，PI為圓周率.

①a←0，b←0，c←0 ；

②angle←0；

③a←p1.x-p2.x；

④b←p1.y-p2.y；

⑤c←ba；

⑥angle←arctan(c)×AnglePI；

⑦ ifc≤0 then

⑧angle←angle+Angle；

⑨ else

⑩angle←angle；

根據算法1和算法2得到查詢對象p的可視區域VISA(p)，根據性質3將移動對象之間的最短距離計算分為2種情形：1)每個在VISA(p)中的目標對象qi與查詢對象p的最短距離是二者之間的歐氏距離即mindis=|p,qi|；2)不在VISA(p)的目標對象qi，最短距離是將目標對象和查詢點與多邊形Si的頂點集合V構成的一張無向圖G，如圖5所示.根據Dijkstra算法，得出目標對象與查詢對象之間的最短路徑，圖5中查詢對象p和目標對象q之間的最短距離為mindis=|p,v2|+|v2,v3|+|v3,v4|+|v4,q|.

Fig. 5 Weighted undirected graph圖5 帶權無向圖

在顧客查詢餐館的例子中，利用算法1和算法2計算出圖5中目標對象集與查詢對象p的最短距離以及用戶所關心的其他非空間屬性如表1所示.

Table 1 Target Objects Set Properties

3.2 DSP-Topk算法的裁剪操作

裁剪操作的目的是縮小目標對象集的規模，從而減少算法執行過程中所需的資源，提高算法的效率.如算法3所示：首先初始化1個隊列A和1棵R-樹(行①②)，將每個目標對象插入到R-樹；然后調整R-樹(行④～⑦)；最后遍歷R-樹，將所有的葉子節點加入到隊列A中(行⑧⑨)得到最優解候選集.

算法3. DSP-Topk裁剪算法.

輸入：數組tar_object；

輸出：裁剪后的最優解候選集A.

變量說明： 數組tar_object為目標對象集合、tar_num為目標對象大小.

① 初始化queueA；

② 初始化R_tree；

③ 輸入tar_object；

④ fori←0 totar_numdo

⑤insert(r_tree，tar_object[i])；*將移動 對象插入到R-樹的葉子結點*

⑥adjust(r_tree)；*調整R-樹*

⑦ end for

⑧ traverse ther_treefromroot；*遍歷R-樹 將所有葉子結點加入到隊列A中*

⑨ add allleafnodetoA；

⑩ returnA.

經過算法3裁剪過后的候選集為A={q2,q8,q9}.對于目標對象中用戶關心屬性的評價值參照用戶自定義或者其他經驗公式統一量化.最后可以將候選集歸結為如表2所示：

Table 2 Optimal Solution Properties of Candidates

3.3 動態調整和閾值二次裁剪

Fig. 6 Target objects dynamic change圖6 目標對象動態變化示意圖

由于目標對象的屬性具有不確定性，所以在查詢過程中當目標對象的屬性發生改變時，就可能影響查詢結果.如顧客查詢餐館的排隊人數時，在查詢的過程中，由于其他顧客的進出，導致餐館在排隊人數這個屬性上發生改變.圖6為目標對象屬性動態變化的示意圖，其中圖6(a)為在3維屬性空間中的目標對象動態變化情況，圖6(b)為在屬性1和屬性2構成的平面上的投影.

在進行移動對象動態調整時，需要將動態變化的對象與參考對象ref比較支配情況.其中對于目標對象屬性支配和參考對象ref有如下定義：

定義5. 目標對象屬性支配.對于對象qi和qj，如果qi在某1個屬性上優于qj且其他屬性都不比qj差，則稱qi支配qj，記為qi>qj；反之則稱qi被qj支配，記為qi

定義6. 參考對象.參考對象ref屬于初始候選集A且不在動態變化集D中，記為{ref|ref∈A∧ref?D}.如果A?D，則說明初始候選集中的對象都發生了變化，需重新查詢.

在查詢過程中目標對象的某些屬性實時發生了改變.為了準確地反映目標對象的真實情況需要對動態變化情況進行考慮.DSP-Topk算法中目標對象集合經過裁剪已經生成1個候選集A，此時需要將A與動態變化的集合D進行比較.

算法4. DSP-Topk動態調整算法.

輸入：候選集數組SP、動態變化集數組c_object、動態調整參考對象ref；

輸出：調整后的候選集A′.

變量說明：judge_num發生變化的移動對象個數；c_object[judge_num]發生變化的移動對象集合；sp_num原最優解候選集個數；SP[sp_num]初始候選集.

①flag←0；

② fori←0 tojudge_numdo

③ forj←0 tosp_numdo

④ ifc_object[i].num=SP[j].numthen*動態變化的對象是初始候選集中 對象*

⑤flag←1；

⑥ 比較c_object[i]和ref；

⑦ ifc_object[i]不被ref支配 then*變化的對象不被ref支配，則 更新對象信息*

⑧SP[j]←c_object[i]；

⑩ ifj=sp_num-1 then

閾值二次裁剪是針對用戶在某些屬性上提出的最低接受條件，閾值的提出意味著某1個目標對象即使在某些屬性上絕對的占優，但是如果不滿足閾值條件那么它也不會成為最優解. DSP-Topk算法在目標對象經過動態調整后進行閾值二次裁剪.如顧客找餐館的例子，經過動態調整后的最優解候選集為D={q2,q11,q9}.如果顧客在餐館價格優惠上提出閾值條件至少打8折，那么經過閾值二次裁剪后得到新的最優解候選集為如表3所示：

Table 3 Optimal Solution Properties of Candidates

對于動態調整和閾值二次裁剪后的候選集，利用式(2)對每個候選對象進行總體評價求和.總體評價后需要將候選集中所有對象排序.其中DSP-Topk算法中采用堆排序中的小頂堆排序.排序過程中，首先初始化1個小頂堆;然后將每個候選對象插入到堆中，調整堆的順序;最后得到1個包含所有候選對象的小頂堆.其中小頂堆內父節點的值不大于子節點，所以根節點是整個堆中的最小值，即用戶所關心的最佳選擇對象.在顧客找餐館的例子中經過DSP-Topk算法后所得到的最佳選擇對象為q10={10,8.0,5}.

4 實驗與結果分析

為了驗證DSP-Topk算法的可行性和有效性，對其進行了實驗測試.實驗所采用的數據為綜合商場真實的商品信息數據，其中商品大類有1 403類，商品種類總數是66 231個，測試數據來源于國內首家大數據交易平臺數據堂.其中顧客、商場障礙物和商品空間分布則隨機生成在商場二維平面圖上，平面圖大小為500×500個單位坐標.根據DSP-Topk算法，首先通過商品的空間分布利用可視區域算法得到商品與顧客之間的最短距離；然后加上顧客關心的非空間屬性如(價格、銷售情況和折扣等)進行多目標優化查詢.實驗測試了不同條件下DSP-Topk算法與已有多目標優化算法(Topk和DS-Topk)在查詢性能上的差異.為避免隨機性，查詢時間取10次測試的平均時間.實驗中的目標屬性和閾值均由用戶的查詢提出和確定.其中為了驗證DSP-Topk算法中動態調整的有效性，實驗過程中手動對顧客的空間位置和商品的某些屬性進行動態修改，如價格和折扣等.

4.1 靜態場景下DSP-Topk算法查詢性能分析

圖7所示為靜態狀態下目標對象集合大小對查詢性能的影響.從圖7中可以看出：當目標對象集合較小時，DSP-Topk算法所耗費的時間要大于已有的多目標優化算法.主要原因是DSP-Topk算法需要對目標對象進行裁剪、動態變化判斷等步驟花費了一部分時間.但是，隨著目標對象集合的增大，DSP-Topk算法的優越性就可以逐步體現.因為已有的多目標優化算法需要對所有的目標對象進行遍歷，查詢時間與目標對象的個數成正比.DS-Topk相比于Topk在最終對目標對象進行排序選擇時，對排序算法進行了優化所以DS-Topk的效率優于Topk.由于DSP-Topk算法先對目標對象集合進行一遍裁剪，刪除了絕大部分候選目標，得到1個數量比原先小得多的最優解候選集.這種執行機制保證了DSP-Topk算法與目標對象的個數關系無正相關性，隨著目標對象個數的增加，執行時間增加幅度趨于平緩.

Fig. 7 Impact of size of the static target set on query performance圖7 靜態目標對象集的大小對查詢性能的影響

4.2 動態場景下DSP-Topk算法查詢性能分析

已有的多目標優化算法沒有考慮目標對象的屬性發生動態變化的情況，當目標對象的屬性值發生改變時，有可能對最終的查詢結果產生影響.為了保證查詢結果的準確性，傳統算法就需要多次查詢，而DSP-Topk算法在執行過程中考慮到目標對象屬性發生動態變化的情況.如圖8所示為動態變化情況下目標對象集合大小對查詢性能的影響.對比圖7在目標對象集合較小時，DSP-Topk由于步驟較多執行時間會多于傳統算法；但動態變化情況下，已有算法由于要多次查詢導致時間增加，故DSP-Topk算法查詢時間始終優于已有算法.

Fig. 8 Impact of size of the dynamic target set on query performance圖8 動態變化下目標對象集合大小對查詢性能的影響

4.3 目標對象屬性個數對查詢性能的影響

對于同一個目標對象，不同的用戶所關心的屬性類型和個數是不一樣的.圖9為對象集合規模為10 000時，目標對象的屬性個數對查詢性能的影響，從圖9中可以看出已有的多目標優化算法隨著目標對象屬性個數的增加，查詢時間呈線性增長，這是因為已有算法的時間消耗基本在累加計算上，在進行目標對象總體評價時需要對所有屬性進行累加計算，因此屬性個數的增加導致查詢時間的增加.而DSP-Topk算法消耗的大部分時間在目標對象動態調整上，對于目標對象屬性個數的增加只影響在目標對象裁剪過程中，而且裁剪過程中進行目標對象比較時只需判斷大小而不需要累加計算，所以屬性個數的增加對DSP-Topk 算法的查詢效率影響不大.

Fig. 9 Number of attributes to query performance圖9 屬性個數對查詢性能的影響

4.4 目標對象動態變化集合規模對查詢性能的影響

DSP-Topk算法需要將動態變化的集合D與裁剪得到初始候選集SP進行比較得到新的候選集，因此動態變化集合D的大小直接影響查詢效率.為了更好地反映動態變化集合規模對查詢性能的影響，實驗測試了不同動態變化比例下DSP-Topk和傳統Topk算法查詢性能變化的情況，如圖10所示，隨著目標對象動態變化集合比例的增加，已有算法查詢性能變化不大，這是由于已有多目標優化算法通過連續查詢和遍歷全部目標對象的機制來適應目標對象屬性發生動態變化的情況；DSP-Topk算法隨著目標對象動態變化集合比例的增加，查詢時間也隨之增加，當動態變化的比例增加到50%左右時，DSP-Topk算法的查詢時間增速出現明顯的提升.實驗還發現對于不同的查詢規模，增長點基本在50%～60%之間浮動，此時最優解候選集的規模占總體查詢規模的1%左右.如圖10所示，當測試規模達到10 000時，增速提升發生在55%左右，最優解候選集的個數約為100；當測試規模為20 000時，增速提升發生在50%左右，最優解候選集的個數約為200.

Fig. 10 Dynamic changing scale to query performance圖10 動態變化規模對查詢性能的影響

4.5 目標對象動態變化規模對候選集的影響分析

目標對象屬性動態變化對最優解候選集的影響分為3種情況:1)原先在候選集中的對象發生改變，但改變后的對象仍然是最優解的候選對象，此時更新目標對象記為update_sp；2)原先在候選集中的對象發生改變后不再是最優解的候選對象，此時從初始候選集中刪除對象記為del_sp；3)原先不在候選集中的對象發生改變后成為最優解的候選對象，此時需要將該對象加入到候選集中記為add_sp.如圖11所示，當目標對象動態變化的比例增加，這三者的規模同時增加，但是add_sp增速和比重遠大于前2種.如圖11(b)的扇形圖可以發現，add_sp的比例達到23左右.因此可以得出這樣的結論：目標對象屬性動態變化對于初始候選集的影響主要歸結于原先不在候選集中的目標對象，經動態變化后成為了最優解的候選對象.

Fig. 11 Dynamic changing scale to candidate set圖11 動態變化規模對候選集的影響

5 結束語

在障礙空間中提出一種支持目標對象屬性動態調整的多目標優化算法DSP-Topk.算法面向具有多屬性的目標對象，采用預處理的裁剪策略降低目標對象集合規模.在查詢過程中，移動對象之間的互相影響可能會改變目標對象屬性，導致目標對象屬性具有不確定性.DSP-Topk算法引入目標對象動態調整機制，提出動態集和靜態集的概念，當目標對象屬性發生改變時，只需針對動態集和候選集進行比較并生成最終結果，提高了算法的效率.通過實驗對DSP-Topk算法和已有的移動對象多目標優化算法在多種條件下進行了對比和分析.實驗結果表明：DSP-Topk算法在目標對象集合較大時，更能體現其在查詢性能上的優勢.動態規模改變對查詢性能和候選集的影響也通過實驗進行了分析，發現目標對象動態比例與查詢時間成正相關變化，其中新增候選對象對候選集的影響最大.此外，已有的移動對象多目標優化算法對用戶關心的屬性個數十分敏感，查詢時間與屬性個數成線性增長.但屬性個數的增加對DSP-Topk算法查詢性能影響不大，隨著屬性個數的增加，算法仍然具有較好的查詢性能.

[1]Zhou Aoying, Yang Bin, Jin Cheqing, et al. Location-based services: Architecture and progress[J]. Chinese Journal of Computers, 2011, 34(7): 1155-1171 (in Chinese)(周傲英, 楊彬, 金澈清, 等. 基于位置的服務: 架構與進展 [J]. 計算機學報, 2011, 34(7): 1155-1171)

[2]Meng Xiaofeng, Chen Jidong. Moving Objects Management[M]. Berlin: Springer, 2010: 120-135

[3]Soliman M A, Ilyas I F, Chen-Chuan C K. Top-kquery processing in uncertain databases[C]Proc of the 23rd IEEE Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2007: 896-905

[4]Borzonyi S, Kossmann D, Stocker K. The skyline operator[C]Proc of the 17th IEEE Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2001: 421-430

[5]Kossmann D, Ramsak F, Rost S. Shooting stars in the sky: An online algorithm for skyline queries[C]Proc of the 28th Int Conf on Very Large Data Bases (VLDB). San Francisco: Morgan Kaufmann, 2002: 275-296

[6]Wu Wei, Guo Wenyuan, Tan K-L. Distributed processing of movingk-nearest-neighbor query on moving objects[C]Proc of the 23rd IEEE Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2007: 1116-1125

[7]Deb K. Multi-objective optimization using evolutionary algorithms[J]. Computer-Aided Civil and Infrastructure Engineering, 2001, 2(3): 509-521

[8]Xu Jianqiu, Güting R H, Qin Xiaolin. GMOBench: Benchmarking generic moving objects[J]. GeoInformatica, 2014, 19(2): 227-276

[9]Güting R H, Almeida V T, Ding Zhiming. Modeling and querying moving objects in networks[J]. The International Journal on Very Large Data Bases, 2006, 15(2): 165-190

[10]Jin Peiquan, Wang Na, Zhang Xiaoxiang, et al. Moving object data management for indoor spaces[J]. Chinese Journal of Computers, 2015, 38(9): 1777-1795 (in Chinese)(金培權, 汪娜, 張曉翔, 等. 面向室內空間的移動對象數據管理[J]. 計算機學報, 2015, 38(9): 1777-1795)

[11]Yuan Wenjie, Schneider M. Supporting continuous range queries in indoor space[C]Proc of the 11th Int Conf on Mobile Data Management. Piscataway, NJ: IEEE, 2010: 209-214

[12]Lee J. A spatial access-oriented implementation of a 3-D gis topological data model for urban entities[J]. GeoInformatica, 2004, 8(3): 237-264

[13]Lu Hua, Cao Xin, Jensen C S. A foundation for efficient indoor distance-aware query processing[C]Proc of the 28th IEEE Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2012: 438-449

[14]Xu Hu, Li Zhicheng, Lu Yansheng, et al. Group Visible Nearest Neighbor Queries in Spatial Databases[M]. Berlin: Springer, 2010: 333-344

[15]Gu Yu, Yu Xiaonan, Yu Ge. Method for continuous reversek-nearest neighbor queries in obstructed spatial databases[J]. Journal of Software, 2014, 25(8): 1806-1816 (in Chinese)(谷峪, 于曉楠, 于戈. 一種障礙空間數據庫中的連續反k近鄰查詢方法[J]. 軟件學報, 2014, 25(8): 1806-1816)

[16]Nutanong S, Zhang Rui, Tanin E, et al. The V*-Diagram: A query dependent approach to moving knn queries[J]. Proceedings of the VLDB Endowment, 2008, 1(1): 1095-1106

[17]Gao Yunjun, Zheng Baohua, Chen Gencai, et al. Visible reversek-nearest neighbor query processing in spatial databases[J]. IEEE Trans on Knowledge and Data Engineering, 2009, 21(9): 1314-1327

[18]Nutanong S, Tanin E, Zhang Rui. Visible Nearest Neighbor Queries[M]. Berlin: Springer, 2007: 876-883

[19]Freitas A A. A critical review of multi-objective optimization in data mining [J]. ACM SIGKDD Explorations Newsletter, 2004, 6(2): 77-86

[20]Wei Xiaojuan, Yang Jing，Li Cuiping, et al. Skyline query processing[J]. Journal of Software, 2008, 19(6):1386-1400 (in Chinese)(魏小娟, 楊婧, 李翠平, 等. Skyline查詢處理[J]. 軟件學報, 2008, 19(6): 1386-1400)

[21]Papadias D, Tao Yufei, Fu G, et al. An optimal and progressive algorithm for skyline queries[C]Proc of the 2003 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2003: 467-478

[22]Papadias D, Tao Yufei, Fu G, et al. Progressive skyline computation in database system[J]. ACM Trans on Database System, 2005, 30(1): 41-82

[23]Yin Jian, Yao Shuyu, Xue Shao’e, et al. An index based efficientk-dominant skyline algorithm[J]. Chinese Journal of Computers, 2010, 33(7): 1236-1245 (in Chinese)(印鑒, 姚樹宇, 薛少鍔, 等. 一種基于索引的高效k-支配Skyline算法[J]. 計算機學報, 2010, 33(7): 1236-1245)

[24]Zhang Bin, Jiang Tao, Gao Yunjun, et al. Topkquery processing of reverse skyline in metric space[J]. Journal of Computer Research and Development, 2014, 51(3): 627-636 (in Chinese)(張彬, 蔣濤, 高云君, 等. 度量空間中的Topk反向Skyline查詢算法[J]. 計算機研究與發展, 2014, 51(3): 627-636)

[25]Jiang Tao, Zhang Bin, Gao Yunjun, et al. Efficient Topkquery processing on mutual skyline[J]. Journal of Computer Research and Development, 2013, 50(5): 986-997 (in Chinese)(蔣濤, 張彬, 高云君, 等. 高效的Topk相互Skyline查詢算法[J]. 計算機研究與發展, 2013, 50(5): 986-997)

Li Bohan, born in 1979. PhD. Associate professor of Nanjing University of Aeronautics and Astronautics. Member of CCF. His main research interests include spatial and spatio-temporal databases and geographic information system.

Zhang Chao, born in 1991. Master candidate of Nanjing University of Aeronautics and Astronautics. Student member of CCF. His main research interests include spatio-temporal databases and uncertain moving objects indexing technology (zhangchao0607@nuaa.edu.cn).

Li Dongjing, born in 1991. Master candidate of Nanjing University of Aeronautics and Astronautics. Student member of CCF. Her main research interests include spatio-temporal databases and uncertain moving objects indexing technology ( 960395655@qq.com).

Xu Jianqiu, born in 1982. PhD. Associate professor of Nanjing University of Aeronautics and Astronautics. Member of CCF. His mian research interests include spatio-temporal databases and moving objects indexing technology (jianqiu@nuaa.edu.cn).

Xia Bin, born in 1992. Master candidate of Nanjing University of Aeronautics and Astronautics. Student member of CCF. His main research interests include spatio-temporal databases and security in distributed environment(742724470@qq.com).

Qin Xiaolin, born in 1953. PhD. Professor of Nanjing University of Aeronautics and Astronautics. Senior member of CCF. His main research interests include spatio-temporal databases and security in distributed environment( qinxcs@nuaa.edu.cn).

A DSP-Topk Query Optimization Algorithm Supporting Indoor Obstacle Space

Li Bohan1,2,3, Zhang Chao1, Li Dongjing1, Xu Jianqiu1,2, Xia Bin1, and Qin Xiaolin1,2

1(SchoolofComputerScienceandTechnology,NanjingUniversityofAeronauticsandAstronautics,Nanjing210016)2(CollaborativeInnovationCenterforNovelSoftwareTechnologyandIndustrializationofJiangsuProvince,Nanjing210016)3(JiangsuEasymapGeographicInformationTechnologyCorpLtd,Yangzhou,Jiangsu225000)

Multi-objective optimization is one of the key technologies in moving objects data management. While in the procession of multi-objective optimization query, the concerned target object’s attributes may depend on the other moving objects’ attributes. Therefore, moving objects can affect each other, which will lead to the uncertainty of the object’s properties. The existing multi-objective optimization algorithms need to traverse all the target objects, furthermore, they can’t effectively solve the problem of dynamic change of object attributes. We propose an effective multi-objective optimization algorithm DSP-Topk (dynamic and support pruning Topk) to solve the query in the obstacle space. Visual area model can calculate the distance between the moving objects with obstacles. The method of viewable area which applies the maximum differential angle can improve the calculation performance of the distance between moving objects. Then, we study the uncertainty of the object’s attributes by using the dynamic adjustment mechanism. The given pruning strategy with preprocessing improves the efficiency of the query. The results of experiments indicate that DSP-Topk algorithm improves the query efficiency significantly compared with the existing Topk algorithm and DS-Topk algorithm. Combined with the real testing data of goods in stores, the rationality and effectiveness of the algorithm are also verified.

moving objects; multi-objective optimization; uncertainty; pruning; dynamic adjustment

2015-10-09；

2016-02-16

國家自然科學基金項目(61373015,61300052,41301047);中央高校基本科研業務費專項資金項目(NP2013307, NZ2013306); 中國留學基金委國家公派留學項目(201406835051); 中國民用航空局安全能力建設基金(AS-SA201521);江蘇省自然科學基金青年基金項目(BK20130819);江蘇高校優勢學科建設工程資助項目;南京航空航天大學科研基地創新基金(NJ20160028);南京航空航天大學研究生創新實驗室開放基金項目(kfjj20151607). This work was supported by the National Natural Foundation of China(61373015,61300052,41301047), the Fundamental Research Funds for the Central Universities (NP2013307, NZ2013306), the China Scholarship Council Study Abroad Program (201406835051), the Funding of Security Ability Construction of Civil Aviation Administration of China (AS-SA201521), the Natural Science Foundation of Jiangsu Province for Youth Scholars (BK20130819), the Project Funded by the Priority Academic Program Development of Jiangsu Province Higher Education Institutions, the Innovation Funding of Nanjing University of Aeronautics and Astronautics (NJ20160028), and the Graduate Innovation and Practice Foundation of Nanjing University of Aeronautics and Astronautics (kfjj20151607).

TP311