Skyline擴展查詢研究.pdf

1、Skyline是指數(shù)據(jù)集中不被其他點支配的所有點的集合。支配是指在數(shù)據(jù)集中，一個數(shù)據(jù)對象的每一維值都不比另一數(shù)據(jù)對象相對應維值差，而且必須至少有一個維值比另一數(shù)據(jù)對象好。維度上的好和差沒有統(tǒng)一的定義，可根據(jù)用戶的選擇和偏好、經(jīng)驗知識來決定。由于Skyline查詢計算在數(shù)據(jù)倉庫、個性化推薦、數(shù)據(jù)庫可視化、城市導航系統(tǒng)等領域的良好應用前景，使其成為當前數(shù)據(jù)庫界研究的熱點之一，受到了學術界和工業(yè)界的廣泛關注。作為對Skyline擴展查詢進行研

2、究的開始和基礎，本文首先對Skyline查詢目前的研究現(xiàn)狀進行了綜述。全面分析了在集中靜態(tài)環(huán)境下利用空間索引或編碼技術快速進行Skyline計算的各種算法及其變形；進而深入探討和分析了為了滿足人們各種不同查詢需求而提出的多種Skyline查詢方案，包括子空間上的Skyline查詢、動態(tài)Skyline查詢、K-支配Skyline查詢和約束Skyline查詢等；最后詳細分析了在不同應用環(huán)境下例如Web信息系統(tǒng)、數(shù)據(jù)流環(huán)境、微觀經(jīng)濟學等中的S

3、kyline計算改進方案。
　　 本文工作主要集中在Skyline查詢問題中的三個擴展查詢，分別是面向雙方?jīng)Q策的Skyline推薦問題，Skyline距離問題以及負載均衡的分布式Skyline查詢問題。以往相關的Skyline查詢研究工作都集中在單方?jīng)Q策的研究上，即決策方在一個給定數(shù)據(jù)集上進行Skyline查詢。然而在現(xiàn)實應用中，決策過程常常是多方參與的，例如企業(yè)招聘，學校招生，企業(yè)并購等等，雙方都希望在滿足一定約束的情況下選擇

4、最優(yōu)的對象。本文用求職者和工作職位為實例，探討和研究系統(tǒng)如何快速回答雙方提出的Skyline擴展查詢問題。我們用Skyline為決策雙方的競爭性選擇進行了建模，首先為用戶可能提出的多種需求定義了一系列靈活的Skyline擴展查詢方案，然后為這些擴展查詢設計了基于共享計算思想的批處理高效算法，最后用一系列實驗證明了這些算法的有效性。
　　 Skyline在多目標決策問題中的應用已經(jīng)被廣泛認可，大多已有工作關注于如何高效計算給定數(shù)據(jù)

5、集中的Skyline對象集合。然而通常情況下，Skyline集合是全體數(shù)據(jù)中的一個相對較小的集合。在本文中我們轉(zhuǎn)換了視角，關注那些大量非Skyline點的需求，提出一個非常新穎的問題：一個數(shù)據(jù)對象距離Skyline有多遠?我們提出了一種新穎的度量：Skyline距離，指在給定的代價函數(shù)下使一個數(shù)據(jù)對象成為Skyline的最小代價。Skyline距離可被視為是一個多維競爭性度量，可用于在推薦系統(tǒng)中評價不同的方案。然而計算Skyline距離

6、并不容易，無法通過擴展已有的Skyline計算方法來獲得解決方案。我們設計了三個有效計算Skyline距離的算法。首先基于對數(shù)據(jù)和問題的直觀觀察，設計了動態(tài)規(guī)劃算法；其次基于若干的理論證明，提出一個排序-投影算法，算法遞歸地將高維空間分解為多個低維空間，降低了計算難度；然后基于空間劃分思想設計和實現(xiàn)了一個能高效裁剪搜索空間的空間劃分算法；最后通過理論和實驗證明了以上算法的有效性。
　　 多目標決策問題的應用場景往往是交互式的，用

7、戶需要對數(shù)據(jù)集進行不斷的探查，因此要求系統(tǒng)具有較高的響應速度，但目前數(shù)據(jù)在往海量化、高維化的方向發(fā)展，單機算法常常不能達到實際應用的要求。隨著并行計算環(huán)境越來越普遍，擴展Skyline查詢到大規(guī)模并行計算環(huán)境中是關乎Skyline計算應用性的一個迫切問題。目前已有研究主要關注如何減少復雜網(wǎng)絡環(huán)境中的網(wǎng)絡通信代價，而沒有考慮如何在多處理器快速互聯(lián)的高性能集群中更好地使用高帶寬特性來提高Skyline計算的性能。本文提出了高帶寬分布式環(huán)境下