skyline

Skyline一個經典的例子 如圖所示：假設去Nassau海灘旅遊，想找一個既便宜又靠近海灘的旅館，一般情況下越靠近海灘的旅館價格越高，所以不能返回一個最好的結果，只能返回一些用戶可能感興趣的旅館，這些旅館在價格和距離兩個方面都不比其它旅館差，這些不被支配的旅館就是Skyline。

Kung 在文獻中針對二維或三維數據提出了一種查詢複雜度為O(nlog2n)的演演算法，針對大於三維的數據，提出了查詢複雜度為O(n(log2n)d−2)的演演算法。後來,Bentley 在假定各維數據分佈獨立的情況下，提出了人們期望的線性查詢演演算法。所有這些研究都假定數據集比較小，可以放入內存，所提出的演演算法也都是內存演演算法.

資料庫領域的研究人員對Skyline 查詢的研究始於2001 年，最早由Borzsonyi 等人提出。主要關注在數據量很大、無法放入內存的情況下，如何處理Skyline 查詢.

最近幾年，對Skyline 查詢的研究大體上可以分為4 類:

1) 單Skyline 查詢處理演演算法。該類演演算法假定所有的Skyline 對象都處在某一個特定的D-維空間中，返回的結果集合只有1 個。根據查詢過程中是否藉助索引，單Skyline 查詢處理演演算法又分為兩類：不帶索引演演算法和帶索引演演算法。前者假定沒有任何索引存在，通過掃描整個數據集(至少1 次)來返回Skyline 查詢的結果；後者通過引入適當的索引結構，如R-樹，來提高查詢處理的效率.

2) 多Skyline 查詢處理演演算法。針對現實生活中不同的用戶可能有不同的興趣和偏好，需要在不同的子空間中處理Skyline 查詢的需求，數據倉庫和OLAP 領域的研究者對在不同子空間上進行Skyline 查詢的研究產生了濃厚的興趣，提出了SKYCUBE的概念.SKYCUBE 借用傳統的Data Cube 的多維層次結構，提出了有效的同時計算多個Skyline 查詢的思想。該類演演算法主要包含針對SKYCUBE 的計算、維護和壓縮等.

3) 不同應用環境下的Skyline 查詢處理。主要包括Web 信息系統中的Skyline 查詢處理、P2P 網路環境下的Skyline 查詢處理、數據流環境下的Skyline 查詢處理、移動的公路網路環境下的Skyline 查詢處理等.

4) Skyline 查詢處理問題的擴展。例如，文獻中首次擴展了空間資料庫中不同數據點之間的控制關係的概念，將其用於經濟學框架下的商業分析，提出了控制關係分析的概念；文獻針對高維空間下出現在Skyline 查詢結果中的點非常多，從而導致該結果在很多時候對用戶失去意義的問題，提出了k-Dominant 的概念，等等.

可以看出,Skyline 的查詢處理問題已經引起了國內外研究者的高度重視，近幾年，在SIGMOD,VLDB,KDD,PODS,ICDE,ICDM等相關的高水平國際會議上發表了許多高質量的論文，展示出大量的研究成果。在TKDE,TODS 等期刊中也發表了大量成果。然而目前，國內和國際上還沒有將Skyline 查詢處理的發展情況、核心技術和研究成果進行整體上的介紹。鑒於Skyline 查詢處理在多規則決策應用方面的重要價值和在實時在線服務方面的良好應用前景，為了捕捉Skyline 查詢處理的發展動態，對Skyline 查詢處理研究有一個總體上的把握，促進國內迅速跟上國際研究的步伐，綜述這方面的工作十分有意義.