Top-k相似连接算法性能优化

相似连接算法在数据清理、数据集成和重复网页检测等领域有着广泛的应用.现有相似连接算法有两种类型：基于相似度阈值的相似连接和Top-k相似连接.Top-k连接算法非常适合于相似度阈值未知的应用场景,目前最为有效的Top-k相似连接算法是Xiao等人提出的Topk-join.为了解决Topk-join中存在的性能问题,提出了一种Top-k相似连接算法Opt-join,该算法将Token批处理技术集成在现有的事件驱动框架中,以降低前缀事件的处理代价;通过置换哈希查找与过滤操作的执行位置来降低哈希查找代价,并理论证明了该置换的正确性.实验结果表明：与Topk-join算法相比,Opt-join取得了1.28倍~3.09倍的性能提升.实验数据还显示：随着数据长度的增加或k值的增长,Opt-join的性能优势有不断增加的趋势.     

基于社会选择理论的在线服务评价

用户评价标准不一致和偏好不一致导致网络空间中的在线服务之间不具备公正的可比较性,从而用户难以选择到满意的在线服务,因此,提出了基于社会选择理论计算在线服务优劣的排序方法。首先,根据用户给出的用户-服务评价矩阵构建群体偏好矩阵;然后,基于群体偏好矩阵和Kemeny社会选择函数构建0-1整数规划模型;最后,通过求解该模型可得到服务的最优排序结果。该方法聚合个体偏好为群体偏好,决策符合群体大多数人的偏好且与个体偏好保持最大的一致性。通过理论分析和实验验证了该方法的合理性和有效性。实验结果表明,该方法能有效地解决在线服务之间的不可比较性问题,实现在线服务的优劣排序,并可以有效抵制推荐攻击,具有较强的抗操纵性。     

概率数据上基于EMD距离的并行Top-k相似性连接算法

以无线传感器网络为代表的新型数据应用和以图像处理为基础的传统数据应用都产生了大规模的概率数据.在概率数据的管理中,Top-k相似性连接操作返回最相似的k 对概率数据,具有重要应用价值.直方图是最常用的概率数据模型之一,而EMD（Earth Mover’s Distance）距离因其较强的鲁棒性可更准确地量化直方图概率数据之间的相似性.然而EMD距离的计算却具有三次方的时间复杂度,给基于EMD距离的Top-k 相似性连接带来巨大挑战.基于流行的MapReduce并行处理框架,利用EMD距离对偶线性规划问题的优良特性,提出了两种大规模概率数据上基于EMD距离的Top-k相似性连接算法.首先提出基于块嵌套循环连接思想的基本解决方法,命名为Top-k BNLJ算法.进而改进数据划分策略,提出基于数据局部性进行数据划分的Top-k DLPJ 算法,有效降低了MapReduce作业执行过程中的数据传输量.使用大规模真实数据集对两种算法进行评估,证实了本文提出的Top-k DLPJ算法的高效性和处理大规模数据集时的良好扩展性.     

一种云环境下的大数据Top-K查询方法

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

利用属性条件偏好推理的在线服务群体选择

在线服务群体选择能够在多人社交活动中提供适合群体的活动方案.在线服务群体选择中，如不考虑用户的服务属性偏好，则难以对未体验服务的偏好进行推理，导致对未体验服务的预测偏好与用户真实偏好存在差异，使得聚合个体用户偏好得到的群体选择结果难以真实反映群体对服务的偏好.为此，提出一种利用属性条件偏好推理的在线服务群体选择方法.首先根据用户对服务属性的偏好建立条件偏好表和属性之间的依赖关系；然后根据条件偏好网络(Condition Preference networks, CP-nets)的性质推理偏好导出图，偏好导出图的拓扑排序对应用户对服务属性值组合的偏好关系，得到个体用户的服务选择结果；最后使用社会选择函数Ranked Pairs对个体用户的服务选择结果进行聚合，得到群体的服务选择结果.通过实验验证了该方法的合理性和有效性.实验结果表明方法得到的群体结果与个体用户选择结果的平均nDCG(Normalized Discounted Cumulative Gain)比对比方法分别高11.4%、2.2%和11.1%,方法还满足多数准则、孔多赛性、抗操纵性等性质.     

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

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

一种QoS感知的Web服务群体评价方法

传统QoS感知的Web服务选择方法需要用户给出精确权重以表达其对QoS属性的偏好。为解决用户无明确偏好情况下的服务选择问题,提出了一种QoS感知的Web服务群体评价方法。对Web服务群体评价的需求进行了详细的分析,以有明确QoS偏好的用户对服务的历史选择结果为基础,利用群决策的Condorcet和Borda函数集结这些结果得到服务的群体评价,从而使得无明确QoS偏好用户可以参考该评价结果进行服务选择。理论分析和仿真实验验证了该服务群体评价方法的合理性和有效性。     

