图数据库中的相似性搜索算法研究与应用*

图数据库的相似性搜索是一个非常重要的研究内容,图的相似性匹配属于图同构的判定问题,是NP完全问题,传统的高开销搜索的方法已经不能满足复杂图查询的需要;另外,由于图数据库的复杂性和特殊性,已有的优化算法不能直接使用。为了提高图数据库的搜索效率,提出了一种基于索引的相似性搜索算法,通过数据库中的频繁结构建立特征索引,算法可高效准确地滤除大量的非相似图集合,避免了图之间精确匹配即图同构的计算,最后将本算法应用于化学数据库,实验结果证明了该方法的有效性和可行性。     

基于敏感数据加密的分布式安全数据库服务研究*

针对目前基于数据加密技术的安全数据库服务不能有效平衡数据处理性能与数据隐私保护的不足,提出一种新的基于分布式安全数据库服务的隐私保护方法,通过引入准标志属性集的自动检测技术,采用对部分敏感属性加密和分解准标志属性集的方式实现数据的垂直分解,通过基于元数据的查询分解实现分布式查询处理。实验结果表明,该方法能较好地平衡查询性能与隐私保护之间的矛盾。     

GPU近实时线性双目立体代价聚合

目的 近年来双目视觉领域的研究重点逐步转而关注其“实时化”策略的研究,而立体代价聚合是双目视觉中最为复杂且最为耗时的步骤,为此,提出一种基于GPU通用计算(GPGPU)技术的近实时双目立体代价聚合算法。方法 选用一种匹配精度接近于全局匹配算法的局部算法——线性立体匹配算法(linear stereo matching)作为代价聚合策略;结合线性代价聚合的原理,对其主要步骤(代价计算、均值滤波及系数求解等)的计算流程进行有针对性地并行优化。结果 对于相同的实验样本,用本文方法在NVIDA GTX780 实验平台上能在更短的时间计算出代价矩阵,与原有的CPU实现方法相比,代价聚合的效率平均有了数十倍的提升。结论 实时双目立体代价聚合方法,为在个人通用PC平台上实时获取高质量双目视觉深度信息提供了一个高效可靠的途径。     

基于PMI-IR的联想词表构造方法研究

通过对大规模查询日志进行挖掘分析进而提高检索的准确率一直是信息检索领域的热点问题。文章提出一种基于PMI-IR（逐点互信息方法）的联想词表构造方法。该方法利用序列模式挖掘算法扫描大规模用户查询日志,获取共现频次超过某一阈值的词组合,进行聚类获取候选同义词集,然后依次计算词wordA与每个候选词的相似度,选择相似度高于某一阈值的词作为词wordA的联想词集,最后形成联想词表。实验表明,借助该方法得到的联想词表进行扩展查询提高了检索的准确率。     

基于社交网络的图数据挖掘应用研究

社交网络数据的高度复杂性给数据挖掘研究带来了巨大的挑战,而社交网络数据挖掘更注重实体之间相互关联的特点,使得图数据挖掘技术的研究与应用逐渐成为该领域的热点。传统数据挖掘,如聚类、分类、频繁模式挖掘等技术逐渐拓展到图数据挖掘领域。文中首先介绍了现阶段图数据挖掘算法（其中包括图查询、图聚类、图分类和图的频繁子图挖掘）的研究内容和存在的问题;其次介绍了图形数据库研究现状,以及对比了主流图形数据库管理系统的优劣;最后介绍了图挖掘技术在社交网络中的应用。     

Towards evolvable Internet architecture-design constraints and models analysis

There is a general consensus about the success of Internet architecture in academia and industry. However, with the development of diversified application, the existing Internet architecture is facing more and more challenges in scalability, security, mobility and performance. A novel evolvable Internet architecture framework is proposed in this paper to meet the continuous changing application requirements. The basic idea of evolvability is relaxing the constraints that limit the development of the architecture while adhering to the core design principles of the Internet. Three important design constraints used to ensure the construction of the evolvable architecture, including the evolvability constraint, the economic adaptability constraint and the manageability constraint, are comprehensively described. We consider that the evolvable architecture can be developed from the network layer under these design constraints. What＇s more, we believe that the address system is the foundation of the Internet. Therefore, we propose a general address platform which provides a more open and efficient network environment for the research and development of the evolvable architecture.     

