摘要:

摘要:信息技术的迅速发展,催生了大数据时代的到来.大数据已经成为信息社会的重要财富,为人们更深入地感知、认识和控制物理世界提供了前所未有的丰富信息.然而随着数据规模的扩大,劣质数据也随之而来,导致大数据质量低劣,极大地降低了大数据的可用性,严重困扰着信息社会.近年来,数据可用性问题引起了学术界和工业界的共同关注,展开了深入的研究,取得了一系列研究成果.介绍了数据可用性的基本概念,讨论数据可用性的挑战与研究问题,综述了数据可用性方面的研究成果,探索了大数据可用性的未来研究方向.

摘要:信息化时代数据海量增长的同时,用户需要利用多种指标从不同性质角度对数据质量进行评价和改善.但在目前数据质量管理过程中,影响数据可用性的多种重要因素并非完全孤立,在评估机制和指导数据清洗规则时,彼此会发生关联.研究了在实际信息系统中适用的综合性数据质量评估方法,将文献所提出以及在实际的信息系统中常用的数据质量性质指标按其定义与性质进行了归纳总结,提出了基于性质的数据质量综合评估框架.之后针对影响数据可用性的4个重要性质:精确性、完整性、一致性以及时效性整理出在数据集合上的操作方法,并逐一介绍其违反模式的定义,随后给出其具体关系证明,进而确定数据质量多维关联关系评估策略,并通过实验验证了该策略的有效性.

摘要:现有的模糊粗糙集方法,由于其基础理论复杂度的桎梏,无法应用到大规模数据集上.考虑到随机抽样是一种可以极大地减少运算量的统计学方法,将随机抽样引入到经典的模糊粗糙集理论中,建立了一种统计粗糙集模型.首先,提出了统计上、下近似的概念,它相比经典模糊粗糙集模型的优势在于,以随机抽样得到的小容量样本代替了大规模全集,从而显著降低了计算量.而且,随着全集数量的增大,抽样样本数量并不会显著增大.此外,还讨论了统计上、下近似的性质,揭示统计上、下近似和经典上、下近似之间的关系.并且,提出了一个定理,该定理保证了统计下近似与经典下近似的取值统计误差在允许的范围内.最后,通过数值实验验证了统计下近似在计算时间上的显著优势.

摘要:真值发现作为整合由不同数据源提供的冲突信息的一种手段,在传统数据库领域已经得到了广泛的研究.然而现有的很多真值发现方法不适用于数据流应用,主要原因是它们都包含迭代的过程.针对一种特殊的数据流——感知数据流上的连续真值发现问题进行了研究.结合感知数据本身及其应用特点,提出一种变频评估数据源可信度的策略,减少了迭代过程的执行,提高了每一时刻多源感知数据流真值发现的效率.首先定义并研究了当感知数据流真值发现的相对误差和累积误差较小时,相邻时刻数据源的可信度变化需要满足的条件,进而给出了一种概率模型,以预测数据源的可信度满足该条件的概率.之后,通过整合上述结论,实现在预测的累积误差以一定概率不超过给定阈值的前提下,最大化数据源可信度的评估周期以提高效率,并将该问题转化为一个最优化问题.在此基础上,提出了一种变频评估数据源可信度的算法——CTF-Stream(continuous truth finding over sensor data streams),CTF-Stream结合历史数据动态地确定数据源可信度的评估时刻,在保证真值发现结果达到用户给定精度的同时提高了效率.最后,通过在真实的感知数据集合上进行实验,进一步验证了算法在处理感知数据流的真值发现问题时的效率和准确率.

