基于MongoDB的轨迹大数据时空索引构建方法

近年来,随着计算机技术与无线传感器网络的发展,轨迹大数据越来越得到人们的关注.针对海量轨迹数据在存储与查询中出现的效率问题,文章基于文档型非关系型数据库MongoDB提出了一套基于四叉树的道路网时空索引,实现海量轨迹数据的高效查询.通过对太原市1915辆出租车的50万条轨迹数据进行时空查询,在不同数据量与不同并发数下测试道路网时空索引与MongoDB复合时空索引的效率表现.实验结果显示道路网时空索引在数据量大于10万时有较好表现,并能够适应不同并发数下的时空查询,验证了道路网时空索引构建方法的可行性和高效性.     

一种面向闪存键值存储的矩阵索引布鲁姆过滤器

索引结构是提高闪存键值存储插入和查询性能的关键技术之一.在分析目前相关索引结构特点的基础上提出了一种面向闪存键值存储的矩阵索引布鲁姆过滤器(matrix-indexed Bloom filter, MIBF),由m×s的位矩阵表示的多个布鲁姆过滤器组(multiple Bloom filter group, MBFG)和一个附加布鲁姆过滤器(additional Bloom filter, ABF)组成,其核心思想是键值对的闪存页地址被拆分为多组位串,每组位串采用MBFG中的一组布鲁姆过滤器(Bloom filter, BF)来表示,同时将键值对的Key与闪存页地址组合值存入ABF中.根据Key查询Value时,MBFG中的每组BF产生多位,组合生成键值对的闪存页地址,并通过ABF滤掉部分伪闪存页地址达到较精确地址定位,从而降低闪存访问次数,提高系统性能.与已有类似方法相比,MIBF的查询地址定位精度提高,内存和闪存访问次数降低明显,插入和查询性能显著提升.     

使用MapReduce构建列存储数据的索引

大数据的存储与分析是近年来数据库领域研究的热点,高效的索引技术是提高大数据查询分析性能的重要技术手段。在现有的数据存储模型及索引技术研究基础上,提出使用MapReduce构建列存储数据的索引。该索引技术结合MapReduce编程模型,先在Map阶段完成数据划分,然后在Reduce阶段完成数据的排序,最后在数据有序的Reduce节点上创建RB+树索引,从而减少索引创建时因为RB+树内部节点递归分裂而产生的昂贵代价和树的高度,提高数据查询的性能。通过在真实数据集上进行实验,验证了所提出方法的有效性。     

电能表系统数据存储的研究

为了解决电能表系统数据现场升级程序容易出现数据混乱的问题,分析了目前电能表系统数据存储的方式,针对目前电能表系统数据存储的问题提出了改善方案。通过数据链表创造出一个可以自由伸缩的数据存储系统,形成了以数据块为存储单元的存储模式,解决了电能表系统中新增加数据会导致现有数据地址改变的问题。文章先从目前电能表系统数据存储的问题说起,随后提出了新的数据存储模型,并一一介绍了新数据存储模型的创建、读取、写入及删除等操作,并在电能表上成功实现了新数据存储模型。     

面向并行备份数据流的数据快速存储方法

在大规模数据服务应用中,尤其是备份与共享系统中,服务器往往会面临大量的上行数据流,而对这些数据的处理需要进行频繁的写操作,由于服务器数据存储位置的随机性,在多用户多任务环境下磁盘性能大大降低.传统的缓存技术只是针对小范围数据的局部性进行优化,对于并行备份数据流的效果不好,因此提出一种数据缓冲方法,通过数据封装,对上行数据流进行整理,动态调整IO次序,实现异步的数据处理接口,提高了文件服务器的存储性能.     

面向云存储的非结构化数据存储研究

作为一种先进计算方式的云计算,不断在信息服务与科研领域升温,并且影响了存储和运算大规模数据。本文主要分析了云存储技术,非结构化数据存储方式,面向云存储的非结构化数据存储系统架构,面向云存储的非结构化数据存储结构设计和实现。     

一种面向相似查询的轨迹索引方法

