分布式网络中连续时间周期的全局top-K频繁流测量

在分布式网络中,测量top-K频繁流对资源分配、安全监控等应用至关重要。现有的top-K频繁流测量工作存在不适用于测量分布式网络流量或只考虑单时间周期等局限。为此,提出了分布式网络中连续时间周期的全局top-K频繁流测量方案,在分布节点中布置了紧凑的概率数据结构来记录网络流信息,每个时间周期结束后分布节点向中心节点发送必要信息,中心节点汇聚得到从测量开始至当前时间周期的全局top-K频繁流。考虑到每条流可能出现在一个或多个测量节点,使用了不同的方法来减少传输开销。对于每条流只会出现在单一节点的情况,采用传输分段最小值的方法来获得阈值,实验结果表明这种方法减少了全量传输超过50%的传输开销。对于每条流会出现在多个节点的情况,提出了多阶段无误差处理方法和单阶段快速处理方法,分别应对不能容忍误差的场景和实际高速网络流量,相比每个时间周期都使用已有单周期方法,传输开销的实验表现降低了两个数量级。最后还提出了一种利用历史平均增值信息降低通信延迟的方法,实验结果表明该方法有效降低了限制信息的平均相对误差。

一次性条件下top-k高平均效用序列模式挖掘算法

针对传统序列模式挖掘(SPM)不考虑模式重复性且忽略各项的效用(单价或利润)与模式长度对用户兴趣度影响的问题,提出一次性条件下top-k高平均效用序列模式挖掘(TOUP)算法。TOUP算法主要包括两个核心步骤:平均效用计算和候选模式生成。首先,提出基于各项出现位置与项重复关系数组的CSP(Calculation Support of Pattern)算法计算模式支持度,从而实现模式平均效用的快速计算;其次,采用项集扩展和序列扩展生成候选模式,并提出了最大平均效用上界,基于该上界实现对候选模式的有效剪枝。在5个真实数据集和1个合成数据集上的实验结果表明,相较于TOUP-dfs和HAOP-ms算法,TOUP算法的候选模式数分别降低了38.5%~99.8%和0.9%~77.6%;运行时间分别降低了33.6%~97.1%和57.9%~97.2%。TOUP的算法性能更优,能更高效地挖掘用户感兴趣的模式。

大图中多样化Top-k模式挖掘算法研究

频繁模式挖掘(Frequent Pattern Mining,FPM)是图数据挖掘领域的一项重要任务。该任务的目标是从图数据中找到出现频次大于给定阈值的所有模式。近年来,随着社交网络等大规模图数据的涌现,单一大图上的FPM问题受到广泛关注,并得到了较为充分的研究,取得了一系列研究成果。然而,已有技术大都存在着计算成本高、挖掘结果理解困难以及并行计算难等问题。针对上述问题,文中提出了一种从大规模图数据中挖掘多样化top-k模式的方法。首先设计了一个多样化函数,用于度量模式集合的多样性;随后设计了一种面向分布式图数据,具有提前终止特性的分布式挖掘算法DisTopk,以实现多样化top-k模式高效挖掘。在真实图数据和合成图数据上进行了大量实验,结果表明,与传统分布式挖掘算法相比,DisTopk算法能更高效地挖掘多样化top-k模式。

Top-k空间偏好查询方法研究

随着无线通信技术的发展和智能移动终端的广泛普及,基于位置的服务已经融入了人们生活的方方面面。其中,Top-k空间偏好查询在地理信息系统、城市建设规划、资源调度与分配、旅游规划等领域具有重要的意义。Top-k空间偏好查询是根据空间对象周围的特征对空间对象进行等级评价,并返回具有最高等级评价的k个空间对象。目前,对于Top-k空间偏好查询的研究主要集中在欧式空间和路网环境,本文对欧式空间和路网环境下的Top-k空间偏好查询方法进行分析和比较。

基于本地差分隐私的网络测量Top-k目的地址估计研究

针对网络测量中的Top-k目的地址问题,设计了基于布谷鸟过滤器的ε-本地差分隐私Top-k目的地址估计机制。在保护隐私的前提下,该机制能够提高对Top-k目的地址的估计效果。采用了多轮迭代方法,将布谷鸟过滤器和本地差分隐私模型结合,在服务器端和客户端进行了一轮交互。理论分析部分证明了所提出的机制符合本地差分隐私模型,并在数据集上进行了实验,对比了F1分数、NCR分数以及L1误差,验证了所提机制的有效性。

道路网多用户偏好Top-k天际线查询方法

