一种新颖的对比子图索引算法

针对当前图索引算法存在的问题,提出一种基于对比子图索引框架,开发冗余感知机制,选择一个小型的具有明显区分力的索引特征集,改善索引性能。实验结果表明,该算法对不同的包容搜索载荷能达到近优化的修剪力,与传统图搜索方法相比,具有明显的索引性能优势。     

近似图包含搜索和索引技术的研究

在对图形数据库中的几种有代表性的传统相似性搜索及索引构造方法进行总结分析的基础上,探讨了近似图包含搜索区别于传统相似性搜索的特征,并且提出了一种针对近似图包含搜索的基于覆盖率和支持度对频繁子模式进行筛选的索引构造算法。实验结果验证了该方法的有效性。     

基于TF-IQF模型和图聚类的个性化搜索研究

针对信息检索领域存在的用词歧义和检索词简短的问题,本文提出了一种基于TF-IQF模型和图聚类的个性化查询建议方法。对于用户的查询请求,提供查询建议,帮助用户进行查询修正,进而检索到其所需的信息;同时通过获取不同用户的查询偏好,以达到个性化查询推荐的目的。实验结果表明,该方法能够给出个性化的查询建议,为用户提供潜在感兴趣的资源,具有较高的准确率。     

一种有效的图索引查询算法

图是一种很强大的工具,在许多应用领域如化学化合物,生物信息,XML文档,图像处理和社会网络等应用中它可以表示其对象及它们之间的关系,而且在模式化复杂的结构数据时图发挥了越来越重要的作用.图的一个最基本的操作是图的查询处理,经典的图查询问题是给出图数据库和一个查询图,从图数据库中找出那些包含查询图作为子图的图.在本文中对于给定的查询图提出了一种有效的索引策略,在图数据库中选取具有判别力的树作为特征树,对这些特征树进行编码,将结构之间的比较转化为编码序列之间的比较,并利用特征树建立索引,提出了两种剪枝策略,过滤掉数据库中与查询图不是精确匹配的图.实验验证了所提出查询处理算法的有用性和有效性.     

一种基于命名实体的搜索结果聚类算法

针对现有搜索结果聚类方法中形成的聚类标签可读性比较差的情况,提出一种基于命名实体的搜索结果聚类方法——NEC。命名实体作为文本中的基本信息元素,具有一定的实际意义,表征主题的能力比一般词语更强,也更具可读性。算法以搜索结果文档中存在的命名实体作为聚类的标签,经过一定的标签选择和聚类合并策略,形成最终的聚类结果,提高聚类标签的可读性。实验证明,该方法是一种可行的搜索结果聚类方法。     

层次序列索引的大规模动态标签图子图查询

标签图常用于智能交通网、生物信息网等新兴领域的建模。子图查询作为图数据分析的关键问题，引起了研究者的广泛关注。对现有子图查询算法的研究发现，随着图数据规模增大且频繁更新，传统子图查询算法普遍存在查询效率低，存储开销大，忽略顶点标签信息等问题。为此，提出了一种支持大规模动态标签图子图查询的层次序列索引（Dynamic Hierarchical Sequence，DHS），该索引提取数据图中带有顶点编号的层次拓扑序列关系以实现子图查询；针对图的动态变化，提出了更新点拓扑扩展式索引维护策略，仅从局部变化顶点及边开始进行增量式更新，大大降低了重建索引造成的巨大开销；提出了基于DHS索引的子图查询方法，仅需将查询图与数据图的层次序列进行匹配即可获得候选集，并在其上利用关系匹配策略获得最终查询结果。实验证明提出的方法在保证高效查询的同时降低了索引的创建及维护时间，提高了子图查询效率。     

半结构化数据相似搜索的索引技术研究

为了在海量、高维、动态的半结构化数据集上进行有效的相似搜索，该文提出一种采用聚类技术进行索引构建与更新的多路平衡树－－CSS－树以及基于CSS－树的相似搜索与动态更新的算法。CSS－树借鉴SS^ -树基于聚类进行节点组织与分裂的基本思想，避免了根据坐标准进行分裂时所要求的维不相关性，同时在节点组织、分裂算法和搜索算法等方面进行了改进，提出了新的搜索剪枝策略，实验表明，该结构及算法对海量半结构化数据相似搜索和效率明显优于传统算法。     