轨迹数据具有重要的应用价值,轨迹索引技术得到广泛的研究与关注。传统索引方法存在节点重叠、缺乏动态划分空间能力和丢失大量原始信息等问题,为此提出一种面向相似查询的轨迹索引方法GeoSAX。该方法将原始轨迹分成若干等长子段并采用基于Geohash的空间编码;对编码后的整条轨迹设计了基于HBase存储的索引架构;实现相似轨迹查询。GeoSAX不仅节点间没有重叠,还能依据数据量的大小对空间动态划分,同时保留指定精度的轨迹信息。在真实的航运和出租车数据集上进行的对比实验表明,与传统方法相比GeoSAX具有更好的轨迹查询性能。     

一种基于数据访问流的数据库索引优化方法

提出了一种基于数据访问流进行索引优化的方法,该方法通过集成业务流程模型与数据模型,抽取了流程活动中包含的数据访问操作和流程的控制结构形成数据访问流,分析了数据访问流中数据访问操作的频度,为频繁数据访问操作所对应的数据项创建索引,达到改善数据访问性能的目的。实验结果表明,该方法提高了数据查询的速度。     

面向路网连通关系的车辆轨迹数据查询技术研究

定位及通信技术的发展使获取和传输移动车辆的轨迹信息成为可能。从车辆轨迹数据中可以提取出大量的交通信息,这些信息是对交通状况的一个直接和全面的反映。但由于轨迹数据固有的网络特性及时空特性,使针对此类数据的查询成为一个难点,其中关键技术包括建立用于车辆轨迹数据的索引结构及其对应的轨迹数据查询语言。在比较现有轨迹数据索引结构的基础上,对轨迹数据查询语言的分类及其与索引结构之间的调用关系进行了初步的探讨,提出了面向连通关系的查询语言（connectivity-oriented query language, CQL）的定义、分类及实现方法,并简要讨论了车辆轨迹数据查询原型系统的结构和实现方法。     

流数据和传统数据存储及管理方法比较研究

传统数据或静态数据是指来自关系数据库、数据仓库和事务数据库里面的数据,与之对应的流数据,是一种具有实时、快速和连续到达特点的动态数据.由于流数据的上述特点,使得应用于传统数据挖掘的技术和方法不能很好地适应流数据.对传统数据进行存储、查询和管理,使用成熟的DBMS完成,对流数据的类似操作,必须开发出具体的DSMS加以实现.提出了一个对流数据进行管理的系统框架,并在管理系统和存储方式两方面对两种数据进行综合比较.     

面向轨迹数据流的KNN近似查询

提出一种基于滑动窗口的K-最近邻(KNN)近似查询算法。将滑动窗口内数据通过聚类划分成若干大小不一的基本窗口,针对每个基本窗口给定一个采样率,对窗口内数据进行偏倚采样,形成数据流摘要,并基于该摘要,采用计算几何平面扫描算法执行分布式最近邻查询。仿真实验结果表明该算法有效,且具有较好的可扩展性。     

一种面向数据流模型的流计数算法

在研究数据流过程中,基于现有的概要数据结构Bloom Filter,给出改进的K Bloom Filter结构,从理论上对假阳性误判进行分析,得出两者具有相同的在误判率f0下表示集合规模的上限n0,因此,K Bloom Filter的误判率在可控范围内。提出基于K Bloom Filter的流计数算法,与基于Bloom Filter的流计数算法相比,在相同的空间复杂度O(m)和插入操作时间复杂度O(k)情况下,该算法降低了统计结果的误差。     

DTI:对于运动轨迹数据的新型索引结构

近年随着定位技术(Location-based Service)越来越广泛的使用,时空数据(Spatio-Temporal Data)大量的产生.如何有效的对这些数据的进行管理已经成为一个越来越受重视的问题.通常可以使用R-tree[1]结构对这类数据进行索引,然而,目前并不是所有的商业关系数据库都支持R-tree.因此,提出了DTI这种新型的基于B-tree结构的索引方法.DTI可以在几乎所有的关系数据库上进行实施.DTI使用Hilbert曲线处理空间维度.同时在时间维度上使用RI-tree进行处理.实验证明,DTI显著提高查询速度.     

