无线传感器网络中top-k连接查询处理

无线传感器网络是物联网核心组成部分之一,数据查询处理是无线传感器网络中很重要的一个研究领域.连接查询能在不同的位置监视相似的网络环境,top-k连接查询能进一步得出组合得分最大(或最小)的k个相似网络环境.top-k连接查询根据得分函数计算匹配结果的组合得分,并报告组合得分结果最大(或最小)的k个匹配节点对.文中提出了基本top-k连接算法BTJQ.该算法首先按照得分属性值从大到小对所有元组排序,然后依次取出元组,产生连接结果.对每个连接结果按照得分函数计算组合得分,如果满足停止条件,则停止取元组,并输出连接结果.在BTJQ基础上,作者提出了集中式top-k连接算法CTJQ和优化的集中式top-k连接算法OCTJQ.针对特定应用场景,作者进一步提出了分布式top-k连接算法DTJQ.最后,在真实数据集上验证了各算法.实验结果表明,文中算法好于经典连接算法SENS-Join.     

基于用户反馈的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查询

联盟数字图书馆(DLF)可以为用户提供一次请求访问多个数字图书馆资源的途径。一个查询提交后,会产生若干带有概率的重写形式,采用top-k算法可以获得最近似的k个结果。在传统的top-k算法中,同时考虑依据偏好形成的得分函数与概率直接的关系,那么,在一个DLF中,最终用户就会获得结果中最符合其偏好且概率最高的结果。通过完善数字图书馆联盟DLF的概率的信息集成模型,在进行模式的自动映射时,会产生几种候选的模式对应关系,提交查询时,会按照各种映射形式形成多个查询的重写形式,采用树结构来阐述opt_U-kRanks查询时,如果定义tm为在排序位k时的概率,那么,通过条件的设定,可以快速评估tm是否是在位置上的适合的解,从而实现理想的查询效果。     

遗憾最小化查询研究综述

面临大量数据时,如何从中摘取一部分感兴趣的数据帮助用户进行决策是数据库系统的一项重要功能.在过去几十年里,top-k和skyline查询是两种最常用的技术手段,但他们分别存在不能控制输出结果大小与需要用户提供效用函数的缺陷.为克服两者的缺陷,k代表点查询技术应运而生;其中性质较好、受到较多关注的是k-遗憾查询.本文首先...     

一种动态维护分布式环境下top-k集合的近似算法

在分布式数据流场景中,如何动态维护top-k集合并尽可能地降低通信开销是非常重要的.通常的做法是:把大量的数据从分布式节点传送到中央节点,然后在中央节点计算top-k集合.这样的通信开销非常大,在许多场合下是根本无法实现的.提出了一种高效地动态维护分布式环境下top-k集合的近似算法top-k'.在算法中对一个top-k查询,通过动态维护k'(K<,max>≥k'≥k)个最高积分的元组,可以从中选取积分最高的k个元组返回.实验表明top-k'显著降低了各节点与中央协调节点之间的通信代价.     

海量数据上有效的top-k Skyline查询算法

在许多应用中,Skyline查询是一种十分重要的查询类型,它在潜在的巨大的数据空间中返回不被其他元组支配的用户感兴趣的元组,但是Skyline查询无法控制返回结果的数量。处理一个新的top-k Skyline查询问题,该查询返回支配分数最大的k个Skyline元组,从而控制了需要向用户返回的查询结果数量。分析发现,大多数现有算法忽略了利用支配分数作为限制Skyline查询的结果数量的度量。提出一个新的基于表扫描的RSTS(ranked Skyline with table scan)算法来有效计算海量数据上的top-k Skyline结果。RSTS算法首先对表执行预排序操作,保证预排序表的元组按照对有序列表的round-robin扫描的顺序排列。RSTS算法包括两个阶段。阶段1利用对预排序表的顺序扫描来获得候选元组。阶段2计算候选元组的支配分数并返回结果。可以证明,RSTS算法具有早结束特性,并给出其扫描深度的理论分析。提出对于候选元组的剪切操作,理论剪切效果表明,绝大多数的Skyline结果可以直接丢弃。实验结果表明,RSTS算法可以有效计算top-k Skyline结果。     

联机分析查询处理中的一种聚集算法

联机分析处理(online analytical processing,简称OLAP)查询是涉及大量数据的即席复杂查询,从SQL(structured query language)角度来看,这些查询通常都包含多表连接和分组聚集操作.从OLAP查询处理角度出发,提出一种新的基于排序的聚集查询算法MuSA(sort-based aggregation with multi-table join).该方法充分考虑到数据仓库星型模式的特点,将聚集操作和新的多表连接算法MJoin相结合,排序时采用     

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

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

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

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

数据库安全功能测试自动化框架设计与实现

传统的top-k查询为顾客返回符合其偏好的产品集合,reverse top-k查询则返回将给定产品作为top-k结果的偏好集合。reverse top-k查询由于能帮助生产者评估产品对顾客的影响,因此在商业分析中具有重要价值。现有的reverse top-k查询假设数据是精确的,许多现实应用中,数据的不确定性广泛存在。将reverse top-k查询扩展到不确定数据上,并给出了基于物化视图的高效查询算法GMV。实验结果表明,GMV算法能够减少需要计算的偏好数量,具有较高的计算效率。