摘要:随着经济与信息技术的发展,在许多应用中均产生大量数据.然而,受硬件设备、人工操作、多源数据集成等诸多因素的影响,在这些应用之中往往存在较为严重的数据质量问题,特别是不一致性问题,从而无法有效管理数据.因此,首要的任务就是开发新型数据清洗技术来提升数据质量,以支持后续的数据管理与分析.现有工作主要研究基于函数依赖的数据修复技术,即以函数依赖来描述数据一致性约束,通过变更数据库中部分元组的属性值(而非增加/删除元组)来使得整个数据库遵循函数依赖集合.从一致性约束描述的角度来看,函数依赖并非是唯一的表达方式,还存在其他表达方式,例如硬约束、数量约束、等值约束、非等值约束等.然而,随着一致性约束种类的增加,其处理难度也远比仅有函数依赖的场景要困难.考虑以函数依赖与其他一致性约束共同表述数据库的一致性约束,并在此基础上设计数据修复算法,从而提升数据质量.实验结果表明,所提方法的执行效率较高.

摘要:针对关系数据的不一致性虽然已有各种修复方法被提出,但这些修复策略在构建最终修复方案的过程中只分析函数依赖包含属性的信息(即,数据集的部分信息),且偏向于修复代价最小的方案,而忽略了数据集的其他属性以及这些属性与函数依赖包含属性之间的相关性.为此,提出一种基于可能世界模型的不一致性修复方法.它首先构造可能的修复方案,然后从修复代价和属性值相关性两个方面量化各个候选修复方案的可信性程度,并最后找出最优的修复方案.实验结果验证了所提出的修复方法取得了比现有基于代价的修复方法更好的修复效果.同时也分析了错误率和不同类型概率量化对所提出的修复方法的影响.

摘要:重要位置是指人们在日常生活中的主要活动地点,比如居住地和工作地.智能手机的不断发展与普及为人们的日常生活带来了极大的便利.除了通话、上网等传统应用之外,手机连接基站自动生成的日志记录也是用于用户行为模式挖掘的重要数据来源,例如重要位置发现.然而,相关工作面临着诸多挑战,包括轨迹数据规模庞大、位置精度低以及手机用户的多样性.为此,提出了一个通用解决框架以提高轨迹数据可用性.该框架包含一个基于状态的过滤模块,提高了数据的可用性,以及一个重要位置挖掘模块.基于此框架设计了两种分布式挖掘算法:GPMA(grid-based parallel mining algorithm)和SPMA(station-based parallel mining algorithm).进一步地,为提高挖掘结果的准确性和精确度,从3个方面进行优化:(1)使用多元数据的融合技术,提高结果的准确性;(2)提出了无工作地人群的发现算法;(3)提出了夜间工作人群的发现算法.理论分析和实验结果表明,所提算法具有较高的执行效率和可扩展性,并具有更高的精度.

摘要:随着下一代、第三代等测序技术的快速发展,DNA等生物序列数据快速增长.如何高效地处理这些大数据是目前所面临的一个挑战.研究发现,这些生物序列数据尽管很大,但是不同数据之间具有很高的相似性.因此可以通过保存这些基因串同一个基准序列之间的差异来减少存储的代价.最新的研究发现,可以在这些压缩的数据上直接进行查询,而不需要解压缩.研究的目标是进一步提高索引和查询的可伸缩性,从而满足日益增长的大数据需要.首先在现有方法的基础上,对基准序列进行了压缩存储.基于该压缩数据,提出了一系列优化查询方法以高效地支持任意长度序列的精确和近似查询.在此基础上,进一步对原有方法进行改进,利用并行计算来提高对大数据的查询效率.最后,实验研究展示了所提方法的高效性.

摘要:遥感图像具有多时相、多语义、多波段等特点,鉴于遥感图像在商业行业及国防军事中的重要性,海量遥感图像密文检索的效率和精度直接影响了遥感大数据使用的广泛性和实时性.对密文存储的遥感大数据的安全检索,是其可用性最重要的标志之一.提出了一种基于Henon映射的遥感图像可搜索加密方案,根据遥感图像的成像原理及多波段特征,采用改进的Henon映射对每个波段的灰度值进行加密处理.同时,根据遥感图像的"大数据"特征,通过统计灰度值的区间信息来构造遥感图像的特征向量,并根据相似度匹配算法来检索目标图像.通过对Landsat 8遥感图像进行加密与检索进行实验,结果表明,该方案有效地提高了检索密文遥感图像的安全性及准确性,且计算复杂度低、通信成本开销小.

