支持室內(nèi)障礙空間的DSP-Topk查詢優(yōu)化算法研究

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

1(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 南京 210016)2(江蘇省軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心 南京 210016)3 (江蘇易圖地理信息科技股份有限公司 江蘇揚(yáng)州 225000) (bhli@nuaa.edu.cn)

支持室內(nèi)障礙空間的DSP-Topk查詢優(yōu)化算法研究

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

1(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 南京 210016)2(江蘇省軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心 南京 210016)3(江蘇易圖地理信息科技股份有限公司 江蘇揚(yáng)州 225000) (bhli@nuaa.edu.cn)

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

移動(dòng)對(duì)象;多目標(biāo)優(yōu)化;不確定性;裁剪;動(dòng)態(tài)調(diào)整

隨著定位技術(shù)和無(wú)線傳感器網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，位置服務(wù)在人們的日常生活中扮演著越來(lái)越重要角色[1].位置服務(wù)的質(zhì)量依賴于對(duì)移動(dòng)對(duì)象數(shù)據(jù)的有效管理，這里的移動(dòng)對(duì)象是廣義上的移動(dòng)對(duì)象，指含有不斷變化屬性的數(shù)據(jù)對(duì)象，屬性包含空間屬性和非空間屬性[2].多目標(biāo)優(yōu)化查詢是移動(dòng)對(duì)象數(shù)據(jù)管理中的研究熱點(diǎn)，如Topk[3]，Skyline[4]，NN[5]，KNN[6]等.多目標(biāo)優(yōu)化查詢可以幫助用戶解決在一定條件約束下，希望查詢結(jié)果在多個(gè)目標(biāo)下達(dá)到最優(yōu)的問(wèn)題[7].

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

室內(nèi)環(huán)境相對(duì)于室外，空間拓?fù)浣Y(jié)構(gòu)更加復(fù)雜，移動(dòng)對(duì)象之間的距離計(jì)算難度更大，傳統(tǒng)的距離算法已不能很好地適應(yīng)于室內(nèi)環(huán)境[11].近年來(lái)，針對(duì)障礙空間中的移動(dòng)對(duì)象數(shù)據(jù)管理已經(jīng)取得了一定的成果，提出了3D幾何網(wǎng)絡(luò)模型(3D geometric network model)[12]和基于連通圖(accessibility base graph)的門模型[13]等代表性模型，這些模型很好地將現(xiàn)實(shí)物理世界抽象為簡(jiǎn)單易懂的幾何模型，但是這些模型忽略了移動(dòng)對(duì)象與障礙空間的位置關(guān)系，導(dǎo)致沒有障礙物阻擋的移動(dòng)對(duì)象之間的距離也需要通過(guò)復(fù)雜的計(jì)算得到結(jié)果，降低了算法的性能.可視區(qū)域模型區(qū)分了移動(dòng)對(duì)象與障礙空間的位置關(guān)系，但是已有的可視區(qū)域生成算法(如多次穿越障礙算法MTO)[14]需要連續(xù)掃描，重復(fù)穿越障礙空間導(dǎo)致可視區(qū)域生成算法效率較低.

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

本文主要貢獻(xiàn)有3點(diǎn)：

1) 采用預(yù)處理的裁剪策略和對(duì)候選集的動(dòng)態(tài)調(diào)整方法得到改進(jìn)的多目標(biāo)優(yōu)化查詢算法DSP-Topk；

2) 為更好地適應(yīng)室內(nèi)障礙環(huán)境，利用基于最大夾角差的可視區(qū)域算法，提高了移動(dòng)對(duì)象之間距離計(jì)算的性能，使得DSP-Topk算法能很好地解決室內(nèi)障礙環(huán)境中移動(dòng)對(duì)象多目標(biāo)優(yōu)化查詢問(wèn)題；

3) 結(jié)合商場(chǎng)真實(shí)的商品數(shù)據(jù)集進(jìn)行測(cè)試，檢驗(yàn)了算法的有效性.

1 相關(guān)工作

1.1 障礙空間中的距離計(jì)算

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

1.2 多目標(biāo)優(yōu)化查詢