面向不一致用户评价准则的在线服务推荐

客观上,用户的评价准则是由主观意识决定的,用户之间的评价准则不同导致多个用户对同一服务的评分不具备可比较性,不考虑不同用户评分的不可比较性所获得的服务推荐将难以满足用户个性偏好及其真实需求。为此,提出一种面向不一致用户评价准则的在线服务推荐方法,考虑用户偏好不一致时用户对在线服务的偏好关系,以偏好关系计算用户之间的相似度,并以此获得在线服务推荐结果。首先以用户-服务评分矩阵为基础建立用户对服务的偏好关系,其次根据偏好关系计算用户之间的相似度,然后以用户相似度为基础对用户未评分的服务进行评分预测,最后以预测评分的排序结果作为推荐结果。与经典的协同过滤推荐方法的比较实验,验证了本方法的有效性。实验表明,本方法获得的推荐结果能满足大多数用户的服务偏好,同时获得了比经典的协同过滤推荐方法更好的准确率。     

带间隔约束的Top-k对比序列模式挖掘

对比序列模式能够表达序列数据集合间的差异,在商品推荐、用户行为分析和电力供应预测等领域有广泛的应用.已有的对比序列模式挖掘算法需要用户设定正例支持度阈值和负例支持度阈值.在不具备足够先验知识的情况下,用户难以设定恰当的支持度阈值,从而可能错失一些对比显著的模式.为此,提出了带间隔约束的top-k对比序列模式挖掘算法kDSP-Miner(top-k distinguishing sequential patterns with gap constraint miner).kDSP-Miner中用户只需设置期望发现的对比最显著的模式个数,从而避免了直接设置对比支持度阈值.相应地,挖掘算法更容易使用,并且结果更易于解释.同时,为了提高算法执行效率,设计了若干剪枝策略和启发策略.进一步设计了kDSP-Miner的多线程版本,以提高其对高维序列元素情况的处理能力.通过在真实世界数据集上的详实实验,验证了算法的有效性和执行效率.     

k-Median近似计算复杂度与局部搜索近似算法分析

k-Median问题的近似算法研究一直是计算机科学工作者关注的焦点,现有研究结果大多是关于欧式空间和Metric空间的,一般距离空间k-Median的结果多年来一直未见.考虑一般距离空间k-Median问题,设d_max/d_min表示k-Median实例中与客户点邻接的最长边长比最短边长的最大者.首先证明d_max/d_min≤ω+ε的k-Median问题不存在近似度小于1+ω-1/e的多项式时间近似算法,除非,由此推出Metric k-Median问题不可近似到1+2/e,除非NP(∈)DTME(N^{O(log logn)}).然后给出k-Median问题的一个局部搜索算法,分析表明,若有d_max/d_min≤ω,则算法的近似度为1+ω-1/2.该结果亦适用于Metric k-Median,ω≤5时,局部搜索算法求解Metric k-Median的近似度为3,好于现有结果3+2/P.通过计算机实验,进一步研究了k-Median局部搜索求解算法的实际计算效果和该算法的改进方法.     

基于Slater社会选择理论的在线服务评价方法

不同用户对于同一在线服务会有不一致的评价标准和偏好,导致其对服务的评分不具备可比性,使用户难以准确选择适合的在线服务。针对该问题,引入Slater社会选择理论提出一种新的在线服务评价方法。对稀疏的评分矩阵进行填充,通过用户对服务评分的相互比较结果,构建以服务为节点、以优先关系为有向边的有向图,并根据其中相似集、前集、后集之间以及内部节点有向边的指向关系,判断所有节点的指向关系及排序,形成服务评价结果。实验结果表明,该方法较Sum法、Average法和Copeland法抗操控性更强,可避免少数用户操控评价结果,并且其符合孔多塞准则,能够体现多数用户的偏好需求。     

Reducing network traffic in unstructured P2P systems using Top-k queries

A major problem of unstructured P2P systems is their heavy network traffic. This is caused mainly by high numbers of query answers, many of which are irrelevant for users. One solution to this problem is to use Top-k queries whereby the user can specify a limited number (k) of the most relevant answers. In this paper, we present FD, a (Fully Distributed) framework for executing Top-k queries in unstructured P2P systems, with the objective of reducing network traffic. FD consists of a family of algorithms that are simple but effective. FD is completely distributed, does not depend on the existence of certain peers, and addresses the volatility of peers during query execution. We validated FD through implementation over a 64-node cluster and simulation using the BRITE topology generator and SimJava. Our performance evaluation shows that FD can achieve major performance gains in terms of communication and response time. Recommended by: Sunil Prabhakar Work partially funded by the ARA Massive Data of the Agence Nationale de la Recherche.     

时序范围最具稳定性服务集推荐算法

