Search

Graph indexing is one of the budding dominant current research domains. Varieties of data from different domains pop into the daily updating world in huge volume. There are plenty ways to analyze and to arrange them into an easily accessible index. Here in this paper, we concentrate on the graphical approach. The complete classical algorithms of graph indexing are discussed initially followed by the latest proposed solving methods. Alas, at the end of the paper a complete PLANO frame work is proposed such that the given data can be easily indexed and the updated features can be propelled onto the index.

Graphs are ubiquitous and play an essential role in modeling and representing complex structures in real-world networked applications. Given a graph database that comprises a large collection of graphs, it is fundamental and critical to enable fast and flexible search for structurally similar graphs. In this paper, we survey recent graph similarity search techniques and specifically focus on the work based on the graph edit distance (GED) metric. State-of-the-art approaches for the GED based similarity search typically adopt a pruning and verification framework. They first take advantage of some easy-to-compute lower-bounds of graph edit distance, and use novel graph indexing structures to efficiently evaluate such lower-bounds between graphs in the graph database and the query graph. This way, graphs that violate the GED lower-bound constraints can be identified and filtered from the graph database from further investigation. Then, the costly GED verification is performed only for the graphs that pass the GED lower-bound evaluation. We examine existing GED lower-bounds, graph index structures, and similarity search algorithms in detail, and compare different similarity search methods from multiple aspects including index construction cost, similarity search performance, and applicability in real-world graph databases. In the end, we envision and discuss the future research directions related to similarity search and high-performance query processing in large-scale graph databases.

This paper proposes the GraphF abstraction which exploits Adaptive Radix Tree for efficient graph indexing with lower storage cost. Leveraging the GraphF abstraction, we implement a separate graph computation engine on Spark. Experiments showed that on average GraphF outperforms GraphX and PowerGraph by up to 8.1X and 3.6X separately in execution time both for real world and for synthetic graphs. Moreover, GraphF is remarkably more efficient than GraphX in memory storage cost and saves up to sevenfold of space consumption.

Ontology offers rich properties to describe knowledge in information systems. However, ontologies in knowledge-based systems usually suffer from semantic heterogeneities due to distributed developers. Ontology matching is a key solution to the heterogeneity problem in knowledge management. Though state-of-the-art ontology matching systems are able to support diverse ontology matching tasks, the semantic heterogeneity in ontology matching is still the main challenge. In this paper, we propose an element and graph combined matching framework to specifically deal with semantic heterogeneity during ontology matching. Moreover, we also develop an automated ontology matching system and evaluate the system in diverse ontology matching tasks. By using the graph indexing technique, the matching system is scalable with large ontology matching. The experimental results show that the proposed system achieves a good result in highly heterogeneous matching tasks and a comparable result in large ontology matching tasks.

We present GeX for the approximate matching of complex queries on graph-modeled data.GeX generalizes existing approaches and allows for querying any graph-based datasets.GeX query language supports queries ranging from keyword-based to complex ones.GeX query answering model delivers meaningfully approximated results only.GeX implements data structures and algorithms to efficiently support query answering. We present the GeX (Graph-eXplorer) approach for the approximate matching of complex queries on graph-modeled data. GeX generalizes existing approaches and provides for a highly expressive graph-based query language that supports queries ranging from keyword-based to structured ones. The GeX query answering model gracefully blends label approximation with structural relaxation, under the primary objective of delivering meaningfully approximated results only. GeX implements ad-hoc data structures that are exploited by a top-k retrieval algorithm which enhances the approximate matching of complex queries. An extensive experimental evaluation on real world datasets demonstrates the efficiency of the GeX query answering.

Temporal graphs represent vertexes and binary relations that change over time. In this paper we consider a temporal graph as a set of 4-tuples ( v s , v e , t s , t e ) indicating that an edge from a vertex v s to a vertex v e is active during the time interval [t s , t e ). Representing those tuples involves the challenge of not only saving space but also of efficient query processing. Queries of interest for these graphs are both direct and reverse neighbors constrained by a time instant or a time interval. We show how to adapt a Compressed Suffix Array (CSA) to represent temporal graphs. The proposed structure, called Temporal Graph CSA (TGCSA), was experimentally compared with a compact data structure based on compressed inverted lists, which can be considered as a fair baseline in the state of the art. Our experimental results are promising. TGCSA obtains a good space-time trade-off, owns wider expressive capabilities than other alternatives, obtains reasonable space usage, and it is efficient even when performing the most complex temporal queries.