已有的天际线(Skyline)查询主要聚焦于单用户场景,并基于单用户模型进行Skyline计算,而较少考虑道路网环境下多用户情况.为了弥补已有方法无法解决道路网络环境下多用户偏好和权重Top-k Skyline查询问题的不足,提出了一种基于道路网环境下多用户偏好Top-k Skyline(multi-user preference Top-k Skyline,MUP-TKS)查询方法.在道路网环境下考虑多用户的不同偏好和权重进行Skyline查询,可以快速得到符合查询用户群偏好和权重的结果集,提供用户群更好的决策支持.MUP-TKS首先通过所提的G_DBC算法,利用道路网中数据点与查询点之间的位置关系和新的索引结构Vor-R*-DHash剪枝、过滤数据点,从而得到距离较优集;再利用静态Skyline集不变的性质,预先计算、保存该集合;然后通过所提的新支配关系对距离较优集与静态Skyline集取并集后的集合S进行放松支配;最后利用所提TK_DC算法对经过放松支配后的候选结果集打分,依据数据点得分情况,排序输出Top-k个结果集返回用户群.理论研究与实验表明,所提方法具有较好的效率与可靠性.

卷积神经网络的top-k相似节点搜索方法

针对复杂网络环境下搜索与目标节点文本和结构均相似的top-k节点问题,本文提出了一种基于卷积神经网络的top-k相似节点搜索算法LRE-CNN.对于一个无向带权复杂网络,首先为网络中每个节点构造基于度和权重的最近邻网络模型,利用最近邻网络相对加权熵计算度和权重对节点结构的影响.然后,通过KL散度比较节点对的差异生成节点结构相似度,从而筛选出目标节点的候选相似节点.最后,利用卷积神经网络(CNN)抽取目标节点和候选相似节点的文本特征间的潜在关系,从而预测出与目标节点文本结构均相似的top-k节点.通过在不同规模的复杂网络上进行实验,并与现有主流相似节点搜索方法进行对比,实验结果表明所提方法具有较高的检索准确率,同时具有较高的执行效率,能够有效适用于大规模复杂网络环境下的相似节点top-k搜索.

通用可重组安全的多方求解Top-k协议设计

对于一个定点数多重集合S,第k小元素(又称Top-k元素) x∈S是指当集合中元素按照递增顺序排列时,刚好位于第k位置的元素.两方或多方安全求解它们输入的公共集合X的Top-k元素,是安全多方计算应用领域的经典案例.它能够使互不信任的多个数据持有方在不泄露自身数据的前提下,获取更大样本集合上的统计信息,从而实现隐私保护决策.本文提出了一种两方或多方分布式持有定点数数据的场景下,不依赖可信第三方,安全求解它们数据集合X中Top-k元素的协议,证明了其通用可重组(UC)安全性.协议使用了基于秘密分享的比较及加法安全多方计算协议作为构造模块,巧妙地从高到低按位依次确定并公布Top-k元素的p进制定点数表示.协议实现了O(logpM)的通信轮次复杂度,其中M为p进制数的最大取值, p为约定的定点数基数.实验证明,对于常见网络环境(包括局域网和广域网),当p=2^(i)(i=2,···, 8)时,协议的通信时间和总运行时间均显著优于其他现有的Top-k求解协议.

一种基于上界值剪枝的用户敏感top-k dominating查询方法

信息化社会带来了数据量的快速增长,但也导致数据的完整性和价值密度越来越低,如何从海量不完整数据中快速找到有价值的信息用于用户个性化推荐,已经成为研究的热点。结合上界值剪枝算法,提出一种用户敏感top-k dominating(TKD)查询方法(USTD)。该方法首先结合用户兴趣度,重新定义了不完整数据集上对象的支配关系及其度量方法,计算对象的权重支配分数;然后以重新定义的支配关系,证明了依据上界值可剪枝的条件;最后将上界值剪枝条件融于USTD的查询过程,以从数据集中快速找到前k个满足用户兴趣的数据。实验结果表明,USTD算法在查询速度上有一定提升,在查询结果的评分上具有显著优势。

云环境下一种强隐私保护的安全Top-k查询方案

在一个多用户应用场景下,为了防止云勾结一个数据拥有者或一个数据使用者对授权用户的查询隐私进行合谋攻击,构建了云计算环境下针对查询隐私的合谋威胁模型,并实现了一种高效的强隐私保护查询方案.方案采用动态的安全查询索引结构,该结构可以保证外包数据的安全性,且适用于数据文件频繁动态更新的多用户环境,极大地提高了系统的可伸缩性和可用性.为了满足用户的个性化查询需求,依据关键字权重对查询结果进行秘密相关性排序,实现了安全的top-k查询.

不确定性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.

基于Spark的Top-k对比序列模式挖掘