服务的批量推荐在服务计算领域具有巨大的应用前景。然而,针对动态变化的大规模在线用户,如何实现时序范围内最具稳定性服务集合批量推荐,仍然是一个极具挑战的技术问题。提出一种新的服务集推荐算法,它采用回溯法挑选出满足潜在用户需求的服务集,并着重考虑用户在线状态的实时变化,通过服务集与用户集的动态竞争优化,最终挖掘出时序范围内稳定满足最多用户需求的服务集。为验证提出算法的合理性和有效性,利用WS-DREAM的真实数据集,进行了一系列实验。实验结果表明,提出的算法能够有效发现系统中时序范围最稳定满足用户需求的服务集合,从而达到利益最大化。     

基于快速连续蚁群算法的QoS切换决策机制

随着人们对移动网络服务需求的日益增长,用户需要在复杂的异构网络中实现不同接入技术之间的无缝切换,因此选择总最佳连接并提供服务质量保证的切换决策成为下一代互联网研究的关键内容.为了更好地满足用户的需求,在综合考虑网络信息的不确定性、用户服务质量需求、用户偏好、用户愿意支付的费用以及网络供应商的收益等因素的前提下,设计了基于快速连续蚁群算法的切换决策机制,并引入协商博弈和Nash均衡思想来解决用户之间的串谋问题以保证切换决策的公平性.仿真结果表明,设计的切换决策机制在满足用户服务质量需求的同时,不仅使双方的效用最大,并且最契合用户的偏好,能够很好地解决下一代互联网中支持总最佳连接的切换决策问题.     

Exploiting behavioral user models for point of interest recommendation in smart museums

ABSTRACT

The Internet of Things (IoT) holds the promise to blend real-world and online behaviors in principled ways, yet we are only beginning to understand how to effectively exploit insights from the online realm into effective applications in smart environments. Such smart environments aim to provide an improved, personalized experience based on the trail of user interactions with smart devices, but how does recommendation in smart environments differ from the usual online recommender systems? And can we exploit similarities to truly blend behavior in both realms to address the fundamental cold-start problem? In this article, we experiment with behavioral user models based on interactions with smart devices in a museum, and investigate the personalized recommendation of what to see after visiting an initial set of Point of Interests (POIs), a key problem in personalizing museum visits or tour guides, and focus on a critical one-shot POI recommendation task—where to go next? We have logged users' onsite physical information interactions during visits in an IoT-augmented museum exhibition at scale. Furthermore, we have collected an even larger set of search logs of the online museum collection. Users in both sets are unconnected, for privacy reasons we do not have shared IDs. We study the similarities between users' online digital and onsite physical information interaction behaviors, and build new behavioral user models based on the information interaction behaviors in (i) the physical exhibition space, (ii) the online collection, or (iii) both. Specifically, we propose a deep neural multilayer perceptron (MLP) based on explicitly given users' contextual information, and set-based extracted features using users' physical information interaction behaviors and similar users' digital information interaction behaviors. Our experimental results indicate that the proposed behavioral user modeling approach, using both physical and online user information interaction behaviors, improves the onsite POI recommendation baselines' performances on all evaluation metrics. Our proposed MLP approach achieves 83% precision at rank 1 on the critical one-shot POI recommendation problem, realizing the high accuracy needed for fruitful deployment in practical situations. Furthermore, the MLP model is less sensitive to amount of real-world interactions in terms of the seen POIs set-size, by backing of to the online data, hence helps address the cold start problem in recommendation. Our general conclusion is that it is possible to fruitfully combine information interactions in the online and physical world for effective recommendation in smart environments.     

一种空间上下文感知的提及目标推荐方法

作为一种新兴的社交媒体用户交互服务,提及机制(mention mechanism)正在用户在线交互和网络信息传播方面扮演着重要角色.对用户提及行为的研究能够揭示用户的隐式偏好与其显式行为之间的联系,为信息传播监控、商业智能、个性化推荐等应用提供新的数据支撑.当前,对用户提及机制的探索多集中在其信息传播属性上,缺少从普通用户角度对其用户交互属性的学习.通过对普通用户提及行为的分析和建模构建一个推荐系统,为给定的社交媒体消息生成目标用户推荐.通过对大型真实社交媒体数据集的分析发现,用户的提及行为受其提及活动的语义和空间上下文因素的联合影响.据此,提出一个联合概率生成模型JUMBM(joint user mention behavior model),模拟用户空间关联提及活动的生成过程.通过对用户语义和空间上下文感知的提及行为进行统一建模,JUMBM能够同时发掘用户的移动模式、地理区域依赖的语义兴趣及其对应目标用户的地理聚集模式.此外,提出一种混合剪枝算法,加快推荐系统对在线top-k查询的响应速度.在大型真实数据集上的实验结果表明,所提方法在推荐有效性和推荐效率方面均优于对比方法.