We present RDF-4G, the first three miles towards a large-scale graph-analytics engine built on top of the state-of-the-art RDF engine, RDF-3X. The algorithmic building blocks that make up this work help answering fundamental questions about relationships between entities in a graph-structured world. More precisely, our system provides insights into what we define as the trilogy of relationship analyis: Is there a relationship between entities? Who participates in the connection? How can the relationship be characterized? While the first two questions correspond to the algorithmic primitives of graph processing, reachability and shortest path queries, for answering the third question we propose a novel graph-theoretic concept, relatedness cores. The technical contributions we make in this work are efficient index structures for reachability and shortest path query processing together with a new notion of and algorithms for relationship characterization. The latter can be efficiently computed based on the techniques we have developed in our work on graph indexing. All our methods are integrated into the RDF-3X engine, the state-of-the-art system for querying RDF-structured data. Future work includes the exposure of our algorithmic building blocks to the user, via extensions to the de-facto standard query language for graph-structured data, SPARQL.

In this paper, we propose a scalable and highly efficient index structure for the reachability problem over graphs. We build on the well-known node interval labeling scheme where the set of vertices reachable from a particular node is compactly encoded as a collection of node identifier ranges. We impose an explicit bound on the size of the index and flexibly assign approximate reachability ranges to nodes of the graph such that the number of index probes to answer a query is minimized. The resulting tunable index structure generates a better range labeling if the space budget is increased, thus providing a direct control over the trade off between index size and the query processing performance. By using a fast recursive querying method in conjunction with our index structure, we show that, in practice, reachability queries can be answered in the order of microseconds on an off-the-shelf computer - even for the case of massive-scale real world graphs. Our claims are supported by an extensive set of experimental results using a multitude of benchmark and real-world web-scale graph datasets.

Subgraph search in graph datasets is an important problem with numerous applications. Many feature-based indexing methods have been proposed for solving this problem. These methods have to index too many features or select some of them in order to get an index with good pruning capabilities. None of these directions can give an effective solution to all graph indexing issues. In this paper, we propose an efficient indexing approach which improves over current feature-based methods, neither by the costly feature selection nor by explicitly indexing a multitude of features. We achieve this by compressing multiple features into one feature with some neighborhood information encoded. Neighborhood is further used to prune unmatched feature occurrences between the query and data graphs, thus cutting down the search space of subgraph matching, which significantly reduce the verification cost. We implement the approach by exhaustively enumerating small paths as features. A novel path-at-a-time verification method that benefits from the occurrences pruning method is introduced. Via an extensive evaluation on both real and synthetic datasets, we show that our approach is effective and scalable, and outperforms state-of-the-art indexing methods.

Recently, there has been a lot of interest in the application of graphs in different domains. Graphs have been widely used for data modeling in different application domains such as: chemical compounds, protein networks, social networks and Semantic Web. Given a query graph, the task of retrieving related graphs as a result of the query from a large graph database is a key issue in any graph-based application. This has raised a crucial need for efficient graph indexing and querying techniques. In this chapter, we provide an overview of different techniques for indexing and querying graph databases. An overview of several proposals of graph query language is also given. Finally, we provide a set of guidelines for future research directions.

Graphs provide a powerful way to model complex structures such as chemical compounds, proteins, images, and program dependence. The previous practice for experiments in graph indexing techniques is that the author of a newly proposed technique does not implement existing indexes on his own code base, but instead uses the original authors' binary executables and reports only the wall clock time. However, we observed that this practice may result in several problems [6]. In order to address these problems, we have implemented all representative graph indexing techniques on a common framework called iGraph [6]. In this demonstration we showcase iGraph and its visual tools using several real datasets and their workloads. For selected queries of the workloads, we show several unique features including visual performance analysis.

