基于x-tuple的概率阈值top-k查询算法

不确定数据库中的概率阈值top-k查询是计算元组排在前k位的概率和,返回概率和不小于p的元组,但现有的查询语义没有将x-tuple内的元组进行整体处理.针对该情况,定义一种新的查询语义——概率阈值x-top-k查询,并给出查询处理算法.在该查询语义下采用动态规划方法求取x-tuple内每个元组排在前k位的概率和,对其进行聚集后做概率阈值top-k查询,并利用观察法、最大上限值等剪枝方法进行优化.实验结果表明,该算法平均扫描全体数据集中60％的数据即可返回正确结果集,证明其查询处理效率较高.     

TKEP:海量数据上一种有效的Top-K查询处理算法

在许多应用领域中,top-k查询是一种十分重要的操作,它根据给定的评分函数在潜在的巨大的数据空间中返回k个最重要的对象.不同于传统的TA算法,NRA算法只需要顺序读就可以处理top-k查询,从而适合于随机读受限或不可能的场合.文中详细地分析了NRA算法的执行行为,确定了增长阶段和收缩阶段中每个文件需要扫描的元组个数.文中发现在海量数据环境中,NRA在增长阶段需要维护大量的候选元组,严重影响了算法的执行效率.所以,文中提出一种新的海量数据上的top-k查询算法TKEP,该算法在查询的增长阶段就执行早剪切,从而大大减少增长阶段需要维护的候选元组.文中给出了早剪切操作的数学分析,确定了早剪切操作的理论和实际剪切效果.据作者所知,该文是第一篇提出在top-k查询的增长阶段执行早剪切的文章.实验结果表明,和传统的NRA相比,TKEP在增长阶段维护的元组数量减少3个数量级,需要的内存量减少1个数量级,TKEP算法获得1个数量级的加速比.     

无线传感器网络中一种能量高效的skyline查询算法

针对分布式无线传感器网络环境下的skyline查询问题,提出了KSkySenor算法,有效地从传感器网络中获取更有意义的skyline结果;KSkySenor算法对感知数据进行预处理计算每个元组的支配能力,按照支配能力与各维度值之和对其进行排序,设计了一个基于聚簇的结构用于收集所有传感器读数,提出了一个剪枝方法用于渐进的从传感器网中获取skyline结果集;实验中分别改变传感器网络规模大小、数据维度、支配属性个数k,对KSkySensor算法进行测试,实验结果表明KSkySenor算法与先前的skyline查询处理算法相比具有很高效率,减少了无线传感器网络中的数据传输量,延长了网络生命周期。     

DBCC-Join:一种新的高速缓存敏感的磁盘连接算法

在许多应用领域中,top-k查询是一种十分重要的操作,它根据给定的评分函数在潜在的巨大的数据空间中返回k个最重要的对象.不同于传统的TA算法,NRA算法只需要顺序读就可以处理top-k查询,从而适合于随机读受限或不可能的场合.文中详细地分析了NRA算法的执行行为,确定了增长阶段和收缩阶段中每个文件需要扫描的元组个数.文中发现在海量数据环境中,NRA在增长阶段需要维护大量的候选元组,严重影响了算法的执行效率.所以,文中提出一种新的海量数据上的top-k查询算法TKEP,该算法在查询的增长阶段就执行早剪切,从而大大减少增长阶段需要维护的候选元组.文中给出了早剪切操作的数学分析,确定了早剪切操作的理论和实际剪切效果.据作者所知,该文是第一篇提出在top-k查询的增长阶段执行早剪切的文章.实验结果表明,和传统的NRA相比,TKEP在增长阶段维护的元组数量减少3个数量级,需要的内存量减少1个数量级,TKEP算法获得1个数量级的加速比.     

基于用户反馈的top-k查询修改算法

