Rectilinear Range Query Processing on SpatialHadoop Platform

面對全球每年資料的成長，大數據(Big Data)近年來已經成為新興的議題，其中，具有地理空間特性的大數據成為最吸引目光的焦點之一，如何有效率地查詢和處理巨量空間大數據資料仍是一大課題。儘管使用雲端Hadoop/MapReduce技術來平行運算數據，在一定程度上能提高運算效能，但如果當數據量非常大的時候，對全部數據進行運算，所需的時間仍然比較長，無法滿足實際應用的需求。對於空間數據來說，將地理相近的數據放置於相同檔案區塊(Blocks)，並進行空間索引才能快速找出空間數據，由於雲端檔案系統HDFS的特性，使得空間資料的索引和查詢相對困難，因此本論文採用SpatialHadoop平台來建置空間資料庫。 空間資料庫中，行政區域，如國家、縣市或其他地理空間等是以多邊形表示，然而，SpatialHadoop並不支援多邊形查詢；一個資料點是否位在多邊形內的問題，傳統是以ray casting演算法判斷，但相較於矩形的判斷，其計算複雜度高。直覺的解決方法是採取先粗略過濾再精煉(filtering-refinement)的策略，以矩形過濾資料，再以ray casting判斷，但當地理空間較為複雜，過濾資料出來的資料可能還是很多；因此，本論文針對大數據之多邊形查詢問題，提出以直交多邊形(Rectilinear Polygon)涵蓋多邊形，並切割直交多邊形成多個矩形的方法，透過矩形查詢的方式初步過濾出候選資料點，再針對小量的候選資料點進行判斷ray casting計算，此外，我們進一步將矩形分成inside和cross兩類，因僅須對cross矩形中的候選資料點進行精煉，因此可以進一步減少多邊形查詢的計算時間。 為驗證我們的設計，我們以多個實際資料進行實驗，根據實驗結果證實，我們的方法在Hadoop或SpatialHadoop平台上，計算時間都明顯少很多，當多邊形越複雜時，我們所提出的直交多邊形查詢方法效率更好。中文摘要 i 誌謝辭 ii 目錄 iii 表目次 iv 圖目次 v 第1章 緒論 1 1.1 大數據發展狀況 2 1.2 大數據問題提出與研究目的 3 1.3 論文的研究意義 3 1.4 論文研究內容和結構 3 1.4.1 論文研究內容 3 1.4.2 論文章節架構 4 第2章 SpatialHadoop相關技術與理論基礎 5 2.1 SPATIALHADOOP: A MAPREDUCE FRAMEWORK FOR SPATIAL DATA 5 2.1.1 SpatialHadoop Architecture 6 2.1.2 Storage Layer: Indexing 7 2.1.3 MapReduce Layer: Spatial File Splitter / Spatial Record Reader 11 2.2 大規模存儲與處理技術 14 2.2.1 Hadoop Data Chunks 14 2.2.2 SpatialHadoop Data Chunks 15 2.3 平行計算模型MAPREDUCE: SIMPLIFIED DATA PROCESSING ON LARGE CLUSTERS 16 2.4 RAY-CASTING ALGORITHM 17 第3章 空間數據處理Rectilinear Range Query Processing 18 3.1 大數據存在的問題 19 3.1.1 大規模空間數據建置效能的主要因素 19 3.2 RECTILINEAR POLYGON處理空間區域數據問題架構 20 3.3 大數據對空間技術架構的策略 21 3.3.1 空間最小邊界範圍限定 22 3.3.2 空間數據網格切割 22 3.3.3 Rectilinear Polygon 23 3.3.4 平行計算空間數據多區域處理MLI 24 3.3.5 合併輪廓相鄰網格MCG 25 3.3.6 Multiple Rectangle Distributed Cache 29 3.4 RECTANGLE PARTITION平行演算法 30 3.5 PRACTICAL APPLICATION: UNITED STATES GEOLOGICAL SURVEY 33 第4章 平行計算空間網格概率Top-K 34 4.1 大數據中的空間數據潛在價值 34 4.2 平行處理空間網格概率TOP-K 35 4.2.1 空間數據網格概率 35 4.2.2 平行計算空間數據網格概率Top-K 36 4.3 GEOSPATIAL GRID PROBABILITY TOP-K平行演算法 37 第5章 實驗及其結果分析 38 5.1 實驗環境與資料 38 5.2 實驗結果與討論 42 5.2.1 Impact of Spatial Density 43 5.2.2 Impact of Query Area 44 5.2.3 Impact of Grid Size 48 5.2.4 Impact of Multiple Set 49 第6章 結論 50 參考文獻 5