When answering many reachability queries on a large graph, the principal challenge is to represent the transitive closure of the graph compactly, while still allowing fast membership tests on that transitive closure. Recent attempts to address this problem are complex data structures and algorithms such as Path-Tree and 3-HOP. We propose a simple alternative based on a novel form of bit-vector compression. Our starting point is the observation that when computing the transitive closure, reachable vertices tend to cluster together. We adapt the well-known scheme of word-aligned hybrid compression (WAH) to work more efficiently by introducing word partitions. We prove that the resulting scheme leads to a more compact data structure than its closest competitor, namely interval lists. In extensive and detailed experiments, this is confirmed in practice. We also demonstrate that the new technique can handle much larger graphs than alternative algorithms. © 2011 ACM.

Nowadays, business process reuse is very important and necessary inside large organizations that continually increase their process collections. Therefore, an efficient system to manage and search for concrete and relevant processes is necessary. Here we overcome to this problem proposing business process model retrieval based on a Graph Indexing Method. It takes into account a measure similarity between two graphs and provides a ranking of business process retrieved.

Dataspace applications necessitate the creation of associations among data items over time. For example, once information about people is extracted from sources on the Web, associations among them may emerge as a consequence of different criteria, such as their city of origin or their elected hobbies. In this paper, we advocate a declarative approach to specifying these associations. We propose that each set of associations be defined by an association trail. An association trail is a query-based definition of how items are connected by intensional (i.e., virtual) association edges to other items in the dataspace. We study the problem of processing neighborhood queries over such intensional association graphs. The naive approach to neighborhood query processing over intensional graphs is to materialize the whole graph and then apply previous work on dataspace graph indexing to answer queries. We present in this paper a novel indexing technique, the grouping-compressed index (GCI), that has better worst-case indexing cost than the naive approach. In our experiments, GCI is shown to provide an order of magnitude gain in indexing cost over the naive approach, while remaining competitive in query processing time.

We propose a minimum overlap based hyperspherical region graph indexing structure to achieve fast similarity-based queries for both low and high dimensional datasets. Specifically, we reduce the region overlaps in the graph construction phase by incrementally dividing each saturated hyperspherical region and removing the longest edge of a minimum spanning tree representation of the internal objects. This overlap reduction scheme creates more separated regions, so fewer regions as potential paths are traversed when a query is issued. We also introduce a k-nearest-neighbor search scheme by automatically deciding the search radius to return the required number of nearest neighbors. Our extensive experimental results show the effectiveness of the proposed indexing structure compared with other tree and graph based indexing structures.

This paper presents an algorithm for the computation of the maximum common subgraph (MCS) between two directed, acyclic graphs with attributes. The core of the contribution resides in the modularity of the proposed algorithm which allows different heuristic techniques to be plugged in, depending on the application domain. Implemented heuristics for robust graph matching with respect to graph structural noise are discussed. As example of its effectiveness, the algorithm is applied to the problem of 3D shape similarity evaluation through structural shape descriptors.

Graph has become increasingly important in modelling complicated structures and schemaless data such as proteins, chemical compounds, and XML documents. Given a graph query, it is desirable to retrieve graphs quickly from a large database via graph-based indices. In this paper, we investigate the issues of indexing graphs and propose a novel solution by applying a graph mining technique. Different from the existing path-based methods, our approach, called gIndex, makes use of frequent substructure as the basic indexing feature. Frequent substructures are ideal candidates since they explore the intrinsic characteristics of the data and are relatively stable to database updates. To reduce the size of index structure, two techniques, size-increasing support constraint and discriminative fragments, are introduced. Our performance study shows that gIndex has 10 times smaller index size, but achieves 3--10 times better performance in comparison with a typical path-based method, GraphGrep. The gIndex approach not only provides and elegant solution to the graph indexing problem, but also demonstrates how database indexing and query processing can benefit form data mining, especially frequent pattern mining. Furthermore, the concepts developed here can be applied to indexing sequences, trees, and other complicated structures as well.