Contact Project Developer Ashish D. Tiwari [astiwz@gmail.com]
Download Synopsis Abstract
Desktop Applications Java JSP BE-Engineering(CO/IT) ME-Engineering(CO/IT) BCS MCS BCA MCA MCM BSC Computer/IT MSC Computer/IT Diploma (CO/IT) IEEE-2015

Fast Best-Effort Pattern Matching in Large Attributed Graphs

We focus on large graphs where nodes have attributes, such as asocial network where the nodes are labelled with each person’s job title. In such a setting, we want to find sub grap
Abstract-Synopsis-Documentation

Fast Best-Effort Pattern Matching in Large Attributed Graphs

ABSTRCT

We focus on large graphs where nodes have attributes, such as asocial network where the nodes are labelled with each person’s job title. In such a setting, we want to find sub graphs that match a user query pattern. For example, a ‘star’ query would be, “find a CEO who has strong interactions with a Manager, a Lawyer, and an Accountant, or another structure as close to that as possible”. Similarly, a ‘loop’ query could help spot a money laundering ring Traditional SQL-based methods, as well as more recent graph indexing methods, will return no answer when an exact match does not exist. Our method can find exact-, as well as near-matches, and it will present them to the user in our proposed ‘goodness’ order. For example, our method tolerates indirect paths between, say, the‘CEO’ and the ‘Accountant’ of the above sample query, when direct paths do not exist. Its second feature is scalability. In general, if the query has nq nodes and the data graph has n nodes, the problem needs polynomial time complexity O(nnq ), which is prohibitive. Our G-Ray (“Graph X-Ray”) method finds high-quality sub graphs in time linear on the size of the data graph.

EXISTING SYSTEM

Given a large graph with attributed nodes, how can we quickly find patterns that match, say, the ‘star’ query of the abstract? And what should we do when no exact instance of the specified pattern exists? Here, we give the formal problem definition. To start with, we assume that only the nodes in a data graph have categorical attributes. We shall use a running example of the fictitious social network of Figure 1, where nodes indicate people, the (weighted )edges indicate volume of communication



PROPOSED SYSTEM

We propose Graph X-Ray (G-Ray), a fast method that finds sub graphs that either match the desirable query pattern exactly, or as well as possible. We propose an intuitive goodness score g() to measure how well a sub graph matches the query pattern, and we give a fast algorithm to find and rank qualifying sub graphs. The idea of best-effort is illustrated by an example. Figure 2(a) shows a‘line’ query on the fictitious graph of Figure 1. Since no instance of the query exists, our system returns a ‘best-effort’ match, as shown in Figure 2(b). Traditional SQL-based methods, as well as more recent graph indexing methods, will return no answer when an exact instance of a pattern does not exist.


Comment is Only Available for registered users! Create Account or Login Now!