基于可搜索加密的密态知识图谱存储和检索方案

随着云计算的快速发展,知识图谱数据外包成为一种流行的趋势。医疗、金融等诸多领域中的知识图谱有着隐私敏感特性,然而云服务器并不是完全可信的,为了保护数据在云服务器上的机密性和完整性,需要使用加密等方式来保护知识图谱数据的安全。提出了一种基于可搜索加密的密态知识图谱存储方案,可以有效保护数据的机密性和完整性,并且支持在密态数据上的检索。该方案充分考虑了知识图谱实体及其关系顺序读取的必要性,从而对密态索引设计进行优化,加快检索效率。实验结果显示,密态知识图谱的一跳子图查询平均时间为非密态知识图谱的2.09倍,表明该方案在安全性和查询效率上取得了良好的平衡。     

支持语义扩展的动态多关键词密文排序检索

针对云存储环境下已有的动态多关键词密文排序检索方案不支持关键词语义扩展、不具备前向安全和后向安全的问题，提出一种支持语义检索且具备前向安全和后向安全的动态多关键词密文排序检索方案。该方案通过构建语义关系图实现查询关键词的语义扩展；使用树索引结构实现数据的检索和动态更新；利用向量空间模型实现多关键词排序搜索；基于安全K近邻算法对维度扩展后的索引和查询向量进行加密。安全性分析表明，该方案在已知密文模型下是安全的且具有动态更新时的前向安全和后向安全。效率分析及仿真实验结果表明，该方案在服务器检索效率方面优于目前同类型具有相同安全性或相同功能的方案。     

基于关键词的RDF数据图查询模型研究

随着语义网数据的海量涌现,人们更加关注RDF图的数据查询效率,通过关键词匹配直接查询RDF数据图成为一个研究热点。针对关键词查询中普遍存在的结果冗余与偏离等问题,提出了一种基于关键词的RDF数据图查询模型。该模型首先采用提出的基于迭代的图查询算法(ISGR)对所查询关键词进行子图匹配,得到唯一且最大的结果子图集合;然后根据关键词图与结果子图之间的结构信息,利用统计语言模型,给出了一种结果子图排序方法(SimLM)。对比实验表明,提出的查询模型及排序方法在一致性和相关性方面的性能优于传统模型。     

T-STAR: 一种基于关键词的关系数据库时态信息检索方法*

将时态信息融入到信息检索技术中可以有效提高检索效果,时态信息检索已有较多的研究,而现有数据库信息检索方法还缺乏对时态信息有效利用。针对这一研究问题,提出关系数据库上基于时态语义的关键词检索方法,引入时态信息构建时态数据图,设计时态相关性评分机制,在时态图搜索过程中引入时态语义约束,设计基于关键词的时态检索算法。实验验证了该方法可以有效提高数据库信息检索效果,而检索性能并没有降低。     

SQM:基于Spark的大规模单图上的子图匹配算法

针对大规模数据图下基于回溯法的子图查询算法的准确率低、开销大等问题，为提高查询准确率，降低大图下的查询开销，提出一种基于Spark的子图匹配（SQM）算法。首先根据结构信息过滤数据图，再将查询图分割成基本查询单元；然后对每一个基本查询单元分别匹配后进行Join操作；最后运用并行化提高了算法的运行效率，减小了搜索空间。实验结果表明，与Stwig、TurboISO算法相比，SQM算法在保证查询结果不变的情况下，速度提高了50%。     

基于子图相交的社交账号与知识图谱实体对齐

社交媒体与知识图谱的数据各具特点,相互之间的数据互通具有较强的现实意义,而社交账号与知识图谱实体的对齐是数据互通的前提。针对社交媒体与知识图谱的特点,提出了一种基于子图相交的对齐方法,旨在给定社交账号的情况下,根据社交账号的相关信息在知识图谱中找到正确的对应条目。该方法在候选实体生成阶段对比实验了不同的生成策略。在目标实体选择阶段提出一种基于子图相交的算法,利用社交账号的社交关系在知识图谱中映射成子图。子图相交算法通过考察子图中候选实体周围顶点的"稠密"程度,确定社交账号所对应的目标实体。由于该领域尚无公开可用的测试数据集,构造了一个基于Twitter与Wikidata的对齐数据集,使用该数据集对该方法进行评估,对比测试了标题匹配算法和AGDISTIS算法,子图相交算法能够达到更好的效果。     

