一种面向图包容搜索的图索引模型

由于图模型的广泛采用,图数据的快速包容搜索在许多不同领域广泛应用。给定一个模型图集D和一个查询图集q,传统的图搜索旨在检索所有包含q的图(qg),与此不同,包容搜索有其自身的索引特性,针对这些特性进行系统地研究,并提出一种基于对比子图的索引模型（csgIndex）：使用一个冗余感知特征选择过程,csgIndex能挑选出一个鲜明的具有区分力的对比子图集,并最大化其索引能力。对实时测试数据的实验结果显示,csgIndex对不同的包容搜索荷载能达到近优化修剪力,相较于传统图搜索方法表现出明显的索引性能优势。     

NVSA:一种具有可变节点值的查询图搜索算法

图模型作为一种重要的数据结构,常被应用于众多不同领域并被广泛研究。随着图数据规模的日益增大,大图上的子图搜索问题变得极为重要。然而,目前已有的研究成果在大图上的执行效率并不太理想,而且没有考虑查询图上存在节点值可变的情况。为解决具有可变节点值的查询图在大图上的搜索问题,本文提出基于双索引的NVSA算法。首先通过合并相邻同类点构建CP索引和Vin索引,然后根据索引结构优化加速子图搜索算法。真实数据集上的实验表明,NVSA算法具有有效性和高效性。     

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

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

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

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

高效低索引的图相似性搜索算法

图相似性搜索是在给定的度量标准下查找与查询图相似的图集合,目前大多采用“过滤-验证”的计算框架。针对现有方法中过滤下界不紧密和索引空间占用较大等问题,提出了一种基于查询图分区的多层级过滤、低索引空间占用的图相似性搜索算法Z-Index。该算法首先通过全局粗粒度过滤得到预候选集;然后提出基于扩展概率的查询图分区算法,并采用层级过滤机制进一步精简候选集,增强下界紧密性;最后引入序列相似性差值计算序列中数据分布的稀疏度,提出分区压缩和差值压缩两种编码压缩算法,并据此构建“零”索引结构,降低索引空间开销。实验结果表明,Z-Index算法所得下界更加紧密,产生的候选集大小可减少50%左右,算法执行时间大大缩短,且该算法在索引空间占用极小的情况下仍具有可扩展性。     

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

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

基于拓扑序列的DAG子图包含查询算法研究

图模型具有强大的表达能力,被广泛用于各种应用领域的数据建模.如何在大规模图数据库中进行高效子图包含查询是当前的研究难点之一.由于子图同构是一个NP完全问题,在现有的子图包含查询算法中,基于图特征的索引技术被广泛用来提高查询处理性能,但是这些索引结构的维护代价较高.针对有向无环图提出了一种基于拓扑序列的子图包含查询算法,...     

基于化合物库测试的gSpan算法

gSpan算法是一种基于频繁图的数据挖掘算法。该算法基于无候选人产生的频繁子图,采用深度优先搜索策略挖掘频繁连接子图。由于其设计结构具有连续性以及无候选人产生,算法的性能得以提高,在执行速度上可以达到前人算法如FSG算法的15~100倍。基于化合物库Chemical-340测试发现,该算法能够以卓越性能有效挖掘频繁子图。该算法可以应用在搜索具有相同子结构的化合物研究中,对相关领域研究发展具有重要意义。     

基于化合物库测试的gSpan算法

gSpan算法是一种基于频繁图的数据挖掘算法。该算法基于无候选人产生的频繁子图，采用深度优先搜索策略挖掘频繁连接子图。由于其设计结构具有连续性以及无候选人产生，算法的性能得以提高，在执行速度上可以达到前人算法如FSG算法的15～100倍。基于化合物库Chemical_340测试发现，该算法能够以卓越性能有效挖掘频繁子图。该算法可以应用在搜索具有相同子结构的化合物研究中，对相关领域研究发展具有重要意义。     

基于Voronoi图的组最近邻查询

组最近邻查询由于涉及多个查询点,因此比传统的最近邻查询更为复杂.充分考虑查询点的分布特征以及它们构成的几何图形的性质和特点,给出组最近邻所应满足的条件及判断组最近邻的理论方法.提出基于Voronoi图的组最近邻查询的VGNN算法,可以精确求解查询点集的最近邻.对于查询点不共线的情况,该算法的查询方式是以一点为中心、向外扩张式的;对于查询点共线的情况,该算法给出搜索范围,限定了参与计算的数据点的个数.给出基于Voronoi图的VTree索引.实验结果表明,基于VTree索引的VGNN算法具有较好的性能,并且当查询点不共线时,其性能具有较高的稳定性.     

Indexing through laplacian spectra

