不确定性Top-K查询处理

高效Top-K查询处理在涉及大量数据交互的应用中是一项重要技术,随着应用中不确定性数据的大量涌现,不确定性数据的管理逐渐引起人们的重视.不确定性数据上Top-K查询从语义和处理上都呈现出与传统Top-K查询不同的特点.在主流不确定性数据模型和可能世界语义模型下,学者们已经提出了多种不确定性Top-K查询的语义和处理方法.介绍了当前不确定性Top-K查询的研究工作,并对其进行分类,讨论包括语义、排序标准、算法以及应用等方面的技术.最后提出不确定性Top-K查询面临的挑战和下一步的发展方向.

两层传感器网络中安全Top-k查询协议

在两层结构传感器网络中,存储节点收集传感器采集的数据,负责处理Sink的查询.在敌对环境中,存储节点可能会被攻击者妥协而泄露传感器所采集的敏感数据以及向Sink返回不完整的或虚假的查询结果.为此,提出了一种安全Top-k查询协议:SecTQ,SecTQ在保证存储节点正确执行查询的同时能有效防止敏感数据的泄露.为了保护数据的隐私性,首先将不同传感器采集的数据之间的直接比较转换成传感器采集的数据与Sink提供的查询比较值进行比较,并提出了一种基于扰动多项式函数的隐私保护方案.该方案利用扰动函数对传感器采集的数据和Sink提供的查询比较值进行编码,保证存储节点在不知道数据和查询比较值真实内容的情况下正确地执行查询处理.为了保护查询结果的完整性,提出了一种称之为水印链的方案,该方案能有效检测查询结果的完整性.

面向隐私保护的两层传感网Top-k查询处理方法

无线传感器网络中的隐私保护技术已经成为研究热点,其中具有隐私保护能力的Top-k查询已经成为富有挑战性的研究问题.提出了一种基于前缀编码验证(PMV)机制的两层传感器网络隐私保护Top-k查询处理方法.通过引入PMV机制,并利用加密和Hash消息身份验证编码技术,使感知节点对采集到的数据进行加密和编码处理,并上传至存储节点;存储节点利用PMV机制实现在无需感知数据明文参与下的数值线性关系比较,进而计算包含查询结果的最小候选密文数据集,并发送给Sink节点;最终由Sink解密密文数据,完成Top-k查询结果计算.为了降低感知节点能耗,给出基于Hash技术的能量优化策略.理论分析和实验结果表明,该方法能够确保数据的隐私安全性,且性能表现优于现有工作.

无线传感器网络中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查询成为一个急需解决的难题。提出了一种利用控制关系分析(dominate relationship analysis,DRA)的不确定数据Top-k查询算法。该算法通过分析元组之间的控制关系,将那些最有可能成为Top-k查询结果的元组选择出来,这样大大减少了参加运算的元组数量,显著提升了查询效率。并且在数据库更新时,能够判断出此更新是否影响到之前得到的查询结果,从而决定是否需要重查,减少了重查的计算量。

集中式P2P环境下有效的Top-K查询

目前大多数的Peer-to-Peer(P2P)系统只支持基于文件标识的搜索,用户不能根据文件的内容进行搜索。Top-k查询被广泛地应用于搜索引擎中,获得了巨大的成功。可是,由于P2P系统是一个动态的、分散的系统,在P2P环境下进行top-k查询是具有挑战性的。提出了一种在集中式P2P系统中的基于中心文档的层次化的top-k查询算法。首先,采用层次化的方法实现分布式的top-k查询,将结果的合并和排序分散到P2P网络中的各个节点上,充分利用了网络中的资源。其次,将节点返回的结果录入到中心文档中,然后确定其分数上限,对节点进行选择,提高了查询效率。

传感器网络中基于抽样的带权近似Top-k查询算法

提出一种适用于传感器网络的抽样带权阀值过滤近似Top-k聚集查询算法.该近似算法会将无线传感器网络划成几个两两不相交的簇进行处理,在汇聚节点进行预处理以及在各个簇内进行抽样过滤处理,在抽样过程中给可靠而重要的节点赋上相应更大的权值,同时根据节点采集的信息具有时间相关特性,在簇内进行抽样阀值过滤处理,每个簇头节点都会接收到该簇内的Top-k候选子集,然后将每个簇的子集发送给Sink节点,该Sink节点将接收到能代表整网Top-k样本候选集.仿真实验结果显示该算法只需发送少量的数据,更小的抽样样本,并能满足任意精度要求.

基于反馈的无线传感器网络Top-K查询处理算法

无线传感器网络是一种应用非常广泛的网络。Top-K查询是无线传感器网络应用的基础,基于某种比较规则,其返回网络数据的前K个值。文章提出一种基于转发树结构的反馈式Top-K查询处理算法,该算法利用父亲节点与孩子节点的交互结果。在每一轮交互中,孩子节点根据父亲节点的反馈信息有选择性地返回部分数据,以达到减少发送数据量的目的。模拟实验表明该算法具有较好的节能效果。

MapReduce框架下的不确定数据Top-k查询计算

Top-k查询是不确定性数据管理中普遍采用的一种技术.基于参数化排名函数的Top-k查询语义是近年来提出的各种查询语义的统一.文中针对海量不确定数据,提出一种基于MapReduce框架的Top-k计算的有效方法.通过分析基于参数化排名函数的不确定数据Top-k查询语义,设计一种获得未计算元组的排名函数值上界的算法,避免计算所有元组的排名函数值,解决Top-k计算中的剪枝问题.在MapReduce计算模型中提出两种不同的策略来实现该算法.文中针对单机环境和Hadoop分布式计算平台进行两组不同的对比实验.实验表明在处理海量不确定数据时,该算法在计算时间上有较高的性能提升.

