本文關鍵詞：多環(huán)境下Skyline計算問題研究，，由筆耕文化傳播整理發(fā)布。

【摘要】：Skyline計算,也稱輪廓查詢,本質是一個多目標優(yōu)化問題,目的旨在發(fā)現(xiàn)給定數(shù)據(jù)集中所有用戶可能感興趣的信息。作為一種基礎的數(shù)據(jù)操作方法,Skyline計算在多目標決策支持系統(tǒng)、導航系統(tǒng)、環(huán)境監(jiān)控、數(shù)據(jù)挖掘等領域有著廣泛的應用。因此,自2001年被提出以來,Skyline計算研究一直是數(shù)據(jù)庫和數(shù)據(jù)挖掘領域許多研究者關注的焦點。Skyline查詢算法的設計主要受三個因素影響：數(shù)據(jù)特征、運行環(huán)境和設計目標。數(shù)據(jù)特征包含數(shù)據(jù)的生成方式、存儲結構、空間維度及規(guī)模等信息。運行環(huán)境指執(zhí)行查詢操作的計算和網(wǎng)絡環(huán)境,分集中式和分布式兩種。設計目標則包括執(zhí)行效率、漸進性、公平性、友好性等指標。三種因素的交織造成了Skyline計算環(huán)境的復雜多樣性。目前,已有多種Skyline算法被相繼提出,涵蓋了靜態(tài)和動態(tài)數(shù)據(jù)、固定和移動對象、集中和分布式系統(tǒng)、低維和高維數(shù)據(jù)空間等不同環(huán)境。不過,隨著近年來云計算、傳感網(wǎng)、大數(shù)據(jù)、移動互聯(lián)等技術的飛速發(fā)展,新的應用環(huán)境和需求不斷涌現(xiàn),同時也對以往相對成熟的環(huán)境帶來了影響。面對這種情況,現(xiàn)有算法已難以適應發(fā)展的需要。本文針對多種環(huán)境下的Skyline計算問題進行了研究與探索,主要研究點包括：集中式靜態(tài)數(shù)據(jù)集下算法效率的提升問題；移動環(huán)境中基于位置依賴的連續(xù)查詢問題；分布式架構下的Skyline計算問題和集中式靜態(tài)數(shù)據(jù)集上的反Skyline查詢問題。主要貢獻如下：(1)在集中式靜態(tài)數(shù)據(jù)集環(huán)境下,為提升大規(guī)模、高維數(shù)據(jù)集的Skyline計算效率,從算法自身和計算平臺等方面考慮,提出了兩種基于多核并行技術的Skyline算法。第一種算法采用預排序策略,將數(shù)據(jù)集按照任意指定維度排序,然后劃分為多個子集進行并行化處理。第二種算法在第一種算法的基礎上,首先改進了預排序策略,然后通過選擇樞軸點,將數(shù)據(jù)空間劃分為若干區(qū)域,利用區(qū)域支配關系,減少數(shù)據(jù)對象之間的支配測試次數(shù),進一步提高了效率。兩種算法處理過程簡潔,具有較好的漸進性、用戶友好型和可擴展性。實驗結果表明,對于規(guī)模較大、維數(shù)較高的數(shù)據(jù)集,計算效率有較大提升。(2)在移動環(huán)境下,針對查詢點快速移動時連續(xù)、高效輸出指定搜索區(qū)域Skyline集合的問題,結合數(shù)據(jù)流技術,提出一種基于位置依賴的連續(xù)查詢算法。首先使用R-樹快速更新查詢數(shù)據(jù),然后利用兩次連續(xù)計算時搜索區(qū)域的重疊性構造被動數(shù)據(jù)流,并對新增和失效數(shù)據(jù)分別進行處理,最終連續(xù)輸出Skyline集合。由于充分利用了已有計算結果,算法計算量有大幅下降。實驗結果表明,該算法特別適合計算頻度要求較高的場合,與基于網(wǎng)格索引的算法相比,時間效率隨著數(shù)據(jù)集規(guī)模的增大提升明顯。(3)在分布式環(huán)境下,針對層次化拓撲結構對等網(wǎng),研究了分布式數(shù)據(jù)流環(huán)境下的Skyline計算問題,提出了一種由下往上分層匯聚結果的算法。對下層網(wǎng)絡,通過構造路由樹重建了的路由結構,保證在每一跳均能對傳輸?shù)臄?shù)據(jù)進行有效過濾,降低了計算和通信開銷;對上層網(wǎng)絡,采用保序映射的方式將多維數(shù)據(jù)轉換到一維空間并排序,然后依據(jù)上層網(wǎng)絡節(jié)點標識符的大小順序計算,保證了算法的漸進性和效率。實驗結果表明,算法具有較好的可擴展性和較小的通信代價。(4)針對應用需求的變化,研究了集中式靜態(tài)數(shù)據(jù)集下的反Skyline計算問題,以經(jīng)典算法BBRS為基礎,提出一種改進算法。預先為數(shù)據(jù)集建立R-樹索引,然后以查詢點為中心將數(shù)據(jù)空間分割為若干獨立區(qū)域,使用一種簡單的窗口查詢方法并利用多核并行技術加速算法運行。實驗結果表明,相對于傳統(tǒng)的算法,算法性能有一定提升。
【關鍵詞】：輪廓查詢 多核并行 位置服務 層次化對等網(wǎng) 反輪廓查詢
【學位授予單位】：西安電子科技大學
【學位級別】：博士
【學位授予年份】：2015
【分類號】：TP311.13
【目錄】：