基于分层计数型Bloom过滤器的进化数据流计数

许多应用场景所产生的数据流中,元素的频数分布符合重尾分布的特点,即大部分元素的频数较小而少部分元素的频数较大.为了解决数据流中所有相异元素及其频数的高效存储问题,提出了一个基于分层的计数型布卢姆过滤器(hierarchical counting Bloom filter,HCBF)保存所有元素频数的方法.该方法采用长度递减、计数单位递增的多层计数型布卢姆过滤器作为存储数据结构,多层过滤器共同组成元素的频数.与两个经典的计数型布卢姆过滤器CBF和DCF相比,HCBF更加适合真实数据流元素频数分布的重尾特点,在不影响查询性能和错误率的前提下,能够显著地降低空间开销.理论分析与实验结果验证了该结论.     

典型Bloom过滤器的研究及其数据流应用

Bloom过滤器是一种空间高效但有一定假阳性的数据表示方法。该文分析比较计数型Bloom过滤器、光谱Bloom过滤器和动态计数过滤器的异同点及适用场合,介绍Bloom过滤器在重复项检测及频繁项挖掘中的应用,总结Bloom过滤器给数据流带来的挑战,包括元素突发问题及数据流相异元素数目变化问题。     

数据流聚类算法研究

许多应用程序会产生大量的流数据,如网络流、web点击流、视频流、事件流和语义概念流。数据流挖掘已成为热点问题,其目标是从连续不断的流数据中提取隐藏的知识/模式。聚类作为数据流挖掘领域的一个重要问题,在近期被广泛研究。不同于传统的静态数据聚类问题,数据流聚类面临有限内存、一遍扫描、实时响应和概念漂移等许多约束。本文对数据流挖掘中的各种聚类算法进行了总结。首先介绍了数据流挖掘的约束;随后给出了数据流聚类的一般模型,并描述了其与传统数据聚类之间的关联;最后提出数据流聚类领域中进一步的研究热点和研究方向。     

面向大数据流的分布式索引构建

大数据流的高效存储与索引是当今数据领域的一大难点.面向带有时间属性的数据流,根据其时间属性,将数据流划分为连续的时间窗口,提出了基于双层B+树的分布式索引结构WB-Index.下层B+树索引基于窗口内流数据构建,索引构建过程结合基于排序的批量构建技术,进一步对时间窗口分片,将数据流接收、分片数据排序以及B+树构建并行化,提高了构建性能.上层B+树索引基于各时间窗口构建,结合时间窗口时间戳的递增性和无限性,提出了避免节点分裂的构建方法,减少了B+树分裂移动开销,提高了空间利用率和更新效率.WB-Index架构中,将流数据和索引分离,同时利用内存缓存尽可能多的双层B+索引和热点数据来提高查询性能.理论和实验结果表明,该分布式索引架构能够支持高效的实时数据流写入以及流数据查询,能够很好地应用于具有时间属性的数据流场景.     

基于形态特征的数据流聚类方法研究

在聚类过程中为保留数据的重要形态与趋势特征,提出一种基于形态特征的数据流聚类方法。在初始化阶段提取重要特征点表示序列分段,在在线更新阶段使用部分动态时间弯曲方法计算子序列距离,基于动态滑动窗口思想保证多条数据流中数据的同步,在用户触发聚类阶段提出数据流聚类方法。通过对仿真数据和实际股票数据的分析结果表明,在参数设置合理的情况下,该方法可以获得接近0.95的聚类演化精度。     

一种大数据流内存B+树构建方法

面向具有时间维度的大数据流,基于二级B+树索引结构,提出了一种高效的面向时间窗口、采用批量装载技术的内存B+树构建方法。该方法对时间窗口进行分片,通过分离出可以并行处理的操作来加速构建过程,将排序操作与数据流接收并行,B+树骨架的构建与排序并行;采用基于排序的批量装载技术以及优化 的构建顺序,能够避免多线程之间不必要的加锁、同步开销,有效提高构建效率。提出的多次微批量排序单次批量装载(MBSortSBLoad)B+树构建方法的构建速度快,能承载的最大流速大。实验验证了所提方法的有效性。