With ever growing databases containing multimedia data, indexing has become a necessity to avoid a linear search. We propose a novel technique for indexing multimedia databases in which entries can be represented as graph structures. In our method, the topological structure of a graph as well as that of its subgraphs are represented as vectors whose components correspond to the sorted laplacian eigenvalues of the graph or subgraphs. Given the laplacian spectrum of graph G, we draw from recently developed techniques in the field of spectral integral variation to generate the laplacian spectrum of graph G+e without computing its eigendecomposition, where G+e is a graph obtained by adding edge e to graph G. This process improves the performance of the system for generating the subgraph signatures for 1.8% and 6.5% in datasets of size 420 and 1400, respectively. By doing a nearest neighbor search around the query spectra, similar but not necessarily isomorphic graphs are retrieved. Given a query graph, a voting schema ranks database graphs into an indexing hypothesis to which a final matching process can be applied. The novelties of the proposed method come from the powerful representation of the graph topology and successfully adopting the concept of spectral integral variation in an indexing algorithm. To examine the fitness of the new indexing framework, we have performed a number of experiments using an extensive set of recognition trials in the domain of 2D and 3D object recognition. The experiments, including a comparison with a competing indexing method using two different graph-based object representations, demonstrate both the robustness and efficacy of the overall approach.     

Graph-based shape indexing

Graphs have become growingly important in representing shapes in computer vision. Given a query graph, it is essential to retrieve similar database graphs efficiently from a large database. In this paper, we present a graph-based indexing technique which overcomes significant drawbacks of the previous work (Demirci et al. in Comput Vis Image Underst 110(3):312–325, 2008) using a recently developed theorem from the domain of matrix analysis. Our technique starts by representing the topological structure of a graph in a vector space. As done in the previous work, the topological structure of a graph is constructed using its Laplacian spectra. However, unlike the previous approach, which represents all sugraphs of a database graph in the vector space to account for local similarity, a database graph in the proposed framework is represented as a single vector. By performing a range search around the query, the proposed indexing technique returns a set with both partial and global similarity. Empirical evaluation of the algorithm on an extensive set of retrieval trials including a comparison with the previous approach in both 2D and 3D demonstrates the effectiveness, efficiency, and robustness of the overall approach.     

A partition index for XML and semi-structured data

XML and other semi-structured data can be represented by a graph model. The paths in a data graph are used as a basic constructor of a query. Especially, by using patterns on paths, a user can formulate more expressive queries. Patterns in a path enlarge the search space of a data graph and current research for indexing semi-structured data focuses on reducing the search space. However, the existing indexes cannot reduce the search space when a data graph has some references.

In this paper, we introduce a partitioning technique for all paths in a data graph and an index graph which can effectively find appropriate path partitions for a path query with patterns.     

Efficient matching and indexing of graph models in content-basedretrieval

In retrieval from image databases, evaluation of similarity, based both on the appearance of spatial entities and on their mutual relationships, depends on content representation based on attributed relational graphs. This kind of modeling entails complex matching and indexing, which presently prevents its usage within comprehensive applications. In this paper, we provide a graph-theoretical formulation for the problem of retrieval based on the joint similarity of individual entities and of their mutual relationships and we expound its implications on indexing and matching. In particular, we propose the usage of metric indexing to organize large archives of graph models, and we propose an original look-ahead method which represents an efficient solution for the (sub)graph error correcting isomorphism problem needed to compute object distances. Analytic comparison and experimental results show that the proposed lookahead improves the state-of-the-art in state-space search methods and that the combined use of the proposed matching and indexing scheme permits for the management of the complexity of a typical application of retrieval by spatial arrangement     

Content-based image retrieval based on a fuzzy approach

A typical content-based image retrieval (CBIR) system would need to handle the vagueness in the user queries as well as the inherent uncertainty in image representation, similarity measure, and relevance feedback. We discuss how fuzzy set theory can be effectively used for this purpose and describe an image retrieval system called FIRST (fuzzy image retrieval system) which incorporates many of these ideas. FIRST can handle exemplar-based, graphical-sketch-based, as well as linguistic queries involving region labels, attributes, and spatial relations. FIRST uses fuzzy attributed relational graphs (FARGs) to represent images, where each node in the graph represents an image region and each edge represents a relation between two regions. The given query is converted to a FARG, and a low-complexity fuzzy graph matching algorithm is used to compare the query graph with the FARGs in the database. The use of an indexing scheme based on a leader clustering algorithm avoids an exhaustive search of the FARG database. We quantify the retrieval performance of the system in terms of several standard measures.     

Retrieving 2D shapes using caterpillar decomposition

Graphs provide effective data structures modeling complex relations and schemaless data such as images, XML documents, circuits, compounds, and proteins. Given a query graph, finding sufficiently similar database graphs without performing a sequential search is an important problem arising in different domains. In this paper, we propose a new method for indexing tree structures based on a graph-theoretic concept called caterpillar decomposition. Our algorithm starts by representing each tree along with its subtrees in the geometric space using its caterpillar decomposition. After representing the query in the same fashion, similar database trees are retrieved efficiently by means of nearest neighbor searches. We have successfully evaluated the proposed algorithm on two shape databases and include a set of perturbation experiments that establish the algorithm’s robustness to noise. We have also shown that the approach compares favorably to previous approaches for shape retrieval on these datasets.     

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.     

M+树:一种新型、高效的动态哈希算法

通常哈希函数只支持等值查找，这给哈希函数的应用带来了很大的限制。该文提出了一种新型的哈希索引算法——M 树索引。该算法能够支持等值和范围查找，实验表明，该算法无论在查询效率还是可维护性方面都优于同类索引算法。