基于索引的子图查询技术研究进展

图作为表示实体间的数据结构，在社区发现、生物化学分析、社会安全分析等数据关联性要求较高的领域有着广泛的应用。对于大规模数据下进行实时的图查询问题，通过构建合适的索引可以有效降低查询响应时间，提高查询精确度。首先介绍基于索引的子图查询算法的基本结构；然后按索引的构建方式将主流算法分为基于枚举的方法和基于频繁模式挖掘的方法两大类，分别从索引特征、索引结构、应用数据集等方面进行介绍和分析；最后对基于索引的子图查询算法面临的主要问题进行总结和分析，阐述了最新的分布式系统下图查询技术，并对未来趋势进行展望。     

KWSDS:关系数据库中Top-k关键词搜索系统

关系数据库中的关键词搜索技术已经成为信息检索领域的研究热点,它为没有任何SQL语法知识的用户提供了一个简单友好的接口.但是现存的关键词搜索系统主要依赖于数据图或模式图,而单独使用数据图或模式图的算法搜索效率不高,结果准确率也较低.设计实现了一个Top-k关键词搜索系统(keyword search system based on database graph and schema graph,KWSDS),用户提交关键词后,系统对关键词进行预处理,消除一些脏关键词.首次提出使用数据图与模式图相结合的方法,设计了同表查询算法和异表查询算法,分析了算法的正确性和时间复杂度,并且提出了相关性结果排序方法.KWSDS系统的搜索算法运行时间短,搜索结果准确性高,具有良好的查询性能.最后通过实验验证了KWSDS的效率.     

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

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

高效的多关键词匹配最优路径查询算法KSRG

为改进基于关键词的最优路径查询算法,在大规模图以及多查询关键词下复杂度过高与可扩展性不足的缺陷,依据查询关键词序列构建候选路径的策略提出一种高效查询算法。该算法在路径构建过程中优先满足查询关键词的全包含条件,以关键词引导下的路径拓展替代盲目的邻边拓展,从而高效地构建候选路径;通过变量缩放与无效路径裁剪,将问题求解复杂度由阶乘级转化为多项式级,进一步降低算法复杂度,提升可扩展性。通过四组图数据集下的实验,验证了算法在查询效率与可扩展性上的提升。     

多编码树GPU并行轴心子图匹配

子图同构问题是非确定多项式(NP)完全问题,而轴心子图同构是一种特殊的子图同构问题.针对现在已经有许多高效的子图同构算法,然而对于轴心子图同构问题目前并没有基于GPU的搜索算法,且通过改造已有的子图同构算法来解决轴心子图匹配问题会产生大量不必要的中间结果这一问题,提出了一种基于GPU的轴心子图同构算法.首先,通过一种新...     

Utilizing similarity relationships among existing data for high accuracy processing of content-based image retrieval

Retrieving similar images based on its visual content is an important yet difficult problem. We propose in this paper a new method to improve the accuracy of content-based image retrieval systems. Typically, given a query image, existing retrieval methods return a ranked list based on the similarity scores between the query and individual images in the database. Our method goes further by relying on an analysis of the underlying connections among individual images in the database to improve this list. Initially, we consider each image in the database as a query and use an existing baseline method to search for its likely similar images. Then, the database is modeled as a graph where images are nodes and connections among possibly similar images are edges. Next, we introduce an algorithm to split this graph into stronger subgraphs, based on our notion of graph’s strength, so that images in each subgraph are expected to be truly similar to each other. We create for each subgraph a structure called integrated image which contains the visual features of all images in the subgraph. At query time, we compute the similarity scores not only between the query and individual database images but also between the query and the integrated images. The final similarity score of a database image is computed based on both its individual score and the score of the integrated image that it belongs to. This leads effectively to a re-ranking of the retrieved images. We evaluate our method on a common image retrieval benchmark and demonstrate a significant improvement over the traditional bag-of-words retrieval model.     

Blockchain Based Consensus Algorithm and Trustworthy Evaluation of Authenticated Subgraph Queries

