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