Skyline擴(kuò)展查詢研究.pdf

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

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

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

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

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

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

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