Browse Prior Art Database

Using Pattern Matching Accelerator to Solve Popular Problem in Graph Disclosure Number: IPCOM000196572D
Publication Date: 2010-Jun-07
Document File: 3 page(s) / 78K

Publishing Venue

The Prior Art Database


Graph theory are used by many applications and one of the most important metric is clustering coefficient . Pattern matching engine has been implemented by many processor vendors. In this articile, we propose to use pattern matching engine to do the clustering coefficient computation. First, the graph is transformed into regular experssion and send to the pattern matching engine. Second, every computation request is converted into to the language of pattern matching engine. Last but the most important, the proposed transformation technologies can improve the performance largely.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 56% of the total text.

Page 1 of 3

Using Pattern Matching Accelerator to Solve Popular Problem in Graph

In graph theory, clustering coefficient is a measure of degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-


networks, and in particular social networks, nodes tend to create tightly knit groups characterized by a relatively high density of ties.

Short messaging is a popular service provided by cell phone companies worldwide. With the share increase in the number of mobile phone users, in particular, in emerging economies such as China, spamming has become a concern for service providers and users alike. [1] proposed to use clustering coefficient to distinguish spam from regular messages. The computation of clustering coefficient should be fast enough to guarantee the arrival of non-spam messages.

Beside that, clustering coefficient is always used as a measurement of node clustering in P2P environment, because node clustering is an efficient way to improve query hit radio and decreases network traffic cost in unstructured P2P topology [2].

Current methodlogy to compute clustering coefficient has a complexity of O(N*N) (N is the number of nodes). We claim using pattern matching accelerator to perform the computation, further more, efficient encoding techonlogies in pattern matching to decrease the complexity.

[1] P.O.Boykin and V.P.Roychowdhury. Leveraging social networks to fight spam. Computer, 38(4):61-68, 2005.
[2] ZHANG Ke,HUANG Yong-feng,LI Xing. Distribution Character Research of Node'S Clustering Coefi cient in P2P Network. Journal of Xia Men University, 46(2):226-228, 2007.

In a graph, clustering coefficient of a vertex quantifies how close its neighbors are to being a clique. A graph G = (

V, E) formally

consists of a set of vertices V

and a set of edges E between them. An edge eij connects vertex I with vertex j. The neighborhood N for a vertex vi is defined as its immediately connected neighbors as follows:

The clustering coefficient for directed graph is given as

Problem: Input:


v , Neigh...