摘要:抽象解释为程序不变式的自动化生成提供了通用的框架,但是该框架下的大多数已有数值抽象域只能表达几何上是凸的约束集.因此,对于包含(所对应的约束集是非凸的)析取语义的特殊程序结构,采用传统数值抽象域会导致分析结果不精确.针对显式和隐式含有析取语义的循环结构,提出了基于循环分解和归纳推理的不变式生成改进方法,缓解了抽象解释分析中出现的语义损失问题.实验结果表明:相比已有方法,该方法能为这种包含析取语义的循环结构生成更加精确的不变式,并且有益于一些安全性质的推理.

摘要:在模型驱动软件开发过程中,基于模型的测试方法往往用于检验软件代码针对软件模型的一致性以确保软件质量.然而,随着当今软件系统规模的不断扩大,相应的软件开发过程也变得越来越灵活,代码有时会先于模型被修改,以更忠实地体现系统功能和实现机制.传统的基于模型的测试方法只能检测代码之于模型的一致性而不能反作用于模型层面,模型的修改者只能人为地评估修改的正确性,大大降低了效率并增加了系统的潜在隐患.为此,对传统基于模型的测试方法的一致性检验进行了扩展,实现了一致性检验框架ProMiner,通过抽取表达模型与代码的不一致的系统性质来自动定位模型中与实际运行系统不匹配的部分,并将其表示为可直接用于模型检测的线性时序逻辑(LTL)表达式,以支持软件模型和代码间双向的一致性检验.实验结果表明,ProMiner可有效查找软件模型和代码间的不一致并生成可直接检测模型的系统性质,从而实现了自动化的模型与代码间的双向一致性检测,不仅提高了一致性检测的有效性,而且大大减少了人力开销.

摘要:运用模型检测技术验证动态演化的正确性,是近年来软件体系结构动态演化研究领域面临的一个挑战.然而,当前的方法很少考虑软件体系结构动态演化时的相关条件.针对该问题,提出用条件状态转移系统表示软件体系结构动态演化的状态模型,将软件体系结构超图映射为状态,演化规则运用映射为条件状态转移关系,给出软件体系结构动态演化的条件超图文法到条件状态转移系统的映射方法以及相应的实现算法,实现了软件体系结构动态演化的条件状态转移系统的构建,并证明了在该映射方法下,软件体系结构动态演化条件超图文法与条件状态转移系统的互模拟等价.最后通过案例分析,运用该方法以及模型检测技术,验证了软件体系结构动态演化的相关性质,从而验证了该方法的有效性.

摘要:任务并行程序设计模型已成为并行程序设计的主流,其通过发掘任务并行性来提高并行计算机的系统性能.提出一种支持容错的任务并行程序设计模型,将容错技术融入到任务并行程序设计模型中,在保证性能的同时提高系统可靠性.该模型以任务为调度、执行、错误检测与恢复的基本单位,在应用级实现容错支持.采用一种Buffer-Commit计算模型支持瞬时错误的检测与恢复;采用应用级无盘检查点实现节点故障类型永久错误的恢复;采用一种支持容错的工作窃取任务调度策略获得动态负载均衡.实验结果表明,该模型以较低的性能开销提供了对硬件错误的容错支持.

摘要:近年来,位置服务中的隐私保护问题得到了研究者的持续关注,特别是近邻查询中位置隐私保护问题更是得到了广泛的研究.已有工作缺少对查询者个性化隐私偏好约束的系统研究,位置隐私与查询服务质量的兼顾,在隐私偏好约束下尤为困难:(1)偏好强调个性与隐私模型侧重共性存在矛盾;(2)偏好对查询中间结果动态可控依赖与查询简化中间结果的思想相抵触;(3)连续查询中,支持隐私偏好存在基于候选解集攻击的风险.结合上述问题,提出保护位置隐私近邻查询中的隐私偏好问题,从位置隐藏原理及近邻查询性能与保护位置隐私内在制约机理的角度,对已有的位置隐藏与查询处理方法的性能及其对隐私偏好支持能力进行论述分析.进一步地,对支持隐私偏好与保护位置隐私查询内在制约机理进行了剖析,分析保护位置隐私近邻查询中支持隐私偏好需解决的主要问题,并对所归纳问题的可能解决方法进行了展望.