• 摘要5-7
• ABSTRACT7-12
• 符號對照表12-13
• 縮略語對照表13-17
• 第一章 緒論17-29
• 1.1 研究背景17-19
• 1.2 Skyline計算基本概念19-22
• 1.2.1 形式化定義19-20
• 1.2.2 基本算法BNL20-21
• 1.2.3 算法評價標準21-22
• 1.3 研究現(xiàn)狀22-26
• 1.3.1 集中式環(huán)境下的Skyline計算22-24
• 1.3.2 數(shù)據(jù)流環(huán)境下的Skyline計算24-25
• 1.3.4 分布式環(huán)境下的Skyline計算25-26
• 1.3.5 其它類型Skyline計算26
• 1.4 挑戰(zhàn)性問題26-27
• 1.5 研究內容及貢獻27-28
• 1.6 論文章節(jié)安排28-29
• 第二章 多核并行Skyline計算29-55
• 2.1 引言29
• 2.2 背景知識29-34
• 2.2.1 相關工作29-30
• 2.2.2 多核并行計算30-33
• 2.2.3 Skeletal并行編程模型33-34
• 2.3 采用預排序策略的并行Skyline算法34-41
• 2.3.1 預排序策略34-35
• 2.3.2 算法流程35-36
• 2.3.3 詳細實現(xiàn)36-38
• 2.3.4 算法分析38-39
• 2.3.5 實驗驗證39-41
• 2.4 采用樞軸選擇策略的并行Skyline算法41-53
• 2.4.1 樞軸點及區(qū)域支配41-43
• 2.4.2 算法流程43
• 2.4.3 詳細實現(xiàn)43-46
• 2.4.5 算法分析46-47
• 2.4.6 實驗及分析47-53
• 2.5 小結53-55
• 第三章 移動環(huán)境中的Skyline計算55-69
• 3.1 引言55
• 3.2 問題描述55-56
• 3.3 背景知識56-58
• 3.3.1 位置服務56-57
• 3.3.2 數(shù)據(jù)流檢索57-58
• 3.4 LDCS算法58-63
• 3.4.1 搜索區(qū)域更新58-60
• 3.4.2 數(shù)據(jù)流的形成60-61
• 3.4.3 計算Skyline61-63
• 3.5 實驗及性能分析63-67
• 3.5.1 仿真數(shù)據(jù)測試64-65
• 3.5.2 真實數(shù)據(jù)測試65-67
• 3.6 小結67-69
• 第四章 分布式環(huán)境中的Skyline計算69-87
• 4.1 引言69
• 4.2 背景知識69-74
• 4.2.1 P2P網(wǎng)絡69-70
• 4.2.2 層次化P2P網(wǎng)絡70-73
• 4.2.3 相關工作73-74
• 4.3 數(shù)據(jù)流環(huán)境下的連續(xù)Skyline計算74-85
• 4.3.1 問題定義74-75
• 4.3.2 基本思想75
• 4.3.3 樹形路由結構的建立75-76
• 4.3.4 群內Skyline計算76-79
• 4.3.5 上層網(wǎng)絡的Skyline計算79-81
• 4.3.6 實驗及分析81-85
• 4.4 小結85-87
• 第五章 靜態(tài)數(shù)據(jù)集上的反Skyline計算87-103
• 5.1 引言87
• 5.2 背景知識87-89
• 5.2.1 反Skyline概念87-89
• 5.2.2 相關工作89
• 5.3 BBRS算法89-91
• 5.4 RSBP算法91-96
• 5.4.1 算法思想92-93
• 5.4.2 R-樹的建立93
• 5.4.3 并行計算93-96
• 5.5 算法分析96-97
• 5.6 實驗及分析97-100
• 5.7 小結100-103
• 第六章 總結與展望103-105
• 6.1 本文工作總結103-104
• 6.2 研究展望104-105
• 參考文獻105-113
• 致謝113-115
• 作者簡介115

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 李志寬;;基于Skyline的企業(yè)總圖3維信息系統(tǒng)[J];測繪與空間地理信息;2009年02期

2 向劍平;鄭皎凌;;Skyline計算在多維排序問題上的分析[J];太原師范學院學報(自然科學版);2009年02期

3 黎剛;徐潔;陳踴;;基于Skyline的太湖流域水環(huán)境三維GIS系統(tǒng)設計與實現(xiàn)研究[J];現(xiàn)代商貿(mào)工業(yè);2009年23期

