Skyline查詢在多目標決策、數據庫可視化等領域具有重要的應用價值,作為Skyline查詢的一種重要變體,反Skyline查詢同樣具有重要的應用價值。具有不確定性特點的數據流在現實世界中廣泛存在著,因而不確定數據流上的反Skyline查詢研究具有重要意義。但現有不確定數據流上的反Skyline查詢算法存在時間性能不高以及無法應對某些苛刻環(huán)境等不足,本文針對這些不足提出了兩種新算法。本文主要的工作及創(chuàng)新點為:(1)設計與實現了一種新的不確定數據流上的反Skyline查詢單機算法RSUDS。RSUDS算法基于網格劃分思想以及Z–curve設計了一種新的索引結構,并在該索引結構的基礎上RSUDS算法采用了若干啟發(fā)式優(yōu)化策略,這些方法的使用能夠最大限度地減少對象之間關系測試的次數,并最終加快查詢的響應速度。(2)針對單機算法在處理滑動窗口過大、高維度等情況下實時響應性能不高的問題,設計與實現了不確定數據流上的反Skyline查詢并行算法PRSUDS。PRSUDS算法采用基于角度劃分的分發(fā)策略將處理任務分配至各并行節(jié)點進行處理;而在各并行計算節(jié)點則采用RSUDS算法中的網格索引結構以及啟發(fā)式策略對局部處理進行優(yōu)化。(3)通過在人工數據集上的大量實驗對RSUDS算法和PRSUDS算法的性能進行全面的驗證。實驗結果表明RSUDS算法比現有的算法具有更好的時間性能;而PRSUDS算法能夠更好地應對滑動窗口過大以及高維度等情況。因此本文的研究成果能夠滿足實際應用的需求。
【學位單位】：南京航空航天大學
【學位級別】：碩士
【學位年份】：2015
【中圖分類】：TP311.13
【文章目錄】：
摘要
ABSTRACT
縮略詞
第一章 緒論
    1.1 研究背景及意義
    1.2 Skyline查詢研究現狀
    1.3 不確定數據流上反Skyline查詢面臨的挑戰(zhàn)
    1.4 論文研究內容及組織結構
        1.4.1 論文研究內容
        1.4.2 論文組織結構
第二章 相關技術理論研究
    2.1 Skyline查詢研究
        2.1.1 確定Skyline查詢
        2.1.2 不確定Skyline查詢
        2.1.3 反Skyline查詢
    2.2 不確定數據流研究
        2.2.1 不確定數據模型
        2.2.2 流數據管理技術
    2.3 本章小結
第三章 不確定數據流上的反Skyline查詢算法
    3.1 問題定義
    3.2 RSUDS算法設計
        3.2.1 算法框架
        3.2.2 索引結構
        3.2.3 優(yōu)化策略
    3.3 RSUDS算法實現及描述
    3.4 本章小結
第四章 并行算法的設計與實現
    4.1 并行處理概述
    4.2 PRSUDS算法
        4.2.1 分發(fā)策略
        4.2.2 并行處理框架
        4.2.3 局部處理與優(yōu)化
    4.3 算法分析
    4.4 本章小結
第五章 實驗與分析
    5.1 實驗設置
    5.2 RSUDS算法驗證
        5.2.1 RSUDS算法時間性能測試
        5.2.2 RSUDS算法空間性能測試
    5.3 PRSUDS算法驗證
        5.3.1 PRSUDS算法時間性能測試
        5.3.2 并行節(jié)點負載測試
    5.4 本章小結
第六章 總結與展望
    6.1 總結
    6.2 展望
參考文獻
致謝
在學期間的研究成果及發(fā)表的學術論文

【相似文獻】

相關期刊論文 前10條

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

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

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

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

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

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

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

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

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

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

相關博士學位論文 前3條

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

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

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

相關碩士學位論文 前10條

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

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

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

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

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

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

7 孫藝斌;基于相似度的傳感網Skyline查詢處理研究[D];湖南師范大學;2015年

8 劉楊;基于3dsMax及Skyline的城市景觀模型構建研究[D];東華理工大學;2015年

9 王倩;大規(guī)模環(huán)境下基于用戶的服務選擇方法研究[D];南京郵電大學;2015年

10 張建榮;不確定數據流上的反Skyline查詢研究[D];南京航空航天大學;2015年

本文編號：2865592