分布式网络中连续时间周期的全局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属性得分的那些用户.但不同的是,该对象的属性不是自身具有的特性,而是通过计算该对象与其他偏好对象之间的空间关系(如距离)而确定.这种查询在市场分析等许多重要领域具有需求,例如,根据查询结果,分析出某个地区中某个设施受欢迎的程度.但是,由于大量空间对象的存在导致对象之间空间关系的计算代价非常高,如何实时地计算出对象的空间属性得分,给查询处理带来很大的挑战.针对该问题提出优化的查询处理算法包括:数据集剪枝、数据集批量处理、基于权重的用户分组等策略.通过理论分析和充分的实验验证,证明了所提出方法的有效性.与普通方法相比,这些方法能够大幅度提高查询处理的执行时间和I/O效率.

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

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

不确定性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排序方法能够较好地满足用户需求和偏好并且具有较高的执行效率.

XML数据流上Top-K关键字查询处理

利用关键字可以在模式未知的情况下对XML数据进行查询.在当前的XML数据流上的关键字查询处理中,打分函数往往不能都满足各种用户不同的需求.提出了一种基于skyline的XML数据流上的Top-K关键字查询.对于这种查询,不需要考虑影响结果与查询相关性的复杂因素,只需利用skyline挑选与查询最相关的结果.提出了两种XML数据流上的有效的基于skyline的Top-K关键查询处理算法,包括对单查询和多查询的处理算法.通过扩展实验对两种算法的有效性和可扩展性进行了验证.经过实验验证,所提出的查询处理算法的效率几乎不受关键字个数、查询结果数量、查询数量等参数的影响,运行时间和文档大小大致呈线性关系.

基于内容过滤PageRank的Top-k学习资源匹配推荐

针对在线教育支持技术中关于文本处理的多义词和同义词问题,提出基于内容过滤PageRank语义相似替换的Top-k学习资源推荐算法。基于内容的向量空间滤波建立学习资源过滤推荐模型,该模型采用资源间匹配方式以取代语义相似性,从而避免多义词或同义词的漏检问题。基于谷歌PageRank算法结合前述资源间匹配模型构建考虑资源间关系连接的权重矩阵,取代传统PageRank算法网页间的超链接方式,进行资源类型划分,得到特征的马尔可夫收敛矩阵,并利用Top-k算法实现推荐结果细化。实验结果表明,在公共学习资源数据集中,所提算法对计算时间的覆盖率是可行的。

基于MapReduce的top-k高效用模式挖掘算法

高效用模式挖掘被广泛地应用于数据挖掘领域。为了挖掘指定数量的高效用模式,一些基于树结构和效用表结构的top-k高效用挖掘算法被提出,但前者在挖掘过程中产生了大量候选模式,后者在效用模式增长时需要进行多次比较;同时,由于在信息社会,数据量呈爆炸性增长,所以在数据集过大的情况下,挖掘高效用模式需以大量存储空间以及计算开销为代价。为了解决这两个问题,基于MapReduce的top-k高效用模式挖掘算法(TKHUP_MaR)被提出。该算法通过两次扫描数据库,利用三次MapReduce来实现并行top-k高效用模式的挖掘。通过实验表明TKHUP_MaR算法在并行挖掘top-k高效用模式的过程中是有效的。

两层传感器网络中可验证隐私保护Top-k查询协议

无线传感器网络中隐私保护技术已经成为研究热点,其中隐私保护精确Top-k查询协议已成为富有挑战性的研究问题.文中提出了一种两层传感器网络中可验证隐私保护Top-k查询协议SafeTQ(Safe Top-k Query),SafeTQ由隐私保护Top-k查询协议和两种完整性验证模式组成.SafeTQ使用加随机数扰乱、加密和高资源节点之间安全计算第k位数据值等策略,能够在不泄漏隐私信息的情况下,精确地完成传感器网络Top-k查询.SafeTQ中两种完整性验证模式分别使用邻居数据项形成加密链和空间邻居节点概率发送验证消息策略,使Sink能够检测和拒绝不正确或不完整查询响应.文中通过理论分析和使用真实数据集实验验证了SafeTQ的安全性和有效性.

海量高维向量的并行Top-k连接查询

在很多应用领域中,向量的Top-k连接查询是一种很重要的操作,给定两个向量集合R和S,Top-k连接查询要求从R和S中返回距离最小的前k个向量对.由于数据的海量性和高维特性,传统的集中式算法已经无法在可接受的时间内完成连接查询任务.MapReduce作为一个并行处理框架,能够有效地处理大规模数据.由于其高可扩展性、高可用性等特点,MapReduce已经成为海量数据处理的首选实现方案,在很多领域都得到了广泛的应用.文中基于分段累积近似法对高维向量进行降维,然后利用符号累积近似法对高维向量进行分组;在此基础上,结合MapReduce框架,提出了基于SAX的并行Top-k连接查询算法.实验表明,文中所提方案具有良好的性能和扩展性.

海量空间数据的并行Top-k连接查询

在许多空间应用领域中,Top-k空间连接查询是一种十分重要的操作,指定两个空间关系R和S,Top-k空间连接查询从R或S中返回k个与其他空间关系具有最大交叠数的结果.不同于Top-k查询,Top-k空间连接查询先执行空间连接操作,然后才执行Top-k查询.由于空间数据的海量特性和复杂性,传统的单机串行处理需要很长时间甚至不能完成.提出了一种新颖的基于MapReduce的Top-k空间连接查询处理算法TKSJMR.该算法在并行空间连接阶段执行部分聚集操作,减少数据写入和数据传输;在Top-k结果获取阶段提出一种Top-k结果获取算法,将结果聚集和Top-k结果获取缩减为一个阶段,减少MapReduce执行步骤.实验结果表明,该算法不仅在有效时间内解决单机上难以解决的海量空间数据的Top-k连接查询问题,并且TKSJMR在Top-k查询处理阶段性能提升了约50%.