生活中，許多問(wèn)題都是有相互沖突和影響的多個(gè)目標(biāo)組成.人們經(jīng)常會(huì)遇到使多個(gè)目標(biāo)在給定區(qū)域同時(shí)盡可能最佳的優(yōu)化問(wèn)題，也就是多目標(biāo)優(yōu)化問(wèn)題.優(yōu)化問(wèn)題存在的優(yōu)化目標(biāo)超過(guò)1個(gè)并需要同時(shí)處理，就成為多目標(biāo)優(yōu)化問(wèn)題.傳統(tǒng)的移動(dòng)對(duì)象多目標(biāo)優(yōu)化的問(wèn)題通常有3種解決方法[19]：

1) Pareto方法(Skyline查詢)[20]，改進(jìn)的Skyline查詢算法，如NN[5]，BBS[21-22]等.Skyline查詢返回1個(gè)最優(yōu)解的候選集，但是當(dāng)返回的結(jié)果規(guī)模較大時(shí)，并不能很好地為用戶提供決策.

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

3) 將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題，將不同的屬性用一種統(tǒng)一的參考量來(lái)描述，用戶可以對(duì)不同的屬性依據(jù)自己的偏好設(shè)置不同的權(quán)值，然后對(duì)不同對(duì)象之間進(jìn)行計(jì)算，找出最佳選擇.后續(xù)有學(xué)者不斷改進(jìn)Topk算法，如DS-Topk相比于Topk只在最終對(duì)候選目標(biāo)對(duì)象進(jìn)行排序選擇，DS-Topk在前期進(jìn)行一部分排序裁剪，減少了查詢對(duì)象的規(guī)模，提高了算法的效率.雖然DS-Topk算法進(jìn)行了預(yù)裁剪，但是不支持用戶提出的閾值二次裁剪，且當(dāng)查詢過(guò)程中存在移動(dòng)對(duì)象之間的互相影響導(dǎo)致目標(biāo)對(duì)象的屬性發(fā)生動(dòng)態(tài)變化時(shí)也不適用.

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

2 基礎(chǔ)知識(shí)

2.1 問(wèn)題描述

給出2個(gè)不同的室內(nèi)環(huán)境下移動(dòng)對(duì)象多目標(biāo)優(yōu)化的查詢實(shí)例.在圖書館內(nèi)，學(xué)生希望找到距離自己最近的空位且該座位附近有可用的電源插座；某大型商場(chǎng)內(nèi)，購(gòu)物區(qū)內(nèi)的顧客查找餐館，希望餐館距離近、價(jià)格實(shí)惠、排隊(duì)人數(shù)少.在這2個(gè)查詢中其他學(xué)生的離開或者提前使用插座會(huì)改變目標(biāo)對(duì)象座位的屬性值；商場(chǎng)內(nèi)其他顧客進(jìn)出餐館，使目標(biāo)對(duì)象餐館在排隊(duì)人數(shù)這個(gè)屬性上發(fā)生動(dòng)態(tài)變化.通過(guò)這些實(shí)例甚至更多的室內(nèi)場(chǎng)景查詢實(shí)例可知，看似與查詢無(wú)關(guān)的其他移動(dòng)對(duì)象，可能使目標(biāo)對(duì)象在用戶關(guān)心的某些屬性上發(fā)生動(dòng)態(tài)變化，從而使目標(biāo)對(duì)象的屬性具有不確定性.

將室內(nèi)障礙環(huán)境和支持移動(dòng)對(duì)象屬性動(dòng)態(tài)調(diào)整的多目標(biāo)優(yōu)化查詢相結(jié)合將面臨2個(gè)挑戰(zhàn):

1) 現(xiàn)有的室內(nèi)障礙環(huán)境中移動(dòng)對(duì)象距離計(jì)算模型，沒有區(qū)分移動(dòng)對(duì)象與障礙空間的位置關(guān)系，導(dǎo)致沒有障礙物阻擋的移動(dòng)對(duì)象之間的距離也需要通過(guò)復(fù)雜的計(jì)算得到結(jié)果；

2) 現(xiàn)有的移動(dòng)對(duì)象多目標(biāo)最優(yōu)化算法以某一時(shí)刻的靜態(tài)數(shù)據(jù)作為查詢依據(jù)，缺乏考慮在查詢過(guò)程中目標(biāo)對(duì)象的屬性值發(fā)生改變導(dǎo)致查詢結(jié)果不確定的情況.

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

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

