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

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

2、究的開始和基礎(chǔ)，本文首先對(duì)Skyline查詢目前的研究現(xiàn)狀進(jìn)行了綜述。全面分析了在集中靜態(tài)環(huán)境下利用空間索引或編碼技術(shù)快速進(jìn)行Skyline計(jì)算的各種算法及其變形；進(jìn)而深入探討和分析了為了滿足人們各種不同查詢需求而提出的多種Skyline查詢方案，包括子空間上的Skyline查詢、動(dòng)態(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ì)算改進(jìn)方案。
　　 本文工作主要集中在Skyline查詢問(wèn)題中的三個(gè)擴(kuò)展查詢，分別是面向雙方?jīng)Q策的Skyline推薦問(wèn)題，Skyline距離問(wèn)題以及負(fù)載均衡的分布式Skyline查詢問(wèn)題。以往相關(guān)的Skyline查詢研究工作都集中在單方?jīng)Q策的研究上，即決策方在一個(gè)給定數(shù)據(jù)集上進(jìn)行Skyline查詢。然而在現(xiàn)實(shí)應(yīng)用中，決策過(guò)程常常是多方參與的，例如企業(yè)招聘，學(xué)校招生，企業(yè)并購(gòu)等等，雙方都希望在滿足一定約束的情況下選擇

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

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

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

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