top-k查询主要用来从海量的数据中返回用户最为偏好的k个对象.目前已经有大量的研究工作致力于top-k查询中的性能研究,近年来针对top-k查询结果进行解释的研究逐渐得到了广泛的关注.在top-k查询中,由于用户不能精确地指定自己的偏好,因此针对top-k查询的结果用户可能产生这样的质疑:"既然连对象p都出现在top-k结果中,为什么我期望的对象m块没有出现在top-k结果/"针对用户这样的疑问,提出了一种基于用户反馈的top-k查询修改算法,该算法首先定义了用来衡量初始化top-k查询变化的评估模型函数,基于该评估模型函数,使用抽样方法得到候选权重集合,针对每一个候选权重通过渐进式top-k算法来得到新的最优化查询.最后在模拟数据上验证了提出算法的效率.     

结构化网络中聚合Top-K查询优化技术

top-k查询在分布式环境中引起越来越多的关注,但是现存的一些top-k算法大都只适用于集中式网络.提出了一个解决分布式网络中top-k查询的新方法—Histogram-Container算法(简称为HC算法),它不仅网络延迟小,网络带宽花费少,而且能够运行在任何结构的分布式网络中.本文将基于一个树型拓扑网络来说明如何使用本地的直方图和bloom filter信息来优化查询,以及如何在中间节点进行部分结果的合并.实验评估和性能分析表明HC算法在网络带宽消耗和查询响应时间方面要优于其他同类方法.     

基于最小Steiner树的关键词查询方法

在关系数据库中,关键词查询无需用户学习查询语言和数据库模式相关知识,而且有效地扩大了查询范围.采用元组图描述关系数据库中元组关系,可使关键词查询问题转化为元组图的最小Steiner树求解问题.本文提出元组图上基于相似度的边权重计算方法,使边权重能够反映元组与关键词相似度的大小.然后,鉴于最小Steiner树求解问题是NP-完全问题,提出按照贪心策略执行Dijkstra算法的最小Steiner树较优解求解算法.最后,通过实验对算法进行了分析和验证.     

不确定图数据库中高效查询处理

近年来,在多种领域中产生的大量数据都可以自然地建模为图结构,比如蛋白质交互网络、社会网络等.测量手段的不准确性以及数据本身的性质导致不确定性在很多图数据中普遍存在.文中研究不确定图数据库中的高效查询处理方法.首先给出一种数据模型来表示图的不确定性.鉴于对用户提交的查询图通常会产生大量匹配结果,高效得到概率最大的k个匹配常常更具有现实意义.因此文中形式化提出概率top-k子图匹配查询的问题.为了解决提出的查询问题,以附带概率信息的邻居子图为基础,设计了一种有效的索引结构.另外,提出一种高效的基于索引的查询处理方法.该查询处理方法的核心是一个基于搜索树的匹配算法,其中运用了一种概率剪枝技术来提高性能.实验结果表明,所提出方法具有良好的效率和可扩展性.     

无线传感器网络上的极值区域查询处理

提出了无线传感器网络上的一种查询——极值区域查询(peak region query,简称PRQ),即用户指定查询区域的大小和形状,例如半径为R的圆形区域,然后需要查询传感器网络中的某个区域,使得区域内传感器节点数据的某种聚集值最大.定义了极值区域查询的概念,并提出一种集中式算法以求解查询结果.由于传感器节点的能量有限,为了降低查询处理过程中的能耗,提出了分布式算法EXQ(an algorithm for extreme value query processing).与集中式算法相比,EXQ不但显著降低了能耗,而且使得每个传感器的能耗更加平均,从而延长了网络的使用寿命.EXQ的基本思想是,将整个网络划分为若干相互重叠的子区域,对每个子区域通过本地数据聚集得到一个本地结果,然后对这些结果再进行全局数据聚集从而得到查询结果.从理论和实验两方面分析和比较了集中式算法和EXQ的能耗和节点负载分布.     

无线传感器网络多查询的节能优化

提出了一个无线传感器网络多查询的节能优化方案。该方案通过建立相似查询判断算法把多查询中的相似查询分为一组,并在每一组找一个能使传输能耗达到最小的中继节点作为处理节点。组内节点的数据都传送到该处理节点,并由该节点利用数据处理函数处理数据,然后再传到基站。这样就减少了网络中数据的传输量,从而有效地节省了网络的能量,达到能量的最大化利用。