2) 對(duì)所有餐館進(jìn)行預(yù)處理，利用裁剪策略縮小餐館查詢的規(guī)模；

3) 根據(jù)餐館屬性的實(shí)際動(dòng)態(tài)變化情況采取動(dòng)態(tài)調(diào)整策略和閾值二次裁剪重新生成新的候選集合，最后對(duì)候選集合進(jìn)行排序得到最優(yōu)推薦對(duì)象.

2.2 障礙空間中多目標(biāo)優(yōu)化查詢的形式化定義

為便于問(wèn)題描述，利用為顧客作餐館推薦為查詢實(shí)例，結(jié)合餐館所在的商場(chǎng)的室內(nèi)拓?fù)浣Y(jié)構(gòu)，給出移動(dòng)對(duì)象多目標(biāo)優(yōu)化和室內(nèi)場(chǎng)景下基于可視區(qū)域的距離計(jì)算的相關(guān)形式化定義.

將移動(dòng)對(duì)象多目標(biāo)優(yōu)化查詢引入到室內(nèi)障礙場(chǎng)景，移動(dòng)對(duì)象之間距離計(jì)算成為1個(gè)難以規(guī)避的問(wèn)題.室內(nèi)障礙環(huán)境下，空間拓?fù)浣Y(jié)構(gòu)更加復(fù)雜，距離計(jì)算的好壞直接影響了移動(dòng)對(duì)象多目標(biāo)優(yōu)化查詢算法的性能.為解決距離計(jì)算的復(fù)雜性，DSP-Topk算法采用最大夾角差的可視區(qū)域方法計(jì)算移動(dòng)對(duì)象之間的距離.其中可視區(qū)域模型構(gòu)造如下:

假設(shè)室內(nèi)空間為I，具有n個(gè)移動(dòng)對(duì)象構(gòu)成集合Q={q1,q2,…,qn},2

將查詢對(duì)象與移動(dòng)對(duì)象統(tǒng)一抽象為同一平面上的點(diǎn)，對(duì)于現(xiàn)實(shí)世界中移動(dòng)對(duì)象之間的空間距離表示為平面上點(diǎn)之間的距離.移動(dòng)對(duì)象作為多目標(biāo)優(yōu)化的目標(biāo)對(duì)象，其空間距離包含2種情況：1)如果移動(dòng)對(duì)象分布在同一平面上，則空間距離可直接計(jì)算；2)反之需要加上移動(dòng)對(duì)象之間所在平面的距離(如樓梯的長(zhǎng)度和電梯的高度).

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

(1)

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

定義1. 可視區(qū)域. 在室內(nèi)環(huán)境下，每個(gè)查詢對(duì)象p都有1個(gè)可視區(qū)域VISA(p)與之對(duì)應(yīng)，區(qū)域VISA(p)中任意一點(diǎn)與點(diǎn)p的連線都不與障礙物相交,其中VISA(p)具有3個(gè)性質(zhì)：

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

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

性質(zhì)3. 根據(jù)目標(biāo)對(duì)象是否在可視區(qū)域內(nèi)，可分為2種情況：1)在VISA(p)中的目標(biāo)對(duì)象qi與查詢對(duì)象p的最短距離是二者之間的歐氏距離即mindis=|p,qi|；2)不在VISA(p)的目標(biāo)對(duì)象qi與查詢對(duì)象p的最短路徑通過(guò)障礙物所對(duì)應(yīng)的多邊形Si的一些頂點(diǎn)，即

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

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

Fig. 1 VISA of query object p on single obstacle圖1 單個(gè)障礙物下查詢對(duì)象p的可視區(qū)域

如圖2、圖3所示，當(dāng)障礙空間內(nèi)具有多個(gè)障礙物時(shí)，需要對(duì)每個(gè)多邊形的可視區(qū)域VISA(Si)求交集得到可視區(qū)域VISA(p).

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

Fig. 2 VISA of query object p on multi-obstacles圖2 多個(gè)障礙物下查詢對(duì)象p的可視區(qū)域

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

移動(dòng)對(duì)象多目標(biāo)優(yōu)化查詢可以幫助用戶解決在一定條件約束下希望查詢結(jié)果在多個(gè)目標(biāo)下達(dá)到最優(yōu)的問(wèn)題.用戶關(guān)心的多個(gè)目標(biāo)對(duì)應(yīng)于目標(biāo)對(duì)象的多個(gè)屬性，關(guān)于目標(biāo)對(duì)象多屬性的定義如下:

