隨著物聯(lián)網(wǎng)技術(shù)和基于位置的服務（LBS）的快速發(fā)展,位置感知服務在日常生活中發(fā)揮著越來越重要的作用�；谖锫�(lián)網(wǎng)技術(shù)和LBS采集到的數(shù)據(jù)通常帶有時間域和空間域特性,稱之為時空數(shù)據(jù)。連續(xù)到達的時空數(shù)據(jù)稱為時空數(shù)據(jù)流,它具有實時性、無限性、突發(fā)性等特點。對于流式時空數(shù)據(jù)需要新的查詢處理技術(shù)來處理,傳統(tǒng)空間索引的批量裝載方法,如R樹,不適用于時空數(shù)據(jù)流場景,他們通常只考慮靜態(tài)數(shù)據(jù)或批量更新。然而,對于時空流數(shù)據(jù),現(xiàn)有的批量構(gòu)造方法不能實時或近實時處理。本文基于分布式索引技術(shù)和R樹批量裝載技術(shù),提出了一種面向時空數(shù)據(jù)流的分布式索引。該索引采用時間窗口機制將時空數(shù)據(jù)流切分為連續(xù)的時間窗口處理單元,然后使用針對時空數(shù)據(jù)流優(yōu)化的R樹批量裝載算法為每個時間窗口構(gòu)建一棵內(nèi)層R樹,將每個時間窗口的時間信息和對應的R樹根節(jié)點信息組成<key,value>元組,用于構(gòu)建外層B+樹。通過外層B+樹、內(nèi)層R樹組成的兩層分布式索引結(jié)構(gòu),實現(xiàn)了海量時空數(shù)據(jù)的高效存儲,并可對外提供低時延、高并發(fā)的索引服務。本文的主要貢獻如下:1)基于對時間窗口內(nèi)數(shù)據(jù)雙重排序的思想,提出了一種稱為DSortLoad的新型批量裝... 

【文章來源】：浙江工業(yè)大學浙江省

【文章頁數(shù)】：89 頁

【學位級別】：碩士

【部分圖文】：

算法DSortLoad在1億數(shù)據(jù)量下構(gòu)建性能隨線程數(shù)變化情況

圖 4-7 算法 DSortLoad 在不同數(shù)據(jù)量下構(gòu)建時延隨線程數(shù)變化情況gure 4-7. The algorithm DSortLoad builds delays with the number of tunder different data volumes 4-7 可知，3 種數(shù)據(jù)規(guī)模下，算法 DSortLoad 的 R 樹構(gòu)建時加先快速減少，之后基本維持不變。因為當線程數(shù)到達一定U 等其他資源的物理瓶頸影響，使得構(gòu)建時延很難再減少。下，當線程數(shù)從 7 增加到 8 時，構(gòu)建耗時有略微的增加，這務器規(guī)格為 8 個虛擬核心，其中程序主線程需要占用一個線數(shù)據(jù)流，因此當分配給算法 7 個線程時，正好跑滿 CPU；會出現(xiàn)資源競爭導致時間開銷略微增加。在實際應用中，要選取合適的線程數(shù)，從而達到較好的性能。同樣的實驗方法測試 SSortLoad。使用 1 億數(shù)據(jù)量，時間分窗口大小設(shè)置為 120s，通過變化線程數(shù)目觀察算法構(gòu)建 R 指標主要包括分組內(nèi)最后一個時間分片的排序操作和所有時

圖 4-8 算法 SSortLoad 在 1 億數(shù)據(jù)量下構(gòu)建性能隨線程數(shù)變化情況e 4-8. The algorithm SSortLoad builds performance with the number oin the case of 100 million data 4-8 可得，A 2-delayt 、A 2 -sort A 2-merget +t 和A 2-bulkLdt 一開始隨著線程數(shù)少，但當線程數(shù)量多到一定程度后，由于 CPU 已經(jīng)滿載運行變，有時會出現(xiàn)一定的波動。這是因為當線程數(shù)量超過核數(shù)程切換，會造成一定的時間開銷，實驗結(jié)果和理論相符。進一步分析不同數(shù)據(jù)流流速情況下 R 樹構(gòu)建時延隨線程數(shù)變據(jù)量在 1 億條、5000 萬條和 1000 萬條三種情況下（固定時間時間分片數(shù)為 16），算法 SSortLoad 的 R 樹構(gòu)建時延隨線程數(shù)實驗結(jié)果如圖 4-9 所示。

【參考文獻】：
期刊論文
[1]移動終端云存儲技術(shù)研究[J]. 王輝,唐俊勇.  工業(yè)儀表與自動化裝置. 2017(05)
[2]HBase下的高效時空分類索引[J]. 袁茂林,秦小麟,劉亮,王勝.  小型微型計算機系統(tǒng). 2017(06)
[3]基于HBase的分布式空間數(shù)據(jù)庫技術(shù)[J]. 吳琰,唐小明.  吉林大學學報(理學版). 2016(06)
[4]HiBase:一種基于分層式索引的高效HBase查詢技術(shù)與系統(tǒng)[J]. 葛微,羅圣美,周文輝,趙頔,唐云,周娟,曲文武,袁春風,黃宜華.  計算機學報. 2016(01)
[5]云數(shù)據(jù)管理索引技術(shù)研究[J]. 馬友忠,孟小峰.  軟件學報. 2015(01)
[6]大規(guī)模時空數(shù)據(jù)分布式存儲方法研究[J]. 鐘運琴,方金云,趙曉芳.  高技術(shù)通訊. 2013 (12)
[7]分布式空間數(shù)據(jù)索引機制研究[J]. 陳占龍,吳信才,謝忠,吳亮.  微電子學與計算機. 2007(10)
[8]R樹家族的演變和發(fā)展[J]. 張明波,陸鋒,申排偉,程昌秀.  計算機學報. 2005(03)

博士論文
[1]大規(guī)模空間數(shù)據(jù)的高性能查詢處理關(guān)鍵技術(shù)研究[D]. 劉義.國防科學技術(shù)大學 2013

碩士論文
[1]基于hilbert劃分的并行矢量數(shù)據(jù)索引算法研究[D]. 李勛.電子科技大學 2013



本文編號：2980566