对比序列模式(distinguishing sequential pattern,DSP)指在目标类序列集合中频繁出现,而在非目标类序列集合中不频繁出现的序列.对比序列模式能够描述2个序列集合间的差异,有着广泛的应用,例如:构建序列分类器,识别DNA序列的生物特征,特定人群行为分析.与挖掘满足支持度阈值要求的对比序列模式相比,挖掘对比度top-k对比序列模式能避免用户设置不恰当的支持度阈值.因而,更易于用户使用.但是现有的top-k对比序列模式挖掘算法难以处理大规模序列数据.对此,设计了一种基于Spark的top-k对比序列模式并行挖掘算法,称为SP-kDSP-Miner.此外,为了提高SP-kDSPMiner的效率,针对Spark结构的特点,设计了候选模式生成策略和若干剪枝策略,以及候选模式对比度的并行计算方法.通过在真实数据集与合成数据集上的实验,验证了SP-kDSP-Miner的有效性、执行效率和可扩展性.

不产生候选项集的TOP-K高效用模式挖掘算法

目前TOP-K高效用模式挖掘算法需要产生候选项集,特别是当数据集比较大或者数据集中包含较多长事务项集时,算法的时间和空间效率会受到更大的影响.针对此问题,通过将事务项集和项集效用信息有效地保存到树结构HUP-Tree,给出一个不需要候选项集的挖掘算法TOPKHUP;HUPTree树能保证从中计算到每个模式的效用值,不需要再扫描数据集来计算模式的效用值,从而使挖掘算法的时空效率得到较大的提高.采用7个典型数据集对算法的性能进行测试,实验结果证明TOPKHUP的时间和空间效率都优于已有算法,并对K值的变化保持平稳.

基于索引效用的Top-k高效用项集挖掘方法

已有的Top-k高效用项集挖掘为了保持向下封闭性,利用项集的事务效用代替其真实效用,使得项集效用被估计得过大,导致剪枝效果不好,挖掘效率较低.针对这一问题,提出了索引效用的概念,在此基础上建立两级索引,并进行索引剪枝,增强了挖掘中剪枝的效果,提高了Top-k高效用项集挖掘的效率;此外,通过建立效用矩阵,支持对项集效用的快速计算,进一步提高了挖掘效率.不同类型数据集上的实验验证了所提出的Top-k高效用项集挖掘方法的有效性和高效性.

Web数据库top-k多样性关键字查询推荐方法

Web数据库用户通常使用他们熟知的关键字表达查询意图,这可能导致获取的结果不能很好满足其查询需求,因此为他们提供top-k个与初始查询语义相关且多样化的候选查询有助于用户扩展知识范围,从而更准确完善地表达其查询意图.提出一种top-k多样性关键字查询推荐方法.1)利用不同关键字在查询历史中的同现频率和关联关系评估关键字之间的内耦合和间耦合关系;2)根据关键字之间的耦合关系构建语义矩阵,进而利用语义矩阵和核函数方法评估不同关键字查询之间的语义相关度.为了快速返回top-k个与初始查询相关且多样性的候选查询,根据查询之间的语义相关度,利用概率密度函数分析查询的典型程度,并利用近似算法从查询历史中找出典型查询.对于所有的典型查询,从中选出少数代表性查询,根据其他典型查询与代表性查询之间的语义相关度,为每个代表性查询构建相应的查询序列;当一个新的查询到来时,评估其与代表性查询之间的语义相关度,然后利用阈值算法(threshold algorithm,TA)在预先创建的查询序列上快速选出top-k个与给定查询语义相关的多样性候选查询.实验结果和分析表明:提出的关键字之间耦合关系计算和查询之间的语义相关度评估方法具有较高准确性,top-k多样性选取方法具有较好效果和较高执行效率.

基于滑动窗口的Top-K概率频繁项查询算法研究

频繁项查询在网络监控、网络入侵检测、关联规则挖掘等方面是一项非常重要的技术.该技术在静态的不确定数据中已经得到了深入的研究.但随着数据流特征和不确定性表现的日益明显,在不确定数据流环境下的查询已经成为一项新的研究课题.因此基于数据流普遍采用的滑动窗口模型,提出了一种高效的概率Top-K频繁项查询算法sTopK-UFI.该算法避免了每次窗口更新都重新计算查询答案,而是利用现有的计算结果进行增量更新,从而减少查询代价.另外,该算法基于窗口中的现有数据对未来可能成为频繁项的元素进行预测,并利用泊松分布计算元素成为频繁项的概率上下界,提出相应的过滤策略,可以显著减少检测数据的数量,提高查询效率.实验结果表明,所提出算法可以有效地减少候选集、降低搜索空间、改善在不确定数据流上的查询性能.

基于Top-k映射的本体匹配方法

针对本体之间的异构问题,提出一种基于Top-k映射的本体匹配方法。该方法是对现有匹配方法的一种扩展,它以相似度计算为基础,从元素级和结构级计算2个概念之间的相似度,并在匹配过程中同时产生k个映射而不是一个最佳映射。实验结果表明,该算法在查全率和查准率方面都有很好的表现,并且其查准率要优于GLUE方法。