空間數(shù)據(jù)庫(kù)輪廓查詢關(guān)鍵技術(shù)分析和展望

　　摘要：空間查詢及優(yōu)化技術(shù)是研究空間數(shù)據(jù)的難點(diǎn)。輪廓查詢技術(shù)對(duì)于各種數(shù)據(jù)庫(kù)和網(wǎng)絡(luò)應(yīng)用中的空間查詢及優(yōu)化起著至關(guān)重要的作用，已經(jīng)成為空間查詢及優(yōu)化領(lǐng)域的熱點(diǎn)課題。該文對(duì)現(xiàn)有的輪廓查詢關(guān)鍵技術(shù)進(jìn)行了分析和總結(jié)，并對(duì)未來(lái)的發(fā)展方向進(jìn)行了展望。
　　關(guān)鍵詞：空間數(shù)據(jù)庫(kù)；輪廓查詢；輪廓更新
　　中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2012）28-6645-03
　　近年來(lái)，空間數(shù)據(jù)庫(kù)作為一門(mén)非常前沿的交叉學(xué)科，逐漸成為熱點(diǎn)研究領(lǐng)域。它在地理信息系統(tǒng)，多媒體信息系統(tǒng)，計(jì)算機(jī)輔助設(shè)計(jì)，數(shù)據(jù)倉(cāng)庫(kù)技術(shù)等諸多應(yīng)用領(lǐng)域中都起著非常重要的作用。因此，空間數(shù)據(jù)庫(kù)以及對(duì)空間數(shù)據(jù)庫(kù)進(jìn)行查詢優(yōu)化的研究備受關(guān)注。
　　“輪廓”這個(gè)概念最初是2001年Borzsonyi[1]等人在VLDB（Very Large Databases）會(huì)議上作為一個(gè)操作被提出來(lái)的。在d維空間中，輪廓是一個(gè)d維點(diǎn)的集合，是由在所有維上不被其它任何點(diǎn)支配的點(diǎn)組成，記作SP（D，S）。假定一個(gè)點(diǎn)的集合p1，p2，p3，…，pn，點(diǎn)pi支配點(diǎn)，pj當(dāng)且僅當(dāng)點(diǎn)pi在任意維上的坐標(biāo)都不小于點(diǎn)pj對(duì)應(yīng)的坐標(biāo)，且至少在某一維上比pj大。
　　輪廓查詢?cè)谏婕岸鄻?biāo)準(zhǔn)決策的應(yīng)用中起著非常重要的作用。例如，在網(wǎng)上購(gòu)買(mǎi)手機(jī)，手機(jī)的功能各有差異，可能功能強(qiáng)大的手機(jī)價(jià)位高，功能一般的手機(jī)價(jià)位低，在考慮多種因素的情況下，如何選擇適合自己的最佳方案，輪廓的計(jì)算可以輕松解決此類問(wèn)題。由于輪廓查詢技術(shù)有著重要的理論實(shí)際應(yīng)用價(jià)值，因此一直受到相關(guān)專家和學(xué)者的重點(diǎn)關(guān)注。目前，輪廓計(jì)算方法很多，本文將分為輪廓算法、高維空間下的輪廓查詢和輪廓更新技術(shù)三部分介紹。
　　1 輪廓查詢
　　輪廓計(jì)算的基本觀點(diǎn)，就是將所有的輪廓點(diǎn)都求出來(lái)。主要有以下幾種方法：嵌套循環(huán)方法（BNL）[1]、D&C（Divide-and-Conquer）[1]方法、位圖方法[2]、索引輪廓查詢方法[2] 、排序過(guò)濾輪廓查詢方法SFS（Sort Filter Slyline） [3]、最近鄰查詢方法[4]、基于窗口查詢的輪廓查詢方法[5]等。
　　1.1 BNL和D&C
　　計(jì)算輪廓的最直接方法就是將每個(gè)數(shù)據(jù)點(diǎn)p與其他的數(shù)據(jù)點(diǎn)進(jìn)行比較，如果點(diǎn)p不被支配，那么它就是輪廓的一部分。BNL方法就是基于這個(gè)思想掃描數(shù)據(jù)文件，將一個(gè)輪廓點(diǎn)的候選列表放在主存中，初始的時(shí)列表中只有第一個(gè)數(shù)據(jù)點(diǎn)，之后每個(gè)點(diǎn)p都通過(guò)支配定義來(lái)判斷該點(diǎn)是不是輪廓點(diǎn)。
　　BNL的應(yīng)用性很廣泛，因?yàn)樗鼰o(wú)需將數(shù)據(jù)文件排序或索引就可以應(yīng)用到任意維上。但是它的列表大小可能會(huì)超過(guò)主存容量，此時(shí)，所有溢出的數(shù)據(jù)點(diǎn)就會(huì)被添加到一個(gè)臨時(shí)文件中，這就需要執(zhí)行多次BNL。而且BNL在漸進(jìn)性方面有著明顯不足，在返回第一個(gè)輪廓點(diǎn)之前必須對(duì)整個(gè)數(shù)據(jù)集進(jìn)行讀取。
　　D&C和BNL都是Borzsonyi[1]在2001年的ICDE會(huì)議上提出的。D&C是將數(shù)據(jù)集劃分為多個(gè)分區(qū)，然后利用主存算法來(lái)分別計(jì)算每個(gè)分區(qū)的局部輪廓，最終的輪廓通過(guò)將局部輪廓篩選合并獲得。
　　1.2 位圖方法和索引輪廓查詢方法
　　Tan[2]等人在2001年的VLDB會(huì)議上創(chuàng)新的提出了位圖輪廓查詢方法，將所有的信息在位圖中編碼來(lái)確定一個(gè)點(diǎn)是否在輪廓上。
　　位圖法的效率依賴于位圖操作的速度，而且對(duì)于每個(gè)要檢測(cè)的數(shù)據(jù)點(diǎn)來(lái)說(shuō)，必須檢索所有點(diǎn)的位圖來(lái)得到對(duì)應(yīng)位，因此如果不同值的數(shù)碼非常大的話，空間代價(jià)會(huì)相當(dāng)高，所以這種方法很不適合動(dòng)態(tài)數(shù)據(jù)集的運(yùn)算。
　　索引輪廓查詢方法也是Tan等人同時(shí)提出的。它把d維的數(shù)據(jù)點(diǎn)集分成d個(gè)列表，如果在第i軸上的坐標(biāo)在所有維上是最小的，也就是說(shuō)對(duì)于所有j≠i有pi≤pj，那么將點(diǎn)p=（p1，p2，…pd）放到第i個(gè)列表中（1≤i≤d）。
　　這種方法的優(yōu)點(diǎn)是能夠快速返回列表前端的輪廓點(diǎn)，缺點(diǎn)是返回輪廓點(diǎn)的順序是固定的，因此無(wú)法支持用戶自定義的優(yōu)先選擇標(biāo)準(zhǔn)。
　　1.3 排序過(guò)濾輪廓查詢方法
　　Chomicki[3]在2003的ICDE會(huì)議上提出了BNL的改進(jìn)方法-排序過(guò)濾輪廓查詢方法SFS。根據(jù)一個(gè)優(yōu)先選擇函數(shù)首先對(duì)整個(gè)數(shù)據(jù)集進(jìn)行排序，候選點(diǎn)按照分值以升序插入到列表中，因?yàn)榫哂械头种档狞c(diǎn)可能支配大量的點(diǎn)，因此，使得修剪更有效。
　　SFS算法展現(xiàn)出漸進(jìn)性的特點(diǎn)，因?yàn)閿?shù)據(jù)的預(yù)排序能夠確保支配點(diǎn)q的點(diǎn)必須在q之前被訪問(wèn)，因此，能夠立即將插入到列表中的點(diǎn)作為輪廓點(diǎn)進(jìn)行輸出。然而，SFS不得不掃描整個(gè)數(shù)據(jù)文件才能返回一個(gè)完整的輪廓。
　　1.4 最近鄰查詢方法
　　NN是利用最近鄰查詢的結(jié)果來(lái)遞歸劃分?jǐn)?shù)據(jù)空間，通過(guò)查找與原點(diǎn)具有最小距離的點(diǎn)，分別求得輪廓。此方法的查詢速度比前幾種方法都快，具有漸進(jìn)性，而且支持在線處理。但是，對(duì)于高維數(shù)據(jù)來(lái)說(shuō)，該方法存在嚴(yán)重的空間重合問(wèn)題。
　　2 高維空間下輪廓查詢關(guān)鍵技術(shù)
　　然而，隨著考慮因素的增加，數(shù)據(jù)的空間維數(shù)和數(shù)據(jù)集也在增大，一個(gè)點(diǎn)支配其它點(diǎn)的機(jī)會(huì)變得越來(lái)越小，用基本的輪廓技術(shù)計(jì)算將會(huì)得到龐大的輪廓點(diǎn)集合，故而不能再為用戶提供有效的決策依據(jù)。因此，求解高維空間下的輪廓?jiǎng)荼爻蔀榭臻g應(yīng)用的難點(diǎn)和突破點(diǎn)。
　　解決此問(wèn)題的直接方法就是設(shè)法減少輪廓點(diǎn)的個(gè)數(shù)，去掉那些較次要的輪廓點(diǎn)，保留那些支配力相對(duì)較高的輪廓點(diǎn)，在數(shù)據(jù)量很大的情況下，同樣會(huì)提供正確的決策支持。
　　2.1 強(qiáng)輪廓點(diǎn)查詢技術(shù)
　　為了獲得更少的輪廓點(diǎn)，Zhengjie Zhang[4] 等人提出了“δ-子空間”和“強(qiáng)輪廓點(diǎn)”的概念。給定一個(gè)空間的集合S，如果s∈S，且s子集合上的輪廓點(diǎn)個(gè)數(shù)小于δ，則稱s為δ-子空間。集合S的所有δ-子空間的輪廓點(diǎn)的并集，稱為強(qiáng)輪廓點(diǎn)。
　　空間維數(shù)越少，數(shù)據(jù)集合中的某個(gè)點(diǎn)支配其它點(diǎn)的機(jī)會(huì)越大。所以，δ-子空間的提出，使得s集合的維數(shù)小于S的維數(shù)，從而使得輪廓點(diǎn)的個(gè)數(shù)減少，很好得解決了輪廓點(diǎn)集合過(guò)大的問(wèn)題。技術(shù)的核心部分就是如何求得集合S的所有δ-子空間。該技術(shù)提供了兩種實(shí)現(xiàn)算法：廣度優(yōu)先策略（BFS） 和深度優(yōu)先策略（DFS）。
　　在理論上，DFS比BFS的算法節(jié)省時(shí)間，但是在具體實(shí)驗(yàn)時(shí)，后者要比前者的表現(xiàn)要好得多。原因是，DFS只是在求解δ-子空間時(shí)比BFS要快，但是在輪廓計(jì)算的過(guò)程中，前者會(huì)在假的子空間計(jì)算上浪費(fèi)很多時(shí)間。
　　2.2 輪廓頻率技術(shù)
　　該技術(shù)突破了在高維空間中減少輪廓點(diǎn)的定勢(shì)思維，從一個(gè)全新方面來(lái)獲得想要的輪廓點(diǎn)。Chee-Yong Chan[5]提出了“輪廓頻率”的新概念，在給定的n維空間中，在任意維上對(duì)數(shù)據(jù)集進(jìn)行輪廓計(jì)算，最后將所有的輪廓點(diǎn)按照出現(xiàn)頻率排名。這樣，在高維空間下的輪廓查詢也就變成了求解前k個(gè)頻率最高的輪廓點(diǎn)的問(wèn)題，大大的減少了輪廓點(diǎn)的個(gè)數(shù)。
　　2.3 k-支配輪廓查詢技術(shù)
　　為了在高維空間中找到那些重要而且有決定意義的輪廓點(diǎn)。Chee-Yong Chan[6]在2006年提出了k-支配輪廓的定義。k-支配：假定一個(gè)點(diǎn)的集合D（p1，p2，p3….pn），點(diǎn)pi k-支配點(diǎn)pj，當(dāng)且僅當(dāng)點(diǎn)pi在k維上的坐標(biāo)都不小于點(diǎn)pj對(duì)應(yīng)的坐標(biāo)，且至少在k維中的某一維上比pj大。該定義放寬了原來(lái)支配的定義，并提出一次掃描算法、兩次掃描算法和排序檢索算法來(lái)實(shí)現(xiàn)k-支配輪廓查詢。
　　由于k-支配定義的引入，使得輪廓查詢計(jì)算返回更少的有興趣的點(diǎn)，但是，對(duì)于k值的確定是件困難的事。因?yàn)閗值取得過(guò)大，就不能起到減少返回輪廓點(diǎn)的作用；k值取得過(guò)小，就會(huì)導(dǎo)致返回的輪廓點(diǎn)過(guò)少，從而不能為用戶的決策提供正確有力的支持。為了避免這種現(xiàn)象的發(fā)生，Chee-Yong Chan[6]又提出了top-δ k-支配輪廓查詢，即在k-支配輪廓查詢的基礎(chǔ)上，求得前δ個(gè)支配度最高的k-支配輪廓點(diǎn)。
　　以往的輪廓查詢，包括上述的k-支配輪廓查詢，都是將空間的各維同等對(duì)待，沒(méi)有側(cè)重點(diǎn)。當(dāng)對(duì)空間中的某些維更為看重時(shí)，便引入加權(quán)。給定一個(gè)門(mén)檻ω，當(dāng)點(diǎn)p k-支配點(diǎn)q時(shí)，將點(diǎn)p在這k個(gè)維上的權(quán)值相加，如果超過(guò)ω，就稱點(diǎn)p依據(jù)ω k-支配q。進(jìn)一步拓寬了輪廓查詢的應(yīng)用，很好的滿足了用戶偏好查詢。
　　2.4 top-k輪廓查詢技術(shù)
　　解決輪廓點(diǎn)過(guò)多的問(wèn)題，可以在數(shù)據(jù)集中挑選出支配力最強(qiáng)的前k個(gè)點(diǎn)。在文獻(xiàn)[7]中，給定一排序函數(shù)F，對(duì)所有的點(diǎn)進(jìn)行計(jì)算，返回前k個(gè)函數(shù)值最大的點(diǎn)。此算法的優(yōu)點(diǎn)是用戶可以控制返回結(jié)點(diǎn)的個(gè)數(shù)。但是，如何確定一個(gè)合適的排序函數(shù)F對(duì)用戶來(lái)說(shuō)很困難，而且，無(wú)法確定到底哪些是最重要的對(duì)象，因?yàn)椴煌呐判蚝瘮?shù)對(duì)應(yīng)著不同的返回值。
　　文獻(xiàn)[8-9]提出了高維空間下的top-k 支配查詢的有效優(yōu)化，并滿足了用戶的偏好查詢需求。
　　2.5 其它輪廓查詢技術(shù)
　　輪廓查詢重要理論和實(shí)踐價(jià)值使得相應(yīng)的研究機(jī)構(gòu)投入了大量的人力和物力來(lái)從事該領(lǐng)域的研究，因此一些新的概念和新的思想也不斷出現(xiàn)，它們是根據(jù)輪廓的一些特性，針對(duì)特殊環(huán)境和數(shù)據(jù)的輪廓查詢的變體。如大數(shù)據(jù)集的密集輪廓挖掘、獲得輪廓最佳視圖的方法、半序域的輪廓查詢方法等。下面將分別簡(jiǎn)單介紹。
　　1） 大數(shù)據(jù)集的密集輪廓挖掘
　　在輪廓對(duì)象與其近鄰的距離約束的基礎(chǔ)上提出密集輪廓的概念，并采用采樣修剪法、索引評(píng)估法和基于微簇的方法來(lái)查找大數(shù)據(jù)集的密集輪廓。該方法的提出不僅擴(kuò)展了數(shù)據(jù)庫(kù)查詢中的輪廓操作，而且為數(shù)據(jù)挖掘工作提供了一個(gè)有意義的模式。
　　2） 輪廓最佳視圖
　　在2005年的VLDB會(huì)議上，Jian Pei等人提出了基于決策子空間的獲得輪廓最佳視圖的方法，該方法通過(guò)研究輪廓的語(yǔ)義將整個(gè)空間輪廓計(jì)算擴(kuò)展到子空間的輪廓計(jì)算，并提出Skyey算法來(lái)計(jì)算輪廓組的集合和在每個(gè)子空間輪廓上的對(duì)象集合。
　　3） 半序域的輪廓查詢方法
　　以前的相關(guān)工作都是在全有序域內(nèi)的輪廓計(jì)算方法，半序域的輪廓查詢方法針對(duì)部分有序?qū)傩杂虻妮喞樵冇?jì)算和評(píng)價(jià)問(wèn)題提出了解決方法，對(duì)每個(gè)半序?qū)傩詰?yīng)用一個(gè)近似的區(qū)間表示（整數(shù)屬性對(duì)），產(chǎn)生一個(gè)有效且合理的近似域映射，將查詢空間進(jìn)行轉(zhuǎn)化，在轉(zhuǎn)化后的空間內(nèi)采用現(xiàn)有的索引技術(shù)組織轉(zhuǎn)化后的屬性來(lái)計(jì)算輪廓。
　　3 輪廓更新技術(shù)
　　在數(shù)據(jù)流環(huán)境中，數(shù)據(jù)是不斷變化的，有刪除和插入，這樣，原來(lái)的輪廓對(duì)于變化后的數(shù)據(jù)集就沒(méi)有意義了。為了能對(duì)連續(xù)到達(dá)和終止的動(dòng)態(tài)數(shù)據(jù)進(jìn)行處理，于是出現(xiàn)了輪廓查詢更新技術(shù)。
　　文獻(xiàn)[5]對(duì)這一技術(shù)作了闡述，并提出了Addpoint_Skyline算法和Deletepoint_Skyline算法來(lái)解決輪廓的更新問(wèn)題，使輪廓查詢技術(shù)得到更好的完善。
　　2005年的ICDE會(huì)議上，Xuemin Lin等人提出數(shù)據(jù)流環(huán)境中輪廓的計(jì)算方法，只需考慮一個(gè)覆蓋所有最近元組的滑動(dòng)窗口來(lái)進(jìn)行查詢處理，連續(xù)地監(jiān)控新出現(xiàn)的數(shù)據(jù)，并且不斷更新輪廓，利用數(shù)據(jù)流的輪廓屬性來(lái)提高時(shí)間復(fù)雜度和空間復(fù)雜度。
　　在k-支配輪廓的定義提出之后，Prasad Sriram等人提出了“連續(xù)的k-支配輪廓查詢”，目標(biāo)是通過(guò)將所有的輪廓變化進(jìn)行跟蹤記錄，以實(shí)時(shí)的方式來(lái)連續(xù)報(bào)告有效的輪廓。該技術(shù)最大的亮點(diǎn)在于，對(duì)于到達(dá)時(shí)間AT和終止時(shí)間ET都已知的連續(xù)動(dòng)態(tài)數(shù)據(jù)，為每個(gè)新到達(dá)的數(shù)據(jù)點(diǎn)p添加了變量return_skylinetime來(lái)表示點(diǎn)p成為輪廓點(diǎn)的時(shí)間，也就是當(dāng)前已存在的所有對(duì)p k-支配的點(diǎn)中終止時(shí)間最晚的點(diǎn)的ET。當(dāng)現(xiàn)存的k-支配輪廓中的點(diǎn)p因?yàn)榻K止時(shí)間到達(dá)而離開(kāi)時(shí)，此點(diǎn)只需刪除即可，不需再有其它操作。因?yàn)槟切┍籶 k-支配的點(diǎn)qi，在其return_skylinetime（qi）到達(dá)時(shí)會(huì)自動(dòng)轉(zhuǎn)為輪廓點(diǎn)，省去了煩瑣的比較操作，變得簡(jiǎn)單易行。
　　4 小結(jié)和展望
　　目前，學(xué)術(shù)界已經(jīng)提出很多種輪廓查詢方法，但是如何處理高維空間下的輪廓查詢問(wèn)題是個(gè)難點(diǎn)，也是當(dāng)前的熱點(diǎn)。本文就國(guó)內(nèi)外現(xiàn)有的空間數(shù)據(jù)庫(kù)輪廓查詢的關(guān)鍵技術(shù)進(jìn)行了綜合分析，在這方面還有更多的工作要做，主要有以下幾個(gè)方面。
　　4.1 減少返回的輪廓點(diǎn)
　　輪廓在多標(biāo)準(zhǔn)決策、數(shù)據(jù)挖掘、用戶偏好查詢等方面用處廣泛。隨著空間集和數(shù)據(jù)集的不斷增大，為了能更好的滿足需要，必須從多方面和角度著手，在眾多的信息中返回有效的較小輪廓。
　　4.2 輪廓的更新
　　在實(shí)際應(yīng)用中，輪廓的更新不僅僅是數(shù)據(jù)點(diǎn)的插入和刪除，還應(yīng)該包括空間維數(shù)變化以及若干個(gè)數(shù)據(jù)集合并等對(duì)輪廓更新的影響，這在現(xiàn)實(shí)生活中有著廣泛的用途。
　　4.3 提高查詢效率
　　由于空間對(duì)象的表達(dá)形式復(fù)雜且數(shù)據(jù)量大，如果對(duì)每個(gè)對(duì)象都要檢查其是否滿足要求，需要大量的復(fù)雜的計(jì)算和磁盤(pán)存取操作。因此，如何縮短計(jì)算時(shí)間，提高查詢效率也是將來(lái)的研究方向之一。
　　參考文獻(xiàn)：
　　[1] Borzsonyi S， Kossmann D， Stocker K.The Skyline Operator [C]. Heidelberg， Germany：ICDE， 2001.
　　[2] Tan K， Eng P， Ooi B.Efficient Progressive Skyline Computation [C].Roma， Italy：VLDB， 2001.[3] Chomicki J，Godfrey P，Gryz J，et al. Skyline with Pre-sorting[C].Bangalore， India：The 19th International Conference on Data Engineering，2003.
　　[4] Zhang Z，Guo X，Lu H，et.al.Discovering Strong Skyline Points in High Dimensional Spaces[C]. Bremen，Germany： CIKM zT0xxZs9/MEAnl5o6A0cCw==，2005.
　　[5] Chan C Y， Jagadish H V， Tan K.-L，et al. On High Dimensional Skylines[C].Munich， Germany： EDBT， 2006.
　　[6] Chan C Y， Jagadish H V， Tan K.-L，et al. Finding k-Dominant Skylines in High Dimensional Space[C]. Chicago：SIGMOD， 2006.
　　[7] Fagin R， Lotem A， Naor M.Optimal Aggregation Algorithms for Middleware[C].California，USA：PODS，2001.
　　[8] Lee J， You， S.W Hwang， Ik.C Sohn.Supporting Personalized Top-k Skylines Queries in High-dimensional Web Data[C].Lisboa， Portugal：ACM WIDM，2007.
　　[9] Yiu M L，Mamoulis N.Efficient Processing of Top-k Dominating Queries on Muti-Dimensional Data[C]. Vienna， Austria：VLDB，200