4 黃丙湖;韓李濤;陳龍;;基于Skyline視頻監(jiān)控系統(tǒng)研究[J];地理信息世界;2010年03期

5 袁昱緯;;基于Skyline的鐵路車站三維信息平臺實現(xiàn)研究[J];辦公自動化;2010年24期

6 周美娟;俞強;楊詩華;黃麗;;基于Skyline的公安三維GIS展現(xiàn)應用系統(tǒng)[J];測繪科學;2011年03期

7 張露露;陳宜金;;基于Skyline的數(shù)字礦山三維綜合監(jiān)測系統(tǒng)的應用研究[J];測繪信息與工程;2011年05期

8 鄧瑞鵬;王意潔;李小勇;王媛;;基于數(shù)據(jù)垂直劃分的高效并行Skyline查詢[J];計算機工程;2012年14期

9 雷浩川;;基于Skyline的三維場景發(fā)布技術分析[J];測繪通報;2012年S1期

10 班鵬新;王元珍;朱虹;張勇;;面向標記安全數(shù)據(jù)庫的Skyline立方體算法[J];華中科技大學學報(自然科學版);2013年02期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 施朗;;淺談Skyline平臺建立三維網(wǎng)絡地理信息系統(tǒng)的優(yōu)缺點[A];2009全國測繪科技信息交流會暨首屆測繪博客征文頒獎論文集[C];2009年

2 葛洪濤;;基于Skyline的三維地理信息系統(tǒng)研究與設計[A];第二屆“測繪科學前沿技術論壇”論文精選[C];2010年

3 陳秉政;;基于Skyline的三維管線系統(tǒng)的實現(xiàn)[A];第十四屆華東六省一市測繪學會學術交流會論文集[C];2012年

4 雷浩川;;基于Skyline的三維場景發(fā)布技術分析[A];第四屆“測繪科學前沿技術論壇”論文精選[C];2012年

5 雷明;張巍;陳利娟;;基于Skyline的水資源三維地理信息系統(tǒng)的設計與實現(xiàn)[A];水與水技術（第3輯）[C];2013年

6 劉劍;張應裕;王東博;周正玉;余建平;;基于Skyline的數(shù)字三維國土資源輔助決策系統(tǒng)設計與研發(fā)[A];廣東省測繪學會第九次會員代表大會暨學術交流會論文集[C];2010年

7 劉莉;蔡軍衛(wèi);田中彬;馬彥;;一種基于移動Agent的分布式Skyline查詢算法[A];2007年全國開放式分布與并行計算機學術會議論文集(下冊)[C];2007年

8 張光偉;羌鑫林;趙建崇;;SketchUp配合下的Skyline快速三維運用[A];江蘇省測繪學會2007年學術年會論文集[C];2008年

9 張光偉;羌鑫林;趙建崇;;SketchUp配合下的Skyline快速三維運用[A];江蘇省測繪學會2007'學術年會論文集[C];2008年

10 趙連鈞;;基于Skyline的高速公路3D GIS系統(tǒng)開發(fā)[A];中國公路學會計算機應用分會2010年學術年會論文集[C];2010年

中國重要報紙全文數(shù)據(jù)庫 前1條

1 慕清;電子地圖熱點詞匯[N];計算機世界;2007年

中國博士學位論文全文數(shù)據(jù)庫 前3條

1 黃伯虎;多環(huán)境下Skyline計算問題研究[D];西安電子科技大學;2015年

2 孫圣力;數(shù)據(jù)流上Skyline查詢處理算法研究[D];復旦大學;2008年

3 周紅福;基于索引的Skyline算法研究[D];復旦大學;2007年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 吳大猛;延遲容忍網(wǎng)絡中的Skyline查詢研究[D];寧波大學;2014年

2 高天宇;非Skyline的Web服務提升方法研究與實現(xiàn)[D];昆明理工大學;2015年

3 蔡文明;高效關鍵詞Skyline查詢算法研宄[D];浙江大學;2015年

4 代博;無線傳感數(shù)據(jù)的Skyline查詢算法研究[D];大連海事大學;2015年

5 王雪菲;基于維度偏好的Skyline查詢結果精簡算法[D];大連理工大學;2015年

6 趙越;不確定數(shù)據(jù)流的分布并行Skyline查詢處理技術研究[D];國防科學技術大學;2013年

7 李佼;基于Skyline的三維GIS開發(fā)關鍵技術研究[D];華東師范大學;2009年

8 胡清蘭;路網(wǎng)中基于位置的多源Skyline查詢研究[D];華南理工大學;2012年

9 宋世凱;基于Skyline的城市三維地理信息系統(tǒng)的設計與研究[D];河北師范大學;2012年

10 黃子晴;Skyline查詢處理在文獻檢索排序中的應用研究[D];西安電子科技大學;2012年

  本文關鍵詞：多環(huán)境下Skyline計算問題研究，由筆耕文化傳播整理發(fā)布。

本文編號：295009