面向时空数据流的分布式索引
发布时间：2021-01-16 09:24
随着物联网技术和基于位置的服务（LBS）的快速发展,位置感知服务在日常生活中发挥着越来越重要的作用。基于物联网技术和LBS采集到的数据通常带有时间域和空间域特性,称之为时空数据。连续到达的时空数据称为时空数据流,它具有实时性、无限性、突发性等特点。对于流式时空数据需要新的查询处理技术来处理,传统空间索引的批量装载方法,如R树,不适用于时空数据流场景,他们通常只考虑静态数据或批量更新。然而,对于时空流数据,现有的批量构造方法不能实时或近实时处理。本文基于分布式索引技术和R树批量装载技术,提出了一种面向时空数据流的分布式索引。该索引采用时间窗口机制将时空数据流切分为连续的时间窗口处理单元,然后使用针对时空数据流优化的R树批量装载算法为每个时间窗口构建一棵内层R树,将每个时间窗口的时间信息和对应的R树根节点信息组成<key,value>元组,用于构建外层B+树。通过外层B+树、内层R树组成的两层分布式索引结构,实现了海量时空数据的高效存储,并可对外提供低时延、高并发的索引服务。本文的主要贡献如下:1)基于对时间窗口内数据双重排序的思想,提出了一种称为DSortLoad的新型批量装...
【文章来源】：浙江工业大学浙江省
【文章页数】：89 页
【学位级别】：硕士
【部分图文】：
算法DSortLoad在1亿数据量下构建性能随线程数变化情况
图 4-7 算法 DSortLoad 在不同数据量下构建时延随线程数变化情况gure 4-7. The algorithm DSortLoad builds delays with the number of tunder different data volumes 4-7 可知，3 种数据规模下，算法 DSortLoad 的 R 树构建时加先快速减少，之后基本维持不变。因为当线程数到达一定U 等其他资源的物理瓶颈影响，使得构建时延很难再减少。下，当线程数从 7 增加到 8 时，构建耗时有略微的增加，这务器规格为 8 个虚拟核心，其中程序主线程需要占用一个线数据流，因此当分配给算法 7 个线程时，正好跑满 CPU；会出现资源竞争导致时间开销略微增加。在实际应用中，要选取合适的线程数，从而达到较好的性能。同样的实验方法测试 SSortLoad。使用 1 亿数据量，时间分窗口大小设置为 120s，通过变化线程数目观察算法构建 R 指标主要包括分组内最后一个时间分片的排序操作和所有时
图 4-8 算法 SSortLoad 在 1 亿数据量下构建性能随线程数变化情况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 一开始随着线程数少，但当线程数量多到一定程度后，由于 CPU 已经满载运行变，有时会出现一定的波动。这是因为当线程数量超过核数程切换，会造成一定的时间开销，实验结果和理论相符。进一步分析不同数据流流速情况下 R 树构建时延随线程数变据量在 1 亿条、5000 万条和 1000 万条三种情况下（固定时间时间分片数为 16），算法 SSortLoad 的 R 树构建时延随线程数实验结果如图 4-9 所示。
【参考文献】：
期刊论文
[1]移动终端云存储技术研究[J]. 王辉,唐俊勇. 工业仪表与自动化装置. 2017(05)
[2]HBase下的高效时空分类索引[J]. 袁茂林,秦小麟,刘亮,王胜. 小型微型计算机系统. 2017(06)
[3]基于HBase的分布式空间数据库技术[J]. 吴琰,唐小明. 吉林大学学报(理学版). 2016(06)
[4]HiBase:一种基于分层式索引的高效HBase查询技术与系统[J]. 葛微,罗圣美,周文辉,赵頔,唐云,周娟,曲文武,袁春风,黄宜华. 计算机学报. 2016(01)
[5]云数据管理索引技术研究[J]. 马友忠,孟小峰. 软件学报. 2015(01)
[6]大规模时空数据分布式存储方法研究[J]. 钟运琴,方金云,赵晓芳. 高技术通讯. 2013 (12)
[7]分布式空间数据索引机制研究[J]. 陈占龙,吴信才,谢忠,吴亮. 微电子学与计算机. 2007(10)
[8]R树家族的演变和发展[J]. 张明波,陆锋,申排伟,程昌秀. 计算机学报. 2005(03)
博士论文
[1]大规模空间数据的高性能查询处理关键技术研究[D]. 刘义.国防科学技术大学 2013
硕士论文
[1]基于hilbert划分的并行矢量数据索引算法研究[D]. 李勋.电子科技大学 2013
本文编号：2980566
【文章来源】：浙江工业大学浙江省
【文章页数】：89 页
【学位级别】：硕士
【部分图文】：
算法DSortLoad在1亿数据量下构建性能随线程数变化情况
图 4-7 算法 DSortLoad 在不同数据量下构建时延随线程数变化情况gure 4-7. The algorithm DSortLoad builds delays with the number of tunder different data volumes 4-7 可知，3 种数据规模下，算法 DSortLoad 的 R 树构建时加先快速减少，之后基本维持不变。因为当线程数到达一定U 等其他资源的物理瓶颈影响，使得构建时延很难再减少。下，当线程数从 7 增加到 8 时，构建耗时有略微的增加，这务器规格为 8 个虚拟核心，其中程序主线程需要占用一个线数据流，因此当分配给算法 7 个线程时，正好跑满 CPU；会出现资源竞争导致时间开销略微增加。在实际应用中，要选取合适的线程数，从而达到较好的性能。同样的实验方法测试 SSortLoad。使用 1 亿数据量，时间分窗口大小设置为 120s，通过变化线程数目观察算法构建 R 指标主要包括分组内最后一个时间分片的排序操作和所有时
图 4-8 算法 SSortLoad 在 1 亿数据量下构建性能随线程数变化情况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 一开始随着线程数少，但当线程数量多到一定程度后，由于 CPU 已经满载运行变，有时会出现一定的波动。这是因为当线程数量超过核数程切换，会造成一定的时间开销，实验结果和理论相符。进一步分析不同数据流流速情况下 R 树构建时延随线程数变据量在 1 亿条、5000 万条和 1000 万条三种情况下（固定时间时间分片数为 16），算法 SSortLoad 的 R 树构建时延随线程数实验结果如图 4-9 所示。
【参考文献】：
期刊论文
[1]移动终端云存储技术研究[J]. 王辉,唐俊勇. 工业仪表与自动化装置. 2017(05)
[2]HBase下的高效时空分类索引[J]. 袁茂林,秦小麟,刘亮,王胜. 小型微型计算机系统. 2017(06)
[3]基于HBase的分布式空间数据库技术[J]. 吴琰,唐小明. 吉林大学学报(理学版). 2016(06)
[4]HiBase:一种基于分层式索引的高效HBase查询技术与系统[J]. 葛微,罗圣美,周文辉,赵頔,唐云,周娟,曲文武,袁春风,黄宜华. 计算机学报. 2016(01)
[5]云数据管理索引技术研究[J]. 马友忠,孟小峰. 软件学报. 2015(01)
[6]大规模时空数据分布式存储方法研究[J]. 钟运琴,方金云,赵晓芳. 高技术通讯. 2013 (12)
[7]分布式空间数据索引机制研究[J]. 陈占龙,吴信才,谢忠,吴亮. 微电子学与计算机. 2007(10)
[8]R树家族的演变和发展[J]. 张明波,陆锋,申排伟,程昌秀. 计算机学报. 2005(03)
博士论文
[1]大规模空间数据的高性能查询处理关键技术研究[D]. 刘义.国防科学技术大学 2013
硕士论文
[1]基于hilbert划分的并行矢量数据索引算法研究[D]. 李勋.电子科技大学 2013
本文编号：2980566
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/2980566.html