定義2. 目標(biāo)對(duì)象多屬性.移動(dòng)對(duì)象多目標(biāo)優(yōu)化查詢的對(duì)象稱為目標(biāo)對(duì)象，目標(biāo)對(duì)象具有的屬性包含的空間屬性和非空間屬性.空間屬性是指目標(biāo)對(duì)象與查詢對(duì)象在障礙空間中的最短距離；非空間屬性是指對(duì)象除空間信息外含有的其他屬性.

當(dāng)目標(biāo)對(duì)象的規(guī)模較大時(shí)，對(duì)初始的候選集合進(jìn)行裁剪處理能提高查詢效率.DSP-Topk算法的裁剪處理是利用R-樹中父節(jié)點(diǎn)空間包含子節(jié)點(diǎn)的思想.在DSP-Topk算法中，目標(biāo)對(duì)象在插入到R-樹的過(guò)程中，每個(gè)對(duì)象都對(duì)應(yīng)1個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)對(duì)應(yīng)1個(gè)最小屬性矩形(MBR).節(jié)點(diǎn)之間的層次關(guān)系通過(guò)矩形的包含關(guān)系來(lái)描述，對(duì)于節(jié)點(diǎn)有如下定義：

定義3. 最小屬性矩形MBR.每個(gè)目標(biāo)對(duì)象在坐標(biāo)軸上的投影對(duì)應(yīng)于該對(duì)象在某一個(gè)屬性上的值.在二維平面內(nèi)，即對(duì)象點(diǎn)qi在x,y軸上的投影與x,y軸構(gòu)成的矩形為最小屬性矩形，記為MBRi.

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

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

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

DSP-Topk算法在進(jìn)行多目標(biāo)優(yōu)化時(shí)對(duì)于目標(biāo)對(duì)象的總體評(píng)價(jià)公式為

(2)

其中，q.value[i]是記錄目標(biāo)對(duì)象在第i個(gè)屬性上的評(píng)價(jià)值，w[i]是用戶自定義的在第i個(gè)屬性上的影響因子.對(duì)于目標(biāo)對(duì)象中用戶關(guān)心屬性的評(píng)價(jià)值可參照用戶自定義或者經(jīng)驗(yàn)公式統(tǒng)一量化.

3 支持裁剪和動(dòng)態(tài)調(diào)整的DSP-Topk算法

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

3.1 DSP-Topk算法的空間距離計(jì)算方法

算法1. 可視區(qū)域生成算法.

輸入：查詢對(duì)象p、多邊形的頂點(diǎn)數(shù)組Obstacles;

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

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

變量定義：頂點(diǎn)個(gè)數(shù)obstacles_num、頂點(diǎn)數(shù)組Obstacles，Angle= 180°、最佳頂點(diǎn):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. 夾角計(jì)算算法.

輸入：目標(biāo)對(duì)象點(diǎn)qi、查詢對(duì)象點(diǎn)p；

輸出：qi相對(duì)于以查詢對(duì)象點(diǎn)p為原點(diǎn)與x軸構(gòu)成的夾角.

變量定義：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；

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

Fig. 5 Weighted undirected graph圖5 帶權(quán)無(wú)向圖

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

Table 1 Target Objects Set Properties

3.2 DSP-Topk算法的裁剪操作

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

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

輸入：數(shù)組tar_object；

輸出：裁剪后的最優(yōu)解候選集A.

變量說(shuō)明： 數(shù)組tar_object為目標(biāo)對(duì)象集合、tar_num為目標(biāo)對(duì)象大小.

① 初始化queueA；

② 初始化R_tree；

③ 輸入tar_object；

④ fori←0 totar_numdo

⑤insert(r_tree，tar_object[i])；*將移動(dòng) 對(duì)象插入到R-樹的葉子結(jié)點(diǎn)*

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

⑦ end for

⑧ traverse ther_treefromroot；*遍歷R-樹 將所有葉子結(jié)點(diǎn)加入到隊(duì)列A中*

⑨ add allleafnodetoA；

⑩ returnA.