一种基于路网的多源聚合距离Skyline查询算法

基于路网距离的多源Skyline查询在地图服务中广泛使用,但现有的Skyline查询方法对于复杂的路网距离计算效率低下,并且随着查询点数量的增加查询结果集变得过于庞大,无法为用户提供精简有效的查询结果。为了提高查询结果的有效性和查询效率,提出一种基于最小聚合距离的倒排索引Skyline查询算法,该算法对道路网建立QG-tree索引,提高聚合距离的计算效率;同时对兴趣点集建立倒排索引,结合剪枝策略对兴趣点进行检索,减少聚合距离计算和支配判定的开销,有效地提高查询效率。在真实道路网上的实验表明,所提出的算法效率比现有算法DSR和N3S快1~3个数量级,可以有效地处理道路网环境下多源Skyline查询问题。     

大图上跳数受限的可达查询算法研究与优化

判断有向图上两个顶点之间是否存在一条路径是一个经典问题,而对于一些路由规划和图分析等实际应用,要求查找是否存在跳数受限的可达路径,这是一个变种的图可达查询问题.对于大图上跳数受限的查询算法,不仅仅要对大图查询的时间效率和空间效率进行权衡,而且还要利用跳数受限的特性进行优化.普通的可达查询算法存在小度数顶点索引项占用空间过多的问题,造成空间浪费严重.为此我们提出了一种面向跳数受限的2-hop部分索引方法,采用改进的索引方法并结合局部搜索,实现跳数受限的有效可达性查询.实验结果表明,在Orkut社交网络数据集上与已有算法相比,该算法索引空间节省了32％,同时查询时间略微增加,使得我们算法可以计算更大规模图的跳数受限可达问题.     

时序图节点嵌入策略的研究

相较于传统的图数据分析方法,图嵌入算法是一种面向图节点的新型图数据分析策略.其旨在通过将图节点向量化表达,进而在节点向量基础上利用神经网络相关技术更有效的进行图数据分析或挖掘工作,如在节点分类、链接预测及交通流预测等经典问题上取得效果显著.虽然研究者们在图嵌入方面已取得了诸多成果,但是面向时序图的节点嵌入问题却未被充分重视,本文便是在先前研究工作的基础上,结合信息在时序图中的传播特性,提出了一种对时序图节点进行自适应嵌入表达的方法ATGEB （Adaptive Temporal Graph Embedding）.首先,为了解决不同类型时序图节点活跃程度不同的问题,通过设计一种自适应方式对其活跃时刻进行聚类.而后,在此基础上设计一种游走模型用以保存节点对之间的时间关系,并将节点游走序列保存在一种双向多叉树上进而可以更快速的得到节点时间相关的游走序列.最后,在基于节点游走特性和图拓扑结构的基础上,对节点向量进行重要节点采样,以便在尽可能短的时间内训练出满足需求的网络模型.通过充分的实验证明,本文面向时序图的嵌入策略相较于现流行的嵌入方法,在时序图时序中节点间时序可达性检测以及节点分类等问题上得出了更好的实验效果.     

GPU数据库核心技术综述

GPU以其超高速计算能力和超大数据处理带宽受到数据库厂商及研究人员的青睐,以GPU计算为核心的数据库分支（GDBMS）蓬勃发展,以其吞吐量大、响应时间短、成本低廉、易于扩展的特点,与人工智能、时空数据分析、数据可视化、商务智能交互融合能力,彻底改变了数据分析领域的格局.本文将对GDBMS的四大核心组件：查询编译器、查询处理器、查询优化器和存储管理器进行综述,希望促进未来的GDBMS研究和商业应用.