摘要:在大规模的无线传感器网络中收集数据,不仅需要考虑节点的能量消耗,而且还需要考虑数据收集延迟.如何有效地均衡节点的能量消耗,同时最小化数据收集延迟,是一个具有挑战性的问题.为了均衡节点的能量消耗,利用移动数据收集器收集数据.以此为基础,提出一种DC-Collection算法来解决数据收集延迟和能耗的问题.首先,在网络中构造最短路径树,网络非连通时,不同的网络子图可以构造多棵最短路径树,它们构成一个最短路径树集合;其次,在每一棵最短路径树上选取部分节点作为采集节点和逗留节点,使得以采集节点为根的限高树的高度不超过h,且在每个采集节点的通信区域内至少有一个逗留节点;再次,在每棵限高树内调整树的结构,让能量高的节点承担更多的子孙节点,最大化限高树的生命周期;最后,移动数据收集器从Sink出发,遍历逗留节点所在位置收集数据,最终回到起点,并将数据发送给Sink.通过理论分析和大量仿真实验,其结果表明:与现有的数据收集协议相比,DC-Collection不仅能够均衡各节点的能量消耗从而延长网络生命周期,而且能够缩短移动数据收集器收集数据行走的路径长度,从而缩短数据收集延迟.

摘要:超点检测对于网络安全、网络管理等应用具有重要意义.由于存在着高速网络环境下海量网络流量与有限系统资源之间的矛盾,在线准确地监测网络流量是一个极大的挑战.随着多核处理器的发展,多核处理器的并行性成为算法性能提高的一种有效途径.目前,针对基于流抽样的超点检测方法存在计算负荷重、检测精度低、实时性差等问题,提出了一种并行数据流方法(parallel data streaming,简称PDS).该方法构造并行的可逆Sketch数据结构,建立紧凑的节点链接度概要,在未存储节点地址信息的情况下,通过简单地计算重构超点的地址,获得了良好的效率和精度.实验结果表明:与CSE(compact spread estimator),JM(joint data streaming and sampling method)方法相比,该方法具有较好的性能,能够满足高速网络流量监测的应用需求.

摘要:科学工作流是一种复杂的数据密集型应用程序.如何在混合云环境中对数据进行有效布局,是科学工作流所面临的重要问题,尤其是混合云的安全性要求给科学云工作流数据布局研究带来了新的挑战.传统数据布局方法大多采用基于负载均衡的划分模型布局数据集,该方法可以获得很好的负载平衡布局,然而传输时间并非最优.针对传统数据布局方法的不足,并结合混合云中数据布局的特点,首先设计一种基于数据依赖破坏度的矩阵划分模型,生成对数据依赖度破坏最小的划分;然后提出一种面向数据中心的数据布局方法,该方法依据划分模型将依赖度高的数据集尽量放在同一数据中心,从而减少数据集跨数据中心的传输时间.实验结果表明,该方法能够有效地缩短科学工作流运行时跨数据中心的数据传输时间.

摘要:提出了一种基于虚拟机负载高峰特征的虚拟机放置策略,通过更好地复用物理主机资源来实现资源共享,从而提高资源利用率.在云环境下,当多个虚拟机的负载高峰出现在相同的时间段内时,非高峰时段的资源利用率就会明显偏低;相反,多个虚拟机只要负载高峰能错开在不同的时间,闲置的资源就能更充分地被利用.由于应用的负载通常具有一定的周期性,因此,可以利用虚拟机负载的历史数据作为分析的依据.基于虚拟机的负载高峰特征对虚拟机负载进行建模,建立虚拟机负载之间的相似度矩阵来实现虚拟机联合放置.使用CloudSim模拟实现了所提出的算法,并与基于相关系数的放置算法、随机放置算法进行了比较.实验结果表明:所提算法在平均CPU利用率上有8.9%~12.4%的提高,主机使用量有8.2%~11.0%的节省.