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

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

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

【學(xué)位級(jí)別】：碩士

【部分圖文】：

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

圖 4-7 算法 DSortLoad 在不同數(shù)據(jù)量下構(gòu)建時(shí)延隨線程數(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í)加先快速減少，之后基本維持不變。因?yàn)楫?dāng)線程數(shù)到達(dá)一定U 等其他資源的物理瓶頸影響，使得構(gòu)建時(shí)延很難再減少。下，當(dāng)線程數(shù)從 7 增加到 8 時(shí)，構(gòu)建耗時(shí)有略微的增加，這務(wù)器規(guī)格為 8 個(gè)虛擬核心，其中程序主線程需要占用一個(gè)線數(shù)據(jù)流，因此當(dāng)分配給算法 7 個(gè)線程時(shí)，正好跑滿 CPU；會(huì)出現(xiàn)資源競(jìng)爭(zhēng)導(dǎo)致時(shí)間開銷略微增加。在實(shí)際應(yīng)用中，要選取合適的線程數(shù)，從而達(dá)到較好的性能。同樣的實(shí)驗(yàn)方法測(cè)試 SSortLoad。使用 1 億數(shù)據(jù)量，時(shí)間分窗口大小設(shè)置為 120s，通過變化線程數(shù)目觀察算法構(gòu)建 R 指標(biāo)主要包括分組內(nèi)最后一個(gè)時(shí)間分片的排序操作和所有時(shí)

圖 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ù)少，但當(dāng)線程數(shù)量多到一定程度后，由于 CPU 已經(jīng)滿載運(yùn)行變，有時(shí)會(huì)出現(xiàn)一定的波動(dòng)。這是因?yàn)楫?dāng)線程數(shù)量超過核數(shù)程切換，會(huì)造成一定的時(shí)間開銷，實(shí)驗(yàn)結(jié)果和理論相符。進(jìn)一步分析不同數(shù)據(jù)流流速情況下 R 樹構(gòu)建時(shí)延隨線程數(shù)變據(jù)量在 1 億條、5000 萬條和 1000 萬條三種情況下（固定時(shí)間時(shí)間分片數(shù)為 16），算法 SSortLoad 的 R 樹構(gòu)建時(shí)延隨線程數(shù)實(shí)驗(yàn)結(jié)果如圖 4-9 所示。

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

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

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



本文編號(hào)：2980566