分布式网络中连续时间周期的全局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的算法性能更优,能更高效地挖掘用户感兴趣的模式。

PeakSketch:检测网络流中的top-k流的无偏和通用草图

通过对现有Sketch结构的研究,提出一种新的Sketch结构:PeakSketch,本文将其应用于三种任务:检测top-k频繁流,检测top-k重变化流,检测top-k持久流,从理论上证明了PeakSketch可以提供无偏估计,并且给出了算法的误差界。实验结果表明,PeakSketch的各项性能优秀,在检测top-k频繁流任务中,PeakSketch的吞吐量显著提升,特别是在分配内存小于200 kB以下时,吞吐量最高提升可以达到50%,准确率最高提升一倍,PeakSketch也展现突出的性能。

大图中多样化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查询方案

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

一种针对反向空间偏好top-k查询的高效处理方法

随着地理位置定位技术的蓬勃发展,基于在线位置服务技术的应用也越来越多.提出一种查询类型——反向空间偏好top-k查询.类似于传统的反向空间top-k查询,对于给定的空间查询对象,该查询返回使该对象满足top-k属性得分的那些用户.但不同的是,该对象的属性不是自身具有的特性,而是通过计算该对象与其他偏好对象之间的空间关系(如距离)而确定.这种查询在市场分析等许多重要领域具有需求,例如,根据查询结果,分析出某个地区中某个设施受欢迎的程度.但是,由于大量空间对象的存在导致对象之间空间关系的计算代价非常高,如何实时地计算出对象的空间属性得分,给查询处理带来很大的挑战.针对该问题提出优化的查询处理算法包括:数据集剪枝、数据集批量处理、基于权重的用户分组等策略.通过理论分析和充分的实验验证,证明了所提出方法的有效性.与普通方法相比,这些方法能够大幅度提高查询处理的执行时间和I/O效率.

云环境下加密图上top-k最近模糊关键词查询

随着云计算的快速发展,将图数据外包给云成为趋势。为保护数据隐私,用户需在外包前对其加密,并保留查询和处理数据的能力。考虑到用户容易出现拼写错误,文章基于标记图提出top-k最近模糊关键词查询的图加密方案,方案基于2-Hop标签构造加密索引结构计算最短距离,使用基于通配符的方法为关键词生成模糊集,构造模糊关键词索引实现模糊关键词查询,最终返回距给定节点最近的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对比序列模式挖掘算法k DSP-Miner(top-k distinguishing sequential patterns with gap constraint miner).k DSP-Miner中用户只需设置期望发现的对比最显著的模式个数,从而避免了直接设置对比支持度阈值.相应地,挖掘算法更容易使用,并且结果更易于解释.同时,为了提高算法执行效率,设计了若干剪枝策略和启发策略.进一步设计了k DSP-Miner的多线程版本,以提高其对高维序列元素情况的处理能力.通过在真实世界数据集上的详实实验,验证了算法的有效性和执行效率.

差分隐私保护下一种精确挖掘top-k频繁模式方法

频繁模式挖掘是分析事务数据集常用技术.然而,当事务数据集含有敏感数据时(如用户行为记录、电子病例等),直接发布频繁模式及其支持度计数会给个人隐私带来相当大的风险.对此提出了一种满足ε-差分隐私的top-k频繁模式挖掘算法DP-topkP(differentially private top-kpattern mining).该算法利用指数机制从候选频繁模式集合中挑选出top-k个携带真实支持度计数的模式;采用拉普拉斯机制产生的噪音扰动所选模式的真实支持度计数;为了增强输出模式的可用性,采用后置处理技术对top-k个模式的噪音支持度计数进行求精处理.从理论角度证明了该算法满足ε-差分隐私,并符合(λ,δ)-useful要求.实验结果证明了DP-topkP算法具有较好的准确性、可用性和可扩展性.

微博网络地域Top-k突发事件检测

传统的事件检测不考虑地域特性,面对的是媒体的整个信息流,是一种广域事件检测,会引起局部地域事件检测的失效.随着Web2.0及GPS技术的推广应用,很多社交媒体生成的内容体现了地理信息和时间标记.社交媒体中地域性突发事件的检测是近期新兴的研究热点.针对地域突发事件检测的需求,在合理利用社交媒体及突发事件表现的特性等方面,已有的研究仍有较大的不足.微博网络作为实时性、交互性很强的社交媒体,已经成为人们爆料事件、发表观点的首选媒体.该文面向微博网络,给出了地域Top-k突发事件检测的系统框架,包含地域博文采集、博文预处理、词突发值计算、突发词聚类、突发事件排序及突发事件可视化等部分.根据微博的时空特点,在综合考虑微博博文及社交关系的基础上,利用词出现频率、词关联用户、词分布地域及词社交行为4类指标,提出了新颖的微博网络词突发值计算模型.结合微博网络的特点以及地域Top-k突发事件检测的需求,提出了融合突发词地域、频率、关联博文、关联博文产生的影响力以及关联用户5类指标的突发事件热度计算方法.选取新浪微博作为真实的检测环境,以北京、南京、连云港和日照4个城市为地域范围,使用了5种方法比对了突发事件检测的准确率,这5种方法分别为HBED(2011年)、GeoSED(2013年)、EvenTweet(2013年)、GeoBurst(2016年)和该文提出的方法 LocTBED.结果表明,文中所提方法在地域Top-k突发事件的检测上有较好的性能.

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查询从海量数据中返回最符合用户需求的前K个结果,主要目的是消除信息过载带来的负面影响.大数据背景下的Top-K查询,给数据管理和分析等方面带来新的挑战.结合MapReduce的特点,从数据划分、数据筛选等方面对云环境下的大数据Top-K查询问题进行深入研究.实验结果表明,该方法具有良好的性能和扩展性.

基于上下文偏好的Web数据库查询结果Top-K排序方法

为了解决Web数据库多查询结果的问题,该文提出了一种基于上下文偏好的查询结果top-k排序方法,首先提出了一种带偏好程度的上下文偏好模型:i_1>i_2,d|X,表示在上下文条件X下,项i_1与i_2相比,用户偏好项i_1的程度为d(0.5≤d≤1),带偏好程度的上下文偏好通过在查询历史中使用关联规则挖掘获得.基于上下文偏好,提出了一种查询结果top-k排序方法,给出了相应的元组排列创建、聚类和top-k排序算法.实验结果表明,提出的上下文偏好模型具有较强的偏好表达能力,top-k排序方法能够较好地满足用户需求和偏好并且具有较高的执行效率.