擴展Skyline查詢處理技術研究

第1章 緒論
1.1 研究背景與意義
1.2 Skyline查詢概述
1.2.1 Skyline查詢的定義
1.2.2 Skyline查詢的問題
1.2.3 Skyline查詢的應用
1.3 不確定數據流概述
1.3.1 不確定數據流的應用
1.3.2 不確定數據流的模型
1.3.3 不確定數據流的查詢
1.4 不確定數據流的Skyline查詢
1.4.1 不確定數據流的Skyline查詢的應用
1.4.2 不確定數據流的Skyline查詢的定義
1.4.3 不確定數據流的Skyline查詢的挑戰
1.5 Skyline查詢的挑戰
1.6 主要研究內容
1.7 組織結構
第2章 相關研究
2.1 基於不確定偏好關系的Skyline查詢的研究
2.1.1 基於不確定數據的Skyline查詢的研究
2.1.2 基於不完全數據的Skyline查詢研究
2.1.3 基於不確定偏好關系的Skyline查詢研究
2.1.4 基於數據流環境下的Skyline查詢研究
2.2 並行與分佈式Skyline查詢研究
2.2.1 基於垂直劃分的Skyline查詢研究
2.2.2 基於水平劃分的Skyline查詢研究
2.2.3 基於角度劃分的Skyline查詢研究
2.3 並行Skyline查詢研究
2.3.1 基於並行模型的並行Skyline查詢方法研究
2.3.2 基於空間劃分的並行Skyline查詢方法研究
2.4 基於Skyline團組的Top-k支配查詢研究
2.4.1 Skyline團組查詢研究
2.4.2 Top-k支配查詢研究
2.4.3 其他排序方法研究
2.5 數據流Skyline的查詢研究
2.5.1 確定性數據流的Skyline查詢研究
2.5.2 不確定數據流的Skyline查詢研究
2.6 n-of-N Skyline查詢研究
2.6.1 確定性n-of-N Skyline查詢研究
2.6.2 不確定n-of-N Skyline查詢研究
2.7 k-支配Skyline查詢研究
2.7.1 數據集的k-支配Skyline查詢
2.7.2 數據流的k-支配Skyline查詢
2.8 本章小結
第3章 基於不確定偏好的Skyline查詢
3.1 引言
3.2 問題定義
3.3 基於前綴的k層吸收技術
3.3.1 算法的理論基礎
3.3.2 算法理論基礎的不完整性
3.3.3 算法正確性的完整證明
3.4 Skyline概率計算
3.4.1 Parallel-sky算法
3.4.2 不相交集合概率計算
3.4.3 時間覆雜度分析
3.5 動態算法
3.5.1 添加算法
3.5.2 刪除算法
3.6 Parallel-all算法
3.7 實驗
3.7.1 Parallel-sky算法性能分析
3.7.2 添加與刪除算法的性能分析
3.8 本章小結
第4章 Skyline團組的並行計算方法
4.1 引言
4.2 問題定義
4.3 計算Skyline層次
4.3.1 並行計算方法
4.3.2 基於元組的分割和排序
4.3.3 Skyline層次的數據結構
4.3.4 與已知的Skyline層次相比較
4.3.5 與同一分塊中的元組比較
4.3.6 更新全局Skyline層次
4.3.7 實例分析
4.3.8 時間覆雜度分析
4.3.9 並行算法總結
4.4 查找Skyline團組
4.4.1 構建cell
4.4.2 並行計算Skyline團組
4.4.3 時間覆雜度分析
4.5 實驗
4.5.1 總體性能分析
4.5.2 計算Skyline層次性能分析
4.5.3 計算Skyline團組性能分析
4.6 本章小結
第5章 基於Skyline團組的Top-k支配查詢
5.1 引言
5.2 問題定義
5.3 Skyline團組上的TKD查詢
5.3.1 基於排列的Skyline團組
5.3.2 基於SUM函數的Skyline團組
5.3.3 基於MAX函數的Skyline團組
5.3.4 時間覆雜度分析
5.3.5 基於MIN函數的Skyline團組
5.4 位圖索引方法
5.4.1 計算團組的分數
5.4.2 位圖索引壓縮
5.5 實驗分析
5.5.1 Skyline團組的輸出大小
5.5.2 位圖索引壓縮比例
5.5.3 不同Skyline團組定義下的實驗分析
5.5.4 不同數據分佈情況下的實驗分析
5.6 本章小結
第6章 基於區間樹刺探的並行n-of-N Skyline查詢方法
6.1 基本概念與問題描述
6.1.1 基本概念
6.1.2 問題描述
6.2 並行不確定n-of-N查詢模型設計
6.2.1 並行n-of-N查詢框架
6.2.2 窗口劃分與流數據映射策略
6.2.3 查詢區間編碼策略
6.2.4 基於疊代的處理過程
6.3 並行不確定n-of-N查詢算法設計
6.3.1 窗口劃分算法與流數據映射算法
6.3.2 並行不確定n-of-NSkyline查詢處理算法
6.3.3 查詢區間計算算法
6.3.4 候選集合更新算法
6.3.5 刺探查詢算法
6.4 實驗結果與分析
6.4.1 實驗環境設置
6.4.2 全局窗口長度對性能的影響
6.4.3 窗口滑動粒度對性能的影響
6.4.4 流數據的維度對性能的影響
6.4.5 計算節點數目對性能的影響
6.4.6 不同概率閾值對性能的影響
6.4.7 不同查詢範圍對性能的影響
6.5 本章小結
第7章 基於支配能力索引的並行k-支配Skyline查詢方法
7.1 基本概念與問題描述
7.1.1