基于双索引的子图查询算法

传统的子图查询算法大多只在图数据库上进行一次挖掘算法,即在图数据库上建立稳定的数据库索引后将不再对索引进行更新.随着查询兴趣的改变或数据库的频繁更新,原有的数据库索引将不再能提供有用的信息来减少查询过程中候选图的数量.为此,提出一种双索引的子图查询算法,同时在数据库和查询流上挖掘频繁子图并建立索引.子图查询和查询流索引的建立同步进行,即使查询兴趣改变,查询流索引也能自适应地更新索引信息来优化查询效率.针对数据库的频繁更新,查询流索引已提供实时的有效信息,数据库索引无需重新建立.实验结果表明,双索引的结合能有效提高查询子图的处理效率.     

一种加权稠密子图社区发现算法

目前,针对复杂网络的社区发现算法大多仅根据网络的拓扑结构来确定社区,然而现实复杂网络中的边可能带有表示连接紧密程度或者可信度意义的权重,这些先验信息对社区发现的准确性至关重要.针对该问题,提出了基于加权稠密子图的重叠聚类算法（overlap community detection on weighted networks,简称OCDW）.首先,综合考虑网络拓扑结构及真实网络中边权重的影响,给出了一种网络中边的权重定义方法;进而给出种子节点选取方式和权重更新策略;最终得到聚类结果.OCDW算法在无权网络和加权网络都适用.通过与一些经典的社区发现算法在9个真实网络数据集上进行分析比较,结果表明算法OCDW在F度量、准确度、分离度、标准互信息、调整兰德系数、模块性及运行时间等方面均表现出较好的性能.     

一种基于子空间聚类的图像分层索引方法

随着多媒体技术的发展,许多领域产生大量的高维数据集。为了有效地检索这些高维数据,高维索引成为人们研究的热点。聚类树是一种有效地支持高维数据检索的索引结构。提出了一种基于子空间聚类的聚类树结构,该索引结构基于一种改进的CLIQUE聚类算法,利用小波变换的多尺度特性对图像特征分布曲线进行不同尺度的小波变换,去除一些小的分类和可能的噪声干扰,从而得到不同粒度下的层次聚类。在层次聚类的基础上,建立起分层索引结构。由于改进的聚类算法使用爬山法确定子空间聚类,因而有效地避免了用户参数的定义。实验结果证明,该方法在不需要用户设定聚类参数下能够进行有效聚类,在不同尺度下构建的聚类结构能够有效地组织图像关系,大大提高图像的检索效率。     

基于小世界模型的高维索引算法

高维索引作为基于内容检索和模式识别等领域的一项关键技术,其性能直接影响整个系统的查询速度和准确率,但高维情况下的 “维度灾难”一直制约着相应检索性能的提高。通过分析小世界模型,提出了完整的逐跳逼近索引算法,该算法仅维护点与点在度量空间上的局部邻近关系,通过将查询过程的“关注点”逐步往查询命中区域跳跃逼近来实现高维空间数据点间的范围查询和近似近邻查询。实验证明该方法在不依赖索引数据的先验分布情况下能有效地处理高维数据向量的检索,且具有良好的可维护性与拓展性。     

面向图相似性搜索的高效图编辑距离算法

在图相似性搜索问题中,图编辑距离是较为普遍的度量方法,其计算性能很大程度上决定了图相似性搜索算法的性能。针对传统图编辑距离算法中存在的因大量冗余映射和较大搜索空间导致的性能低下问题,提出了一种改进的图编辑距离算法。该算法首先对图中顶点进行等价划分,以此计算映射编码来判断等价映射;然后定义映射完整性更新等价映射优先级,选出主映射参与扩展;其次,设计高效的启发式函数,提出基于映射编码的下界计算方法,快速得到最优映射。最后,将改进的图编辑距离算法扩展应用于图相似性搜索。在不同数据集上的实验结果表明,该算法具有更好的搜索性能,在搜索空间上最大可降低49%,速度提升了约29%。     

图聚类算法的评价模型