一种能量有效的双层传感器网络Top-k安全查询机制

在双层传感器网络中,高层具有相对较高存储能力和计算能力的存储节点负责收集低层资源受限的传感器节点的感知数据,完成数据存储和回答用户的查询请求.但是由于传感器网络经常部署在不安全环境下,存储节点可能被俘获从而向用户返回错误的查询结果,因此查询结果的正确性验证至关重要.针对双层传感器网络下时隙top-k查询,提出了一种能量有效的top-k安全查询机制RSTOPK,用以验证查询结果的认证性和完全性.通过结合计算承诺的假设检验方法,有效提高了对错误查询结果的检测率,并有效减小了查询结果验证引入的额外通信开销.理论分析和模拟实验结果表明了其有效性.

对等网络环境下数据管理系统上的Top-k查询

对等网络(Peer-to-Peer)模型是一种新型的体系结构模型,许多优势有待于进一步发掘,拥有广阔的应用前景。提出了一种在P2P环境下共享数据库的新框架:基于关键词查询的数据库共享。将每个节点上的数据库看成是一个文档集,用户不用考虑数据库的模式结构信息,简化了不同节点数据库模式间的映射过程,能够较好地适应P2P分散和动态的特性。

基于Top-k查询约束的深网增量爬取

深网数据源的动态性、自治性和体量使第三方应用难以完全爬取所有Web数据.文中研究查询类型(仅允许Top-k查询)和查询资源约束下深网数据源爬取问题,提出基于Top-k查询约束的深网增量爬取方法,结合历史数据和领域知识,优化总体数据质量.首先基于查询树获得有效查询,利用历史数据和领域知识估计查询变化和查询代价.然后,基于估计的查询代价和数据质量,近似选择最优的查询子集最大化总体数据质量.实验表明文中方法较好地提高动态Web数据库爬取的效率和数据质量.

一种基于动态修正值的分布数据流Top-K查询处理算法

对分布式数据流进行查询,得到数值最大的K个对象(Top-K观测查询),最直接的解决方法是由中心结点处理分布式数据流,但这种方法导致中心结点和网络负载较大。提出一种基于动态修正值的查询算法,通过对观测数据进行计算得到修正值,并利用该修正值对不同结点处的对象数据进行操作,从而无需将结点数据流全部发送到中心结点就能完成Top-K观测查询。因而可以减少对网络带宽的要求和降低中心结点的负载,同时还能保持查询结果的完全准确。

一种处理Top-k逆向查询的分支界定算法

Top-k逆向查询在现实生活中有着广泛应用。目前,计算Top-k逆向集最有效的算法是逆向Top-k算法。该算法的效率在处理Top-k逆向查询时受到明显的限制。为了解决这些限制,提出一种直观的分支定界算法来高效地处理Top-k逆向查询,并讨论新颖的优化方法以提其高能。实验评估表明,该算法的效率远胜于逆向Top-k算法。

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

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

基于不确定数据的查询处理综述

不确定数据在一些重要应用领域中是固有存在的,如传感器网络和移动物体追踪。在不确定数据上使用传统的查询方法会使查询结果出现偏差,不能满足用户的需求。因此,基于不确定数据的查询处理受到了越来越多的关注。与在确定数据上查询不同,不确定数据上的研究工作将概率引入到数据模型中来衡量不确定对象成为结果集中元素的可能性。由于问题定义和数据模型的不同,不确定数据上的查询类型也多种多样。从问题定义、数据模型、剪枝策略和算法等角度,对基于不确定数据的范围查询、top-k查询以及skyline查询进行了介绍。

基于P2P的智能交通信息平台构成及数据查询技术研究

智能交通系统(ITSI,ntelligent Transportation System)是现今社会公认的能比较全面实时有效地解决交通运输领域,特别是交通拥挤、道路阻塞、交通事故和车辆污染等问题的最佳途径。然而基于传统网络技术结构的智能交通信息平台存在着许多不足之处。将P2P网络(peer-to-peer networks)技术应用于智能交通信息平台可以解决由于传统网络结构不足而引起的性能问题。

社交网络服务中基于位置的Top-k查询方法

针对社交网络服务中汇聚的大量带有地理和社交属性的数据,提出一种改进的综合考虑用户位置和好友关系的个性化位置Top-k查询方法。首先,在传统Top-k空间查询方法的基础上,将用户的好友关系及好友签到统计信息引入评分函数,以便对查询结果进行个性化排序。然后,改进IR-tree索引结构以支持对位置信息和社交关系的混合索引。最后,在查询过程中采用基于优先级队列的最佳优先遍历方法进行剪枝,从而减少搜索空间。实验表明,改进的评分函数、索引结构和遍历方法能够实现社交网络环境中个性化且高效的Top-k查询。

变压器缺陷管理系统中不确定性数据的处理

针对变压器缺陷管理中缺陷定级时专家定级数据的不确定性,利用不确定数据top-k查询的相关理论,建立了变压器缺陷定级不确定性数据模型——可能世界模型,并确定专家定级数据排序,排在首位的定级结果作为该缺陷的定级结果.然后根据定级结果安排消缺任务.