大型网络中近似子图匹配研究

为降低噪声对近似子图匹配准确率的影响,提出一种改进的近似子图匹配方法。在预处理阶段,利用k-近邻顶点集为数据图中的每个顶点建立标签-权重向量索引。在查询过程中,基于单个近邻标签的权重距离和所有近邻标签的整体匹配程度进行两级过滤,生成顶点候选集,采用生成树匹配和图匹配的方式确定查询图在大型网络中的位置。在真实数据集上的实验结果表明,该方法具有较高的执行效率和匹配准确率。     

基于双索引的近似子图匹配

越来越多的大型复杂网络使得图结构的研究变得日益重要,其中近似子图查询备受关注。为了提高查询效率,利用顶点的邻接关系特征为每个顶点建立索引,减少了匹配顶点的数量;并基于结构和标签对大型数据图进行划分,缩小了匹配时的搜索空间。利用离线时建立的双索引,查询时首先利用顶点间的近邻关系判定公式过滤掉大量不满足匹配关系的候选顶点,然后在一定的划分空间中进行边的匹配。真实数据集中的实验表明,与单纯的划分方法或近邻关系索引相比较,双索引机制对于查询的效率和准确率方面均有明显改善。     

非结构化对等计算系统中多维范围搜索

对等计算数据管理中的一个重要问题是如何有效地支持多维数据空间上的相似性搜索.现有的非结构化对等计算数据共享系统仅支持简单的查询处理方法,即匹配查询处理.将近似技术和路由索引结合在一起,设计了一种简单、有效的索引结构EVARI(扩展近似向量路由索引).利用EVARI,每个节点不仅可以在本地共享的数据集上处理范围查询,而且还可以将查询转发给最有希望获得查询结果的邻居节点.为了建立EVARI,每个节点使用空间划分技术概括本地的共享内容,并与邻居节点交换概要信息.而且,每个节点都可以重新配置自己的邻居节点,使得相关节点位置相互邻近,优化了系统资源配置,提升了系统性能.仿真实验证明了该方法的良好性能.     

一种基于尾匹配q-gram的近似串匹配算法

近似串匹配是生物信息学、文本检索、信号处理等领域的一个基础问题,如何提高近似串匹配的速度一直都是研究的关键问题。提出一种新的在大文本库中快速查找近似匹配的无损过滤算法。为保证在大文本库中的匹配速度,本算法使用了查询速度较快的q-gram索引。为通过提高过滤算法的过滤效率达到提升算法整体性能的目的,详细分析了含有匹配串的文本区域,提取了一些基于尾匹配q-gram特征的新过滤条件,然后用这些特征优化了过滤算法的过滤标准。实验数据表明,新过滤条件有效地提高了算法的过滤效率,提升了算法的整体性能。结果显示新算法适合各种匹配错误率下的近似匹配,算法的通用性较强。     

基于邻居信息聚合的子图同构匹配算法

图匹配在现实中被广泛运用,而子图同构匹配是其中的研究热点,具有重要的科学意义与实践价值。现有子图同构匹配算法大多基于邻居关系来构建约束条件,而忽略了节点的局部邻域信息。对此,提出了一种基于邻居信息聚合的子图同构匹配算法。首先,将图的属性和结构导入到改进的图卷积神经网络中进行特征向量的表示学习,从而得到聚合后的节点局部邻域信息;然后,根据图的标签、度等特征对匹配顺序进行优化,以提高算法的效率;最后,将得到的特征向量和优化的匹配顺序与搜索算法相结合,建立子图同构的约束满足问题（CSP）模型,并结合CSP回溯算法对模型进行求解。实验结果表明,与经典的树搜索算法和约束求解算法相比,该算法可以有效地提高子图同构的求解效率。     

一种支持多种子近似串匹配的q-gram索引

如何在大型文本库中快速找出给定串的近似串是大数据时代要解决的关键问题。基于多种子的近似串匹配算法因匹配速度快而得到众多学者的青睐,但巨大的索引空间消耗也使其难以处理大型文本库。提出了一种支持多种子的q-gram索引结构,通过该索引能够快速地计算出给定任意长度连续种子的地址集合,解决了多种子近似串匹配算法中种子的数目和长度受存储空间限制的问题。实验数据显示,新索引方案成倍地减少了存储空间的消耗。实验结果表明,提出的索引方案在大数据环境下的多种子近似匹配中具有一定的优势。     

基于边映射表连接的匹配算法

针对面向语义网络图匹配的特殊性, 在基于状态回溯搜索算法的基础上提出一种新的称为基于边映射表连接的匹配算法, 利用语义网络图的有向性, 将图匹配问题转换为对搜索路径的规划, 并采用深度优先算法形成搜索步, 同时对目标图的所有边建立索引, 加快以边匹配为中心形成边映射表的过程, 最后对边映射表进行连接形成结果集。在真实数据集上的实验结果表明, 该算法具有较高的执行效率。     

基于OAN的知识图谱查询研究

知识图谱查询是目前知识图谱研究中最广泛的应用,能够有效提高搜索引擎查询效率。然而,现有的知识图谱的查询研究多是基于节点标签的子图匹配。由于节点标签不能体现节点间的语义信息,导致查询结果的语义相关性不高。针对此问题,本文提出了一种基于本体和邻居信息的查询算法OAN(Ontology and Neighborhood)。首先,结合本体相似度和邻居相似度来确定查询节点的候选集,以此提高候选节点的语义相似度;其次,通过边检测算法移除那些不满足条件的查询节点候选集,以此减少查询规模;然后,在目标图上查找满足边标签同构的查询子图,并计算节点的标签相似度和结构相似度总和,给每个结果集打分后排序,获得最终排序后的结果集;最后,通过在真实数据集上与已有查询算法进行对比实验,实验结果表明:本文所提出的方法无论是在精确度上,还是在查询效率方面都有所提高。     

PCPF:一种面向多媒体数据库中高维向量匹配的并行索引结构

提高特征向量的匹配效率是将高维局部特征运用于多媒体数据检索的关键.面向多核处理器架构,提出一种新的PCPF索引以及PCPF并行构建与并行查询匹配算法.PCPF并行构建算法通过量化特征向量构建近似向量空间上的高维索引结构,并进行空间划分并行构建多个子索引分支;PCPF并行查询匹配算法利用优先队列在邻近子分支上并行过滤得到...     

基于Hadamard变换的高维图像检索方法

传统索引方法对高维数据进行近邻搜索时会面临维数灾难问题,向量近似方法是一种有效的高维检索方法。提出一种 Hadamard 变换域上的向量近似方法,在变换域能量最大的分量上建立顺序索引,然后建立近似向量文件。同时提出低維过滤算法,可以在近邻搜索过程中高效排除不匹配近似向量,减少 I/O 访问时间,提高查询效率。在大型高维图像特征库上的实验表明,该方法性能优于小波变换域的向量近似方法。