This code package implements the routines described in the paper
"Space efficient mining of multigraph streams" by G. Cormode and S. Muthukrishnan. 
In Proceedings of ACM Principles of Database Systems, 2005.

The makefile generates two output files, graphd and graphf.  graphd
is used to estimate the nodes of high degree in a multigraph, and
graphf estimates the second frequency moment (F2) of multigraphs.
Both these are defined in the referenced paper. 


Program 1: graphd
=================

graphd is used to estimate the nodes of high degree in a multigraph.

graphd takes six parameters on the command line:
graphd N Z W D FM file

N denotes the number of items to process
Z denotes the parameter of a zipfian distribution to generate data from: this can range from 0.0 to 4.0.  Typical data displays skew of around 1.2 to 1.6.  
W denotes the width of the CM sketch summary to use.  A default value is 200.  Increasing this will bring increased accuracy. 
D denotes the depth of the CM sketch summary to use.  A default value is 5. Increasing this will give greater confidence. 
FM denotes the size of the FM sketch summary to use.  A default value is 10.  Increasing this will also increase accuracy. 
Note that the total space used by the summary is W*D*FM
file is a data file to read in.  The file is expected to be a binary file consisting of HOLDER records: these are defined in graph.c as struct holder {
  unsigned long source;
  unsigned long dest;
  unsigned long time;
};
source is the source of the (directed) edge, dest is the destination
of the directed edge, and time is an optional extra field to hold the
weight of the edge (this is not used by this code). 

If file is present, then N and Z will be ignored and the file data
will be used; if file is not present, then synthetic data will be
generated from the given zipf distribution. 



An example of running graphd is as follows: 

graphd 10000 1.2 250 5 10 

This generates the following output: 

graph.c compiled at 10:15:54, Dec 14 2005
#items  CMFMerr CMFMspc CMFM t  MH err  MH spc  MH t    LCFMerr LCFMspc LCFM t   Null
10000   0.16256 175072  39      0.02826 125004  1904    0.09930 104460  47      0.57290

This indicates that 10000 edges were processed.  The error from using CMFM was 16% over 
all nodes.  Error is calculated as (sum_i=1^20 |d^_i - d_i|)/n, where d^_i is the estimated
degree of node i, and d_i is the true degree of node i, taken over the
nodes with the 20 highest degrees.  The space used by the CMFM
approach is 175072 bytes, and the processing took 39 milliseconds. 

The minwise hashing approach obtained error 2%, using 125KB in
1.9seconds.  The LCFM method achieved accuracy 9.9% using 104KB and 47ms.  
Null indicates the error obtained by using d^_i = 0 for all i.  This
gives error 57% indicating that all three methods have obtained a
significant improvement over a trivial approach. 


An example file lblsourcedest is included.  It is generated from the
LBL-7 data set obtained from the open source Internet Traffic
archive (http://ita.ee.lbl.gov/html/contrib/LBL-CONN-7.html)

It has been converted to the required format for this program. 
LBL-7 has 1650 uniq sources, 35,000 uniq source,address pairs

Here is a sample invocation:

$ graphd 1 0 250 5 10 lblsourcedest
graph.c compiled at 10:15:54, Dec 14 2005
About to read file of length 427944 with 35662 records
Read 35662 items
#items  CMFMerr CMFMspc CMFM t  MH err  MH spc  MH t    LCFMerr LCFMspc LCFM t   Null
35662   0.09100 175072  212     0.02105 125004  6934    0.06356 86524   86      0.42564

The file contains 35662 edges, and obtains the above noted results.  They can be parsed in the same way as the previous results. 

Program 2: graphf
=================

graphf is very similar in operation to graphd.  It estimates F2 of a (multi)graph.

graphf takes six parameters on the command line:
graphf N Z W D FM file

These are the same as for graphd:
N denotes the number of items to process
Z denotes the parameter of a zipfian distribution to generate data from: this can range from 0.0 to 4.0.  Typical data displays skew of around 1.2 to 1.6.  
W denotes the width of the CM sketch summary to use.  A default value is 200.  Increasing this will bring increased accuracy. 
D denotes the depth of the CM sketch summary to use.  A default value is 5. Increasing this will give greater confidence. 
FM denotes the size of the FM sketch summary to use.  A default value is 10.  Increasing this will also increase accuracy. 
Note that the total space used by the summary is W*D*FM
file is a data file to read in.  The file is expected to be a binary file consisting of HOLDER records: these are defined in graph.c as struct holder {
  unsigned long source;
  unsigned long dest;
  unsigned long time;
};
source is the source of the (directed) edge, dest is the destination
of the directed edge, and time is an optional extra field to hold the
weight of the edge (this is not used by this code). 
If file is present, then N and Z will be ignored and the file data
will be used; if file is not present, then synthetic data will be
generated from the given zipf distribution. 



An example of running graphf is as follows: 

 graphf 10000 1.2 250 5 10 

This generates the following output: 

graph.c compiled at 10:15:56, Dec 14 2005
#items  AMS err AMS spc AMS t   MH err  MHapp   MH spc  MH t
10000   0.30761 175072  49      0.07929 0.08014 190040  680

This indicates that 10000 edges were processed.  

The error from using the AMS based heuristic is 30%, where the error is computed as 
the true value minus the estimated value divided by the true value.
The time taken was 49ms, and the space used was 175072 bytes. 
The minwise-hash based approach achieved 7.9% error using the correct
estimation method, and 8% error using the alternate estimation method.
The space used was 190KB, and the time taken was 680ms. 


A sample invocation using a stored file is as follows 

$ graphf 1 0 250 5 10 lblsourcedest

About to read file of length 427944 with 35662 records
Read 35662 items
#items  AMS err AMS spc AMS t   MH err  MHapp   MH spc  MH t
35662   0.08718 175072  124     0.02336 0.02311 190040  2599

The file contains 35662 edges, and obtains the above noted results.
They can be parsed in the same way as the previous results. 

Graham Cormode, December 2005
graham@dimacs.rutgers.edu