Over the past era, subgraph mining from a large collection of graph database is a crucial problem. In addition, scalability is another big problem due to insufficient storage. There are several security challenges associated with subgraph mining in today’s on-demand system. To address this downside, our proposed work introduces a Blockchain-based Consensus algorithm for Authenticated query search in the Large-Scale Dynamic Graphs (BCCA-LSDG). The two-fold process is handled in the proposed BCCA-LSDG: graph indexing and authenticated query search (query processing). A blockchain-based reputation system is meant to maintain the trust blockchain and cloud server of the proposed architecture. To resolve the issues and provide safe big data transmission, the proposed technique also combines blockchain with a consensus algorithm architecture. Security of the big data is ensured by dividing the BC network into distinct networks, each with a restricted number of allowed entities, data kept in the cloud gate server, and data analysis in the blockchain. The consensus algorithm is crucial for maintaining the speed, performance and security of the blockchain. Then Dual Similarity based MapReduce helps in mapping and reducing the relevant subgraphs with the use of optimal feature sets. Finally, the graph index refinement process is undertaken to improve the query results. Concerning query error, fuzzy logic is used to refine the index of the graph dynamically. The proposed technique outperforms advanced methodologies in both blockchain and non-blockchain systems, and the combination of blockchain and subgraph provides a secure communication platform, according to the findings.     

图数据流上时间尊重图模式匹配算法研究

现有的动态子图匹配研究中忽略了模式图中的时间信息,使用户难以得到想要查询的真实结果.针对这种情况,首先设计一种简洁的中间结果保存形式,将匹配结果直接在数据图中以图进行存储;接着改进边缘转换模型,当数据图有边插入/删除时对其快速增量维护并报告结果;最后根据边转换模型设计了一个时间尊重图模式匹配算法,提高了匹配搜索效率.对真实网络流量数据和综合社交流数据进行实验评估,结果表明算法能够有效减少图模式匹配的执行时间和空间花销.     

基于信息熵的子图匹配算法

子图查询是指输入一个图数据库和查询子图,输出图数据库中包含查询子图的图集合,它广泛应用于社会网、生物网和信息网的查询应用中。目前的子图查询算法大多采用静态消耗测算模式,此类测算模式在图中点数和连接边数呈指数分布时,会在少数节点上花费较多时间遍历其邻节点,导致查询算法效率低下。根据信息熵在信息度量中的作用,将条件信息熵作为启发式匹配的依据,提出了基于信息熵的子图匹配算法。实验表明,基于信息熵的子图匹配算法具有更高的查询效率,且在指数分布的数据集上效果更明显。     

煤矿安全知识图谱构建及智能查询方法研究

煤矿企业正从信息化建设向智能化迈进,以大数据、人工智能为代表的网络新技术已促进了矿山领域的智能化发展。但是由于煤矿领域数据信息的繁杂性,难以对其进行统一而高效地收集、信息挖掘,进而促进深一步的特定领域研究和应用。将知识图谱技术初步引入煤矿安全领域,对相关知识概念分类建模,并基于图数据库存储,用实体关系图的方式直观地描述各类概念及概念之间的关系,然后基于初步构建的知识图谱,提出了一种自然语言知识查询方法。实验证明,该文提出的方法具有较高的查全率和查准率,基于Spark的并行朴素贝叶斯问题分类方法可以在保证准确率的同时,显著提升训练效率。该文工作为煤矿安全知识图谱构建及智能查询做了初步有益探索。     

Structure and attribute index for approximate graph matching in large graphs

The increasing popularity of graph data in various domains has lead to a renewed interest in developing efficient graph matching techniques, especially for processing large graphs. In this paper, we study the problem of approximate graph matching in a large attributed graph. Given a large attributed graph and a query graph, we compute a subgraph of the large graph that best matches the query graph. We propose a novel structure-aware and attribute-aware index to process approximate graph matching in a large attributed graph. We first construct an index on the similarity of the attributed graph, by partitioning the large search space into smaller subgraphs based on structure similarity and attribute similarity. Then, we construct a connectivity-based index to give a concise representation of inter-partition connections. We use the index to find a set of best matching paths. From these best matching paths, we compute the best matching answer graph using a greedy algorithm. Experimental results on real datasets demonstrate the efficiency of both index construction and query processing. We also show that our approach attains high-quality query answers.     

大规模时序图中持续性稠密子图搜索算法研究

时序图是一种边上带有时间戳的图结构,其中边上的时间戳表示该边出现时间,即图随时间变化不断变化.图数据中的稠密子图挖掘问题具有非常强烈的现实意义.目前,时序图中大多数现有的工作都集中在稠密子图检测问题,该问题目标是找到时序图中所有的目标子图.然而,当时序图的规模过大时,这一问题将变得极其复杂且收效甚微.旨在研究在时序图中...