經(jīng)過(guò)算法3裁剪過(guò)后的候選集為A={q2,q8,q9}.對(duì)于目標(biāo)對(duì)象中用戶關(guān)心屬性的評(píng)價(jià)值參照用戶自定義或者其他經(jīng)驗(yàn)公式統(tǒng)一量化.最后可以將候選集歸結(jié)為如表2所示：

Table 2 Optimal Solution Properties of Candidates

3.3 動(dòng)態(tài)調(diào)整和閾值二次裁剪

Fig. 6 Target objects dynamic change圖6 目標(biāo)對(duì)象動(dòng)態(tài)變化示意圖

由于目標(biāo)對(duì)象的屬性具有不確定性，所以在查詢過(guò)程中當(dāng)目標(biāo)對(duì)象的屬性發(fā)生改變時(shí)，就可能影響查詢結(jié)果.如顧客查詢餐館的排隊(duì)人數(shù)時(shí)，在查詢的過(guò)程中，由于其他顧客的進(jìn)出，導(dǎo)致餐館在排隊(duì)人數(shù)這個(gè)屬性上發(fā)生改變.圖6為目標(biāo)對(duì)象屬性動(dòng)態(tài)變化的示意圖，其中圖6(a)為在3維屬性空間中的目標(biāo)對(duì)象動(dòng)態(tài)變化情況，圖6(b)為在屬性1和屬性2構(gòu)成的平面上的投影.

在進(jìn)行移動(dòng)對(duì)象動(dòng)態(tài)調(diào)整時(shí)，需要將動(dòng)態(tài)變化的對(duì)象與參考對(duì)象ref比較支配情況.其中對(duì)于目標(biāo)對(duì)象屬性支配和參考對(duì)象ref有如下定義：

定義5. 目標(biāo)對(duì)象屬性支配.對(duì)于對(duì)象qi和qj，如果qi在某1個(gè)屬性上優(yōu)于qj且其他屬性都不比qj差，則稱qi支配qj，記為qi>qj；反之則稱qi被qj支配，記為qi

定義6. 參考對(duì)象.參考對(duì)象ref屬于初始候選集A且不在動(dòng)態(tài)變化集D中，記為{ref|ref∈A∧ref?D}.如果A?D，則說(shuō)明初始候選集中的對(duì)象都發(fā)生了變化，需重新查詢.

在查詢過(guò)程中目標(biāo)對(duì)象的某些屬性實(shí)時(shí)發(fā)生了改變.為了準(zhǔn)確地反映目標(biāo)對(duì)象的真實(shí)情況需要對(duì)動(dòng)態(tài)變化情況進(jìn)行考慮.DSP-Topk算法中目標(biāo)對(duì)象集合經(jīng)過(guò)裁剪已經(jīng)生成1個(gè)候選集A，此時(shí)需要將A與動(dòng)態(tài)變化的集合D進(jìn)行比較.

算法4. DSP-Topk動(dòng)態(tài)調(diào)整算法.

輸入：候選集數(shù)組SP、動(dòng)態(tài)變化集數(shù)組c_object、動(dòng)態(tài)調(diào)整參考對(duì)象ref；

輸出：調(diào)整后的候選集A′.

變量說(shuō)明：judge_num發(fā)生變化的移動(dòng)對(duì)象個(gè)數(shù)；c_object[judge_num]發(fā)生變化的移動(dòng)對(duì)象集合；sp_num原最優(yōu)解候選集個(gè)數(shù)；SP[sp_num]初始候選集.

①flag←0；

② fori←0 tojudge_numdo

③ forj←0 tosp_numdo

④ ifc_object[i].num=SP[j].numthen*動(dòng)態(tài)變化的對(duì)象是初始候選集中 對(duì)象*

⑤flag←1；

⑥ 比較c_object[i]和ref；

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

⑧SP[j]←c_object[i]；

⑩ ifj=sp_num-1 then

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

Table 3 Optimal Solution Properties of Candidates

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

4 實(shí)驗(yàn)與結(jié)果分析

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

4.1 靜態(tài)場(chǎng)景下DSP-Topk算法查詢性能分析

