闪存数据库：现状、技术与展望
摘要：随着闪存存储技术的发展,闪存已经广泛应用于各种移动设备、PC机和服务器中.作为一种完全不同于磁盘的新型存储介质,闪存具有非易失、高速读写、抗震、低功耗、高存储密度等物理特性,这使得基于闪存的数据管理问题成为新的挑战.数据库系统是数据管理的重要技术,将现有的数据库系统直接移植到闪存上并不能充分发挥其硬件特性,设计实现基于闪存的数据库系统是当前的一个研究热点.文中介绍了闪存的特性和闪存转换层;总结了缓冲区、索引、查询和事务等数据库关键技术;讨论了基于闪存的混合存储数据管理.最后,基于该领域亟待解决的诸多问题,指出了未来的研究方向.基于替换概率的闪存数据库缓冲区替换算法
摘要：闪存具有和传统磁盘不同的特性,包括写前擦除、异地更新、读写延迟非对称等.传统的面向磁盘的缓冲区替换算法无法在闪存数据库系统中获得较好的性能.文中提出了一种新的面向闪存数据库的缓冲区替换算法——APB-LRU,其特点：（1）该算法将缓冲区分为冷区和热区,用来捕获数据访问频度,前者用于存放只访问过一次的数据页,后者用于存放至少访问过两次的数据页;（2）采用了其它研究所没有的概率替换机制,即以较大的概率替换冷区中的干净页,以较小的概率替换冷区中的脏页,从而避免了冷脏页长期驻留缓冲区的情况,提高了命中率,获得了较好的整体性能;（3）设计了冷、热区比例动态变化机制,可以根据工作负载的变化动态调整冷、热区所占缓冲区的比例,从而使得替换算法在不同的负载模式下都可以取得较好的性能.基于不同测试数据集的大量实验结果表明,APB-LRU算法具有比其它已有的算法更好的性能.基于相变存储器和闪存的数据库事务恢复模型
摘要：随着闪存容量不断增大、价格不断下降,闪存在实际存储系统上得到了越来越广泛的应用.但是,闪存的页级读写、异位更新、有限寿命等阻碍了闪存数据库系统的性能提升,尤其是事务恢复.闪存的异位更新使得影子页技术可以很好地支持闪存数据库事务恢复,同时也给闪存数据库带来新挑战,如事务管理、缓冲区管理.相变存储器凭借其比闪存更高的读写速度、更小的读写粒度、更长的寿命成为了下一代主流存储技术,所以相变存储器可以用于解决在闪存数据库中使用影子页技术所产生的事务管理和缓冲区管理问题.该文基于相变存储器和闪存混合式存储提出一种全新的数据库事务恢复模型——SPFP.该模型充分利用相变存储器的特性完成事务管理.为支持非强制缓冲区管理,基于SPFP提出了一种优化的数据库事务恢复模型——SPFLP,利用相变存储器记录更多事务信息.实验结果表明,相较于全闪存存储的数据库系统,SPFLP大大提高了基于混合存储的数据库事务处理性能.基于时态数据库的极小子结构逻辑系统
摘要：逻辑是知识表达的重要方法,但由于时序性知识与时间属性知识交叉应用的复杂性,其对时态数据库支撑一直不尽如人意.目前时态数据运算体系不完备,时态关系演算缺乏系统和有力的逻辑与代数理论支持.为此,文中从子结构逻辑出发,针对时态数据库及其信息处理中关键的知识推理、时态操作与函数依赖等内容,构建了一个极小的（最小的）子结构逻辑系统TDLmin,其恰好等价于传统的数据库函数依赖Armstrong规则.TDLmin系统能在逻辑语义模型中对时序性、时间属性进行表达,而在句法逻辑系统将时间剥离,从而既表达了时态知识,对时态操作进行处理,又降低了逻辑系统的复杂度,使得逻辑系统的时间复杂度为P-time（O（n2））.而该逻辑系统还可与传统的Allen方法进行对接,使得相关时态查询所需的时间代价为传统非时态查询的时间加上一个复杂度仅为O（n）的线性时间,从而使得系统具有更强的普适性和应用前景.基于对象异常频度的数据流阈值查询
摘要：数据流查询与处理技术广泛应用在金融系统等诸多领域中,银行卡交易系统中存在的由终端复用所导致的不规范交易即是一个典型案例.此类不规范交易存在两个特点：（1）对象频繁出现;（2）对象的值序列频繁波动.然而,现有的频繁项挖掘算法仅考虑第一个特点,无法有效解决问题,亟需开发新技术进行检测.文中首先形式化地定义了这类不规范交易查询,再设计了多个创新算法进行处理.此外,文中还将工作扩展到滑动窗口模型以处理数据流演化问题.理论分析与实验结果均表明所提方法具有较佳性能,空间复杂度与时间复杂度都较低.混合的大规模数据库自动模式抽象方法
摘要：随着数据库规模的扩大,其模式的复杂度也不断地增加,复杂的模式和文档的缺乏使得理解和操作数据库更加困难.现有的模式抽象方法大多通过关系表中的主外键信息查找出模式中最重要的表,然后使用这些最重要的表来构成单层次的模式总结.在现实应用中,这些模式总结的主题并不明确.文中陈述了现有方法的不足,然后给出了一种为大规模数据库生成多层次模式抽象的方法.在此方法中,首先使用不同类型的社区社团检测算法来将数据库模式划分为＂团＂,然后使用元聚类方法将这些＂团＂集成为数据库的主题组,每一个主题组代表数据库的一个主题.最后将这些主题组进行进一步的聚类以生成主题组类,并为每一个主题组类挑选标签以生成多层次的模式抽象.在Freebase——开源的大规模数据库上验证了文中算法的有效性.实验证明文中算法不仅能够精确地识别大规模数据库的主题,同时可以依据数据库的主题生成易于理解、能够帮助用户浏览和检索数据库的多层次模式抽象.一种列存储数据仓库中的数据复用策略
摘要：数据复用是数据仓库管理中节约存储空间、提高查询效率的重要手段.列存储技术将来自同一属性的数据连续存储,极大地提高了数据仓库等分析型应用软件的性能,同时增加了复用的可行性和灵活性.为此,提出了一种列存储数据仓库中的数据复用策略.首先,利用模式匹配技术发掘候选可复用列,排除大量无法复用的数据列,在此基础上对候选可复用数据进行筛选和过滤,大大降低复用数据检测的复杂度.针对确定的可复用数据,提出了基于列存储的复用实现策略,分别给出了原始数据列、压缩数据列及索引数据列的复用实现方法.最后提出了基于复用数据的查询实现技术.在大规模数据仓库基准数据集上的实验结果验证了数据复用策略在减少存储量、节省数据装载时间及提升查询性能方面的有效性.众包质量控制策略及评估算法研究
摘要：随着Internet技术的快速发展,众包作为一种灵活有效的解决问题方式,开始受到人们越来越多的关注.由于众包的自由松散组织模式,使得如何有效地控制任务完成质量,并将欺骗类型工作者识别出来,成为目前众包研究中一个急需解决的问题.文中基于对众包工作者提交结果的评估与分析,提出了一种阶段式的动态质量控制策略,同时给出了一个组合式众包结果质量评估方法框架.经过实际数据的测试,文中提出的质量控制策略和众包结果质量评估方法具有较好的效果.面向用户观点分析的多分类器集成和优化技术
摘要：网络上用户生成的数据（User-Generated Data）富含用户的观点（情感）,自动识别这些用户观点对很多的Web应用具有重要的作用,例如推荐系统和电子商务/政务智能系统等.但用户的观点表达通常与领域是相关的,因此对于不同的分析领域,用户难以选择到效果最好的分类器.文中针对用户观点分析问题设计了一个三阶段的多分类器集成框架,在此框架下用户只需指定可用的分类器,系统将自动选择一组最优的分类器组合,将它们的预测结果整合为最终分类结果,同时能够保证分类效果优越于最好的单分类器.针对分类器组的选择过程中面临的组合爆炸问题,文中在考虑分类器的准确度和多样性的基础上,设计了一个贪心算法选择成员分类器,并证明该算法是2-近似的.最后,在不同领域的真实数据集上进行了充分的实验,实验结果验证了文中提出的框架和算法的有效性.一种基于情感符号的在线突发事件检测方法
摘要：如何快速高效检测出海量数据流中的突发事件是目前的研究热点之一.文中针对微博数据流,提出了一种新颖的基于情感符号的在线突发事件检测算法框架.伴随着事件的发生,文本流中情感符号也存在突发现象.文中通过实时监测情感符号变化态势,及时发现情感符号的突发期,达到挖掘突发事件的目的.首先基于频繁模式挖掘和互信息相结合的算法构建情感符号模型,并通过此模型抽取数据流中的情感符号,采用改进Kleinberg算法检测突发期,通过启发式的近邻传播聚类算法检测突发事件并对事件进行合并.同时,算法设置了离线回收机制,对不含情感符号的博文进行回收利用以保证事件概要抽取的完备性.实验表明,该算法可有效地挖掘出突发事件,无论在速度还是精度上都能保证实时在线处理的要求.基于语义相似度的Web信息可信分析
摘要：互联网上的虚假事实陈述严重影响人们有效地获取信息,如何判定事实陈述是否可信成为一个亟待解决的问题.文中提出了一种针对事实陈述的可信判定模型MFSV.该模型针对事实陈述的特点,从互联网上搜集与待判定事实陈述相关的文本信息,度量其与对应事实陈述的语义相似度;同时,该模型考虑了相关文本信息在可信度上的差别,从受欢迎程度和重要程度两个方面度量了相关文本信息来源的可信度,并获取了相关文本信息的可信度排序;根据语义相似度以及可信度排序,衡量了相关文本信息对对应事实陈述可信判定所做出的贡献,并以此为基础实现了待判定事实陈述的可信判定.一系列的实验验证了该模型的合理性及可信判定的准确性.集对社会网络α关系社区及动态挖掘算法
摘要：针对Web社会网络中存在确定-不确定关系,提出一种给定阈值的α关系社区概念,该社区是用集对分析方法构建的集对社会网络,并且其中任意结点之间关系强度大于给定阈值α;根据Web社会网络的动态性,分别设计静态和动态α关系社区的挖掘算法;通过收集DBLP数据集,对其进行抽取、分类、社区挖掘、关系分析等实验,验证了算法的高效性,证明了α关系社区的挖掘更能体现社区存在的动态性,可进一步对其潜在关系社区进行挖掘.基于签到数据的短时间体验式路线搜索
摘要：路线搜索已经广泛地应用于基于位置的服务和旅游路线推荐等领域.现有的关于路线搜索的研究,通常只考虑景点之间路线的流行程度与用户的需求,因此提供的推荐路线并未考虑景点类别的丰富性,存在类别重复的现象.为了能使用户在短时间内体验所在地区不同类别特色的景点,增强旅游体验效果,文中提出一种新的路线搜索：短时间体验式路线搜索（SERS）.该路线搜索方法根据用户给定的查询位置vs、旅行时间限定t以及用户对景点类别选择的集合uc,找到一条非重复多类别且收益最大化的最优景点访问路线.为了有效处理SERS,提出一种预计算结点收益上界值的优化策略,设计了两种优化搜索算法：单收益上界剪枝搜索算法（SUB）和多收益上界剪枝搜索算法（MUB）.优化的搜索算法利用收益上界值剪掉了不可能产生结果的分枝,提高了搜索效率.利用Gowalla和Foursquare社交网站真实的签到数据集进行了充分实验,评估了所提出的算法在不同参数设置下的搜索效率,验证了算法的有效性.一种高效的属性图聚类方法
摘要：图是描述现实世界各类复杂系统的一种普适模型,且许多实际应用中的图是大规模的.图的聚类是理解、分析和可视化大规模图的关键技术之一.现实世界的图往往包含丰富的属性信息,如何综合结构和属性信息进行属性图的聚类是一个新的挑战.大多数的现有方法或者将结构和属性转化为距离,基于传统方法进行聚类;或者只考虑某一方面聚类.文中结合信息论中最小长度原则,基于遗传算法,提出一种高效的属性图聚类方法GA-AGC.通过对属性图聚类问题建模,转化为最小描述长度原则问题;扩展标签传播方法作为遗传算法初始化方法,结合编码减小的局部变异方法,提出一种解决属性图聚类的遗传算法.文中方法无需设定聚类的数目,算法复杂度近似线性于结点和边的数目.真实数据集上的实验验证了算法的有效性和高效性.TDTMS：一种面向XML数据的结果子树构建算法
摘要：构建结果子树是XML关键字查询得以完成的关键步骤之一.针对已有方法求解子树效率低的问题,文中提出一种自顶向下的子树构建算法——TDTMS.TDTMS以自顶向下、深度优先的方式求解满足条件的子树根结点,避免了已有方法求解SLCA结点时存在的公共祖先重复处理问题.对于给定的子树根结点,TDTMS以自顶向下、广度优先的方式构建子树,可以在建树过程中快速裁剪无用结点,从而获得了最小的时间和空间复杂度.最后通过实验验证了TDTMS在时间和空间两方面的性能优势.基于结点权重模型的XML片段检索策略
摘要：当用户向XML检索引擎提交查询后,返回的结果通常远远多于用户的期望,返回结果中难免有一些不相关的文档或结点.对于以文档为中心的XML文档集合,XML片段检索是根据用户的查询,从XML检索引擎返回的XML文档或结点中抽取出仅包含数百字节的片段,用户可以通过该片段判断片段所在的XML文档或结点与查询的真实相关性,以决定是否有必要进一步阅读,从而有效地提高从XML文档中获取信息的效率.该文提出了基于结点权重模型的XML片段检索策略.该策略先利用结点权重模型ATG（平均主题概括强度）对XML文档集中的标签或路径设置权重,再将该权重用于BM25模型,得到BM25NW检索模型.在利用BM25NW检索出XML结点后,对结点中定长窗口进行评分,考察其是否适合作为片段内容.最后在保证信息冗余较小的条件下,选择得分较高的窗口内容组成片段返回给用户.INEX 2011片段检索任务上的评测结果显示,基于结点权重模型ATG的XML片段检索策略具有很强的竞争力,性能明显优于其它参赛系统.一种新颖的医学图像建模及相似性搜索方法
摘要：医学图像采集和存储技术的发展导致了相关数据的飞速增长,这些医学图像数据能够有效地辅助医生进行精确的诊断,但由于医学图像在相似性搜索方面要求图像匹配的精度远高于普通图像,所以目前仍没有一种有效的方法解决医学图像的相似性搜索问题.文中首先提出一种不确定定点图模型（ULG,Uncertain Locationgraph）,并针对脑部CT图像的固有特点,提出一种基于脑部CT图像纹理的从图像到不确定定点图的建模方法,继而提出一种基于不确定定点图的相似性搜索算法,并通过一种有效的索引结构,有效地减少了无意义的查询处理,降低了搜索时间.实验结果表明,该方法可以更精确地找出具有相似纹理的脑部CT图像.基于方向梯度的H.264帧内预测模式选择算法
摘要：率失真优化（RDO）技术的应用大幅提高了H.264的编码性能,但全搜索方式下,每一宏块所有模式都要进行R-D代价计算,复杂度非常大.文中利用参考像素与当前块之间的方向梯度检测预测方向上的纹理方向与边缘强度,预先筛除部分方向梯度较大的预测模式,形成一种基于方向梯度的快速帧内预测模式选择算法,并利用预测模式的空间相关性采用最有可能模式替换直流模式作为缺省候选模式,改进了基本算法.对10个标准序列进行测试,两个算法应用在亮度分量帧内预测模式选择中均比JM18.0全搜索方式减少了50%以上的编码时间,且编码性能损失很小,保持峰值信噪比与JM全搜索方式相同时,基本算法码率平均上升2.361%,改进算法码率平均上升1.477%.