RIAIL:大规模图上的可达性查询索引方法

图被广泛用来建模在社交网络、语义网、计算生物学和软件分析中的应用.可达性查询是图数据上的一种基础查询.当前,针对图上的可达性查询已经提出了一些索引算法,但是它们不能灵活地扩展到大的图数据.因此,提出了一种索引方法RIAIL(reachability index augmented by interval labeling).RIAIL将结点的标记信息表示成四元组.前两个元素是区间标记,编码生成树的可达性信息,后两个元素编码非树边的可达性信息.RIAIL查询时只需索引且索引创建代价小.最后,通过大量真实和人工生成数据集上的实验说明,RIAIL能够高效地处理可达性查询,并且可以简单地扩展到大的图数据.     

到达数据中时空异常聚簇发现

在时空数据中有一类表示用户在某一时间到达某一地点的数据——到达数据,到达数据可以是社交网站的签到数据、轨迹数据中的停留点及公共交通中乘客抵达的位置数据,这些数据的聚簇可以反映用户的聚集行为.基于到达数据,提出一类新的时空数据查询——时空异常聚簇发现.将到达数据进行周期性划分,通过时空聚类算法对一个时间段的数据进行聚类,比较不同时间段内聚簇的差异度,发现具有最大簇异常度的前k个簇.通过该查询发现的时空异常聚簇可以应用于城市安全管理、基于位置的服务和交通调度等方面.定义了异常簇查询模型,提出了针对任意形状聚簇的簇差异度度量,将异常簇查询转化为二分图最大匹配问题,对二分图构建与匹配进行了优化并提出了高效的查询算法.利用真实数据集进行了充分实验,验证了查询结果的实际意义,评估了所提出的各查询算法在不同参数设置下的查询效率.     

一种基于DAG动态重构的认知网络服务迁移方法

针对认知网络高度动态性带来的服务随机失效问题,提出了一种服务迁移方法以保障认知网络的 QoS.首先,采用先迁移、后优化的思想,重新生成关联服务有向无环图(directed acyclic graph,简称DAG),并在此基础上提出 DAG 动态重构算法,将关联服务转化为层次化 DAG 服务;其次,计算关键服务迁移路径,并给出可迁移服务死锁避免理论分析,将迁移服务提前迁移到当前网络空闲资源运行,以缩短服务的执行时间.仿真实验测试了3种故障注入类型下网络服务迁移方案的服务性能.实验结果显示,该方法在弹性网络负载与未知故障情况下具有较好的 QoS保障效果.     

超像素分割算法研究综述

超像素能够捕获图像冗余信息, 降低后续处理任务复杂度, 已受到了国内外研究者的日益关注。首先分析了超像素分割领域的发展现状, 以基于图论的方法和基于梯度下降的方法为视角, 对现有超像素分割方法进行归纳和论述。在此基础上, 就目前常用的超像素分割算法进行了实验对比, 分析各自的优势和不足。最后, 对超像素分割技术的最新应用进行了介绍和展望。     

面向个性化云服务的动态信任模型

为更好地实践云计算为用户提供廉价按需服务的宗旨,满足服务请求者的个性化需求,提出一种面向个性化云服务的动态信任模型。基于细粒度服务思想定义个性化云服务,通过引入时间衰减因子和建立高效激励机制修正直接信任值,以灰色系统理论为基础计算实体间的评价相似度,并将评价相似度和推荐者的推荐可信度作为合成推荐信任值的重要因素,同时提出一种基于评价相似度的自信因子赋值方法,以提高合成综合信任值的准确性。实验结果表明,与GM-Trust模型及CCIDTM模型相比,该模型的交互成功率分别平均提高了4%和11%。     

图引擎底层存储的设计与实现

随着社交网络和语义Web等数据应用的兴起,催生了许多图数据处理产品,包括Neo4j,Hyper Graph DB等,然而这些产品在设计时并未充分考虑图应用对数据可用性和可扩展性的更高要求。为此,提出一种基于分布式内存云的图引擎底层建模和存储解决方案。在内存云上搭建分布式键值引擎,进而在键值存储的基础上对图的数据进行建模和读写。在大规模数据集上的实验结果表明,该方案具有较好的图随机访问性能,并能够高效地支持海量规模的图数据应用。     

无线传感器网络中的改进数据聚集调度算法

针对现有聚集数据调度近似算法具有较高延时上界的问题,提出一种改进的聚集数据调度近似算法。建立一棵根在中心结点的广度优先搜索树,分层构造一个最大独立集(MIS),使MIS中相邻的2个结点相距两跳。将MIS中的结点连接起来,形成一棵根在中心结点的数据聚集调度树,使结点按数据聚集调度树进行分层数据调度。在数据聚集调度树的构造过程中,对于任意支配点,以最小的结点连接其相距两跳的支配点。对于2个相邻支配点的公共邻居支配点,通过在距中心点最近的支配点加入数据聚集树,使其在数据调度过程中将数据发送给距中心点最近的支配点,从而降低数据的聚集延时。实验结果表明,与SAS算法、Guo’s算法和IAS算法相比,该算法的数据聚集延时更低,其延时上界为14R+△?10。     

基于日志挖掘的移动应用用户访问模型建模技术研究

提出了一种基于监控日志挖掘的移动应用用户访问模型自动构造方法,该方法包括监控代码注入和界面访问模型构造两部分。首先,提出了一种监控代码自动注入方法,即通过对移动应用代码的静态分析,自动地在相应位置插入监控代码以支持在运行时动态地监控用户的访问行为。其次,提出了一种基于状态机的移动应用用户访问模型构造方法。访问模型中状态机的节点和节点间跳转上的附加属性描述了UI界面之间的跳转行为和界面内控件的使用情况。对移动应用进行的实验表明,这种基于监控日志挖掘的移动应用用户访问模型自动构造方法能够成功地自动注入移动应用的监控代码,并能够有效获得移动应用用户界面访问行为。     

一阶谓词逻辑的图形推理法

针对已有一阶谓词逻辑推理方法中存在的推理效率低等问题,研究一种基于谓词/变迁系统的图形推理法。定义了描述谓词间与/或关系的谓词-与/或图,借助谓词-与/或图表示谓词/变迁系统,提出一种实现反向推理的目标制导的图形推理法。该方法推理效率高,较已有的推理方法具有一定的优越性。     

链图的概念格表示

概念格是基于对象集和属性集之间的二元关系建立的一种层次结构。它与极大二部团存在着一定的联系。将概念格属性约简理论应用于链图,首先给出了链图的概念格表示,其次证明了二部图G=(V1,V2,E)是链图,当且仅当G′=(V1,V2,E)是链图,这里(V1,V2,E)是(V1,V2,E)的约简形式背景。