圖7所示為靜態(tài)狀態(tài)下目標(biāo)對(duì)象集合大小對(duì)查詢性能的影響.從圖7中可以看出：當(dāng)目標(biāo)對(duì)象集合較小時(shí)，DSP-Topk算法所耗費(fèi)的時(shí)間要大于已有的多目標(biāo)優(yōu)化算法.主要原因是DSP-Topk算法需要對(duì)目標(biāo)對(duì)象進(jìn)行裁剪、動(dòng)態(tài)變化判斷等步驟花費(fèi)了一部分時(shí)間.但是，隨著目標(biāo)對(duì)象集合的增大，DSP-Topk算法的優(yōu)越性就可以逐步體現(xiàn).因?yàn)橐延械亩嗄繕?biāo)優(yōu)化算法需要對(duì)所有的目標(biāo)對(duì)象進(jìn)行遍歷，查詢時(shí)間與目標(biāo)對(duì)象的個(gè)數(shù)成正比.DS-Topk相比于Topk在最終對(duì)目標(biāo)對(duì)象進(jìn)行排序選擇時(shí)，對(duì)排序算法進(jìn)行了優(yōu)化所以DS-Topk的效率優(yōu)于Topk.由于DSP-Topk算法先對(duì)目標(biāo)對(duì)象集合進(jìn)行一遍裁剪，刪除了絕大部分候選目標(biāo)，得到1個(gè)數(shù)量比原先小得多的最優(yōu)解候選集.這種執(zhí)行機(jī)制保證了DSP-Topk算法與目標(biāo)對(duì)象的個(gè)數(shù)關(guān)系無(wú)正相關(guān)性，隨著目標(biāo)對(duì)象個(gè)數(shù)的增加，執(zhí)行時(shí)間增加幅度趨于平緩.

Fig. 7 Impact of size of the static target set on query performance圖7 靜態(tài)目標(biāo)對(duì)象集的大小對(duì)查詢性能的影響

4.2 動(dòng)態(tài)場(chǎng)景下DSP-Topk算法查詢性能分析

已有的多目標(biāo)優(yōu)化算法沒有考慮目標(biāo)對(duì)象的屬性發(fā)生動(dòng)態(tài)變化的情況，當(dāng)目標(biāo)對(duì)象的屬性值發(fā)生改變時(shí)，有可能對(duì)最終的查詢結(jié)果產(chǎn)生影響.為了保證查詢結(jié)果的準(zhǔn)確性，傳統(tǒng)算法就需要多次查詢，而DSP-Topk算法在執(zhí)行過(guò)程中考慮到目標(biāo)對(duì)象屬性發(fā)生動(dòng)態(tài)變化的情況.如圖8所示為動(dòng)態(tài)變化情況下目標(biāo)對(duì)象集合大小對(duì)查詢性能的影響.對(duì)比圖7在目標(biāo)對(duì)象集合較小時(shí)，DSP-Topk由于步驟較多執(zhí)行時(shí)間會(huì)多于傳統(tǒng)算法；但動(dòng)態(tài)變化情況下，已有算法由于要多次查詢導(dǎo)致時(shí)間增加，故DSP-Topk算法查詢時(shí)間始終優(yōu)于已有算法.

Fig. 8 Impact of size of the dynamic target set on query performance圖8 動(dòng)態(tài)變化下目標(biāo)對(duì)象集合大小對(duì)查詢性能的影響

4.3 目標(biāo)對(duì)象屬性個(gè)數(shù)對(duì)查詢性能的影響

對(duì)于同一個(gè)目標(biāo)對(duì)象，不同的用戶所關(guān)心的屬性類型和個(gè)數(shù)是不一樣的.圖9為對(duì)象集合規(guī)模為10 000時(shí)，目標(biāo)對(duì)象的屬性個(gè)數(shù)對(duì)查詢性能的影響，從圖9中可以看出已有的多目標(biāo)優(yōu)化算法隨著目標(biāo)對(duì)象屬性個(gè)數(shù)的增加，查詢時(shí)間呈線性增長(zhǎng)，這是因?yàn)橐延兴惴ǖ臅r(shí)間消耗基本在累加計(jì)算上，在進(jìn)行目標(biāo)對(duì)象總體評(píng)價(jià)時(shí)需要對(duì)所有屬性進(jìn)行累加計(jì)算，因此屬性個(gè)數(shù)的增加導(dǎo)致查詢時(shí)間的增加.而DSP-Topk算法消耗的大部分時(shí)間在目標(biāo)對(duì)象動(dòng)態(tài)調(diào)整上，對(duì)于目標(biāo)對(duì)象屬性個(gè)數(shù)的增加只影響在目標(biāo)對(duì)象裁剪過(guò)程中，而且裁剪過(guò)程中進(jìn)行目標(biāo)對(duì)象比較時(shí)只需判斷大小而不需要累加計(jì)算，所以屬性個(gè)數(shù)的增加對(duì)DSP-Topk 算法的查詢效率影響不大.