关系数据可抽象为网络,在通常情况下,缺乏对这些现实网络背景知识的了解。为了评价图聚类算法在现实网络上的性能表现,构建了一种接近现实的网络模型,通过算法在模型网络上的性能表现来推断其分析现实网络的能力。为了确保此推断的合理性,构建的模型网络具有与所研究网络完全相同的一阶统计特征。同时,构建的模型网络可具有任意设定的集团结构,这就相当于给定了背景知识,即真实的分类信息是已知的。实例说明,构建的模型为客观评价图聚类算法提供了一条途径。     

DSP平台的图像特征点快速索引结构

针对DSP(digital signal processor,数字信号处理器)平台上的图像特征点匹配问题,提出了一种高效的基于自聚类二分查找树的快速索引结构,并设计了适合于DSP结构特点的索引存储布局。通过在离线情况下将特征点参考数据集逐级地二分聚类,生成多级索引结构。以顺序数组的方式将树状索引结构存储到连续的内存空间中,便于导出为数据文件存储及进一步加载到DSP内存中使用。实验表明,该索引结构能够快速有效地在DSP平台完成特征点匹配工作。     

Adaptive indexing for content-based search in P2P systems

One of the major challenges in Peer-to-Peer (P2P) file sharing systems is to support content-based search. Although there have been some proposals to address this challenge, they share the same weakness of using either servers or super-peers to keep global knowledge, which is required to identify importance of terms to avoid popular terms in query processing. As a result, they are not scalable and are prone to the bottleneck problem, which is caused by the high visiting load at the global knowledge maintainers. To that end, in this paper, we propose a novel adaptive indexing approach for content-based search in P2P systems, which can identify importance of terms without keeping global knowledge. Our method is based on an adaptive indexing structure that combines a Chord ring and a balanced tree. The tree is used to aggregate and classify terms adaptively, while the Chord ring is used to index terms of nodes in the tree. Specifically, at each node of the tree, the system classifies terms as either important or unimportant. Important terms, which can distinguish the node from its neighbor nodes, are indexed in the Chord ring. On the other hand, unimportant terms, which are either popular or rare terms, are aggregated to higher level nodes. Such classification enables the system to process queries on the fly without the need for global knowledge. Besides, compared to the methods that index terms separately, term aggregation reduces the indexing cost significantly. Taking advantage of the tree structure, we also develop an efficient search algorithm to tackle the bottleneck problem near the root. Finally, our extensive experiments on both benchmark and Wikipedia datasets validated the effectiveness and efficiency of the proposed method.     

一种快速网页检索结果聚类策略

在网页聚类中,HAC（Hierarchical Agglomerative Clustering）算法和K-means算法都是经常用到的。但它们都有各自的不足。提出一种两阶段聚类方法。第一阶段利用HAC聚类算法对网络检索结果的标题进行聚类,第二阶段以第一阶段结果作为初始中心用K-means算法聚类标题和摘要取得比较合理的聚类结果。由于标题一般都比较短,可以大大减少HAC算法的运行时间。这样既满足网络检索对时间的要求又可以得到较好的聚类结果。     

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

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

融合层次类型信息的双向图注意力机制的知识图谱嵌入模型

知识图谱嵌入旨在将实体与关系映射到低维且稠密的向量空间中。目前已有的嵌入模型仍存在以下两个方面的缺陷：现有的模型大多只关注知识图谱的语义信息,而忽略了大量三元组的隐藏信息;现有的模型仅关注了实体的单向信息,而忽略了双向的潜在信息。针对以上问题,提出了一种融合层次类型信息的双向图注意力机制的知识图谱嵌入模型Bi-HTGAT,该模型设计了层次类型注意力机制,考虑不同关系下每种类型的不同实体对中心实体的贡献。同时引入了关系的方向注意力机制,通过融合不同方向的邻居信息来更新实体和关系嵌入,最终聚合两部分信息以得到实体的最终嵌入。在基准数据集上的实验证明,Bi-HTGAT在链接预测任务上性能明显优于其他基线模型,充分证明了Bi-HTGAT能够进一步提高嵌入结果的精准度。     

一种基于谱图理论的Web图像搜索方法*

在对当前Web图像搜索面临的问题进行剖析的基础上,根据谱图理论的研究成果,提出了一种针对Web图像搜索的新的解决方法。这种基于谱图理论的方法极有可能是一种更有效的新型Web图像信息分析方法,从而可以大幅提高现有基于链接的Web图像搜索引擎的工作效率。