Fig. 9 Number of attributes to query performance圖9 屬性個(gè)數(shù)對(duì)查詢性能的影響

4.4 目標(biāo)對(duì)象動(dòng)態(tài)變化集合規(guī)模對(duì)查詢性能的影響

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

Fig. 10 Dynamic changing scale to query performance圖10 動(dòng)態(tài)變化規(guī)模對(duì)查詢性能的影響

4.5 目標(biāo)對(duì)象動(dòng)態(tài)變化規(guī)模對(duì)候選集的影響分析

目標(biāo)對(duì)象屬性動(dòng)態(tài)變化對(duì)最優(yōu)解候選集的影響分為3種情況:1)原先在候選集中的對(duì)象發(fā)生改變，但改變后的對(duì)象仍然是最優(yōu)解的候選對(duì)象，此時(shí)更新目標(biāo)對(duì)象記為update_sp；2)原先在候選集中的對(duì)象發(fā)生改變后不再是最優(yōu)解的候選對(duì)象，此時(shí)從初始候選集中刪除對(duì)象記為del_sp；3)原先不在候選集中的對(duì)象發(fā)生改變后成為最優(yōu)解的候選對(duì)象，此時(shí)需要將該對(duì)象加入到候選集中記為add_sp.如圖11所示，當(dāng)目標(biāo)對(duì)象動(dòng)態(tài)變化的比例增加，這三者的規(guī)模同時(shí)增加，但是add_sp增速和比重遠(yuǎn)大于前2種.如圖11(b)的扇形圖可以發(fā)現(xiàn)，add_sp的比例達(dá)到23左右.因此可以得出這樣的結(jié)論：目標(biāo)對(duì)象屬性動(dòng)態(tài)變化對(duì)于初始候選集的影響主要?dú)w結(jié)于原先不在候選集中的目標(biāo)對(duì)象，經(jīng)動(dòng)態(tài)變化后成為了最優(yōu)解的候選對(duì)象.

Fig. 11 Dynamic changing scale to candidate set圖11 動(dòng)態(tài)變化規(guī)模對(duì)候選集的影響

5 結(jié)束語(yǔ)

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

[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)(周傲英, 楊彬, 金澈清, 等. 基于位置的服務(wù): 架構(gòu)與進(jìn)展 [J]. 計(jì)算機(jī)學(xué)報(bào), 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)(金培權(quán), 汪娜, 張曉翔, 等. 面向室內(nèi)空間的移動(dòng)對(duì)象數(shù)據(jù)管理[J]. 計(jì)算機(jī)學(xué)報(bào), 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)(谷峪, 于曉楠, 于戈. 一種障礙空間數(shù)據(jù)庫(kù)中的連續(xù)反k近鄰查詢方法[J]. 軟件學(xué)報(bào), 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]. 軟件學(xué)報(bào), 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]. 計(jì)算機(jī)學(xué)報(bào), 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]. 計(jì)算機(jī)研究與發(fā)展, 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]. 計(jì)算機(jī)研究與發(fā)展, 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

國(guó)家自然科學(xué)基金項(xiàng)目(61373015,61300052,41301047);中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(NP2013307, NZ2013306); 中國(guó)留學(xué)基金委國(guó)家公派留學(xué)項(xiàng)目(201406835051); 中國(guó)民用航空局安全能力建設(shè)基金(AS-SA201521);江蘇省自然科學(xué)基金青年基金項(xiàng)目(BK20130819);江蘇高校優(yōu)勢(shì)學(xué)科建設(shè)工程資助項(xiàng)目;南京航空航天大學(xué)科研基地創(chuàng)新基金(NJ20160028);南京航空航天大學(xué)研究生創(chuàng)新實(shí)驗(yàn)室開放基金項(xiàng)目(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