Crystal

KO | EN

gitlite — search

#javascript #python #hacktoberfest #react #ai #typescript #llm #go #golang #android #machine-learning #rust #deep-learning #linux

★ 11 Open GitHub ↗

Crystal is a novel method for distributed subgraph matching on very large graphs. Crystal outperforms existing methods by several orders of magnitude on very large graphs. The work was published on VLDB 2018 with title "Subgraph matching: on compression and computation".

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

#      Crystal:A very fast distributed subgraph matching algorithm
This project contains the implemetation of the method described in **Subgraph matching: on compression and computation** published in VLDB2018.

##      Patterns
![Pattern](https://raw.githubusercontent.com/H20Zhang/Crystal/master/pattern.jpg)

##      Environment Requirement

[Hadoop 2.7.3](https://hadoop.apache.org).

##      How to use?

#### 1) preprocess datasets (in edge list form) by
run "Preprocess.sh"

#### 2) perform counting
run "CountingTest.sh", which will count subgraph matching for all pattern listed.

#### 3) generate compression form
run "WritingTest.sh", which will dump the the result of subgraph matching for all pattern listed to HDFS

##	Detail Specification
Source Code is in **Subgraph** folder, which can be open by **Intellij Idea**.

In it you can find three packages:

- sAlg
    - Square
    - Chordal Square
    - House 
        - HouseS: for small data graph
        - House:for large data graph
    - Chordal Roof
    - Three Triangle
    - Solar Square
    - Near5Clique
    - QuadTriangle
    - SolarSquarePlus
- sData: data structure used in sAlg
- sPreprocess: Preprocessing Related
    - sCliqueGeneration
        - classes used to generate the crystal
    - sTool
        - preprocessing the graph

Each of the patterns comes with two java class, one for counting, one for outputting(class with name ended with O). More detail please read the code.

###	Test File
Files related to testing is at Top level.

- **Data**: small datasets for testing the algorithm, in which each dataset is attached with a *-pattern-size.txt recording the pattern's size in each graph for each pattern.
- Preprocess.sh: Preprocessing the Data for CountingTest.sh and WritingTest.sh.
- CountingTest.sh: Testing the code related to counting in **Crystal**
- WritingTest.sh: Testing the code related to writing in **Crystal**
- pattern.eps: give a visulization about what pattern looks like

Please run Preprocess.sh first, before running the other two shell script. More detail please read the .sh file, and change some of the variables accordingly in the script file.

###	Parameter 
- mapreduce.job.reduces: better using the same number as vCore in yarn
- mapreduce.reduce.memory.mb: the default is 4000MB, if graph bigger than UK2002 need to be processed, this might need to increase.
- mapreduce.map.memory.mb: the default is 4000MB, if graph bigger than UK2002 need to be processed, this might need to increase.
- test.memory: same as mapreduce.map.memory.mb. But only available in sAlg.
- bloomHash: controlling hash function used in Bloom filter
- bloomBit: controlling numbers of bit for representing a record in Bloom filter
- test.p
    - test.p (for classes in sIntersection): controlling the number of the round for the algorithm, the lower the better (if memory permit)
    - test.p (for classes in sPartition)L controlling the number of partitions for the algorithm, the lower the better (if memory permit)
- test.isOutput: specify whether the result should be outputted in *O.class.
- test.isEnumerating: whether just counting or enumerating.

###	Format
- InputFormat: Edge List
- OutputFormat: file format specified in the paper.

```
    //Below three configuration is commented for maximum compatibility for the different version of Hadoop, if possible, they should be uncommented to improve the performance and compression ratio.
    
    //These configurations can be found in the source code.
    
    SequenceFileOutputFormat.setOutputCompressionType(job, CompressionType.BLOCK);
    
    FileOutputFormat.setCompressOutput(job, true);
    
    FileOutputFormat.setOutputCompressorClass(job, SnappyCodec.class);
```

###	Core-Crystal Decomposition

The pattern decomposition aims at optimzing Objective 3 in the paper.

This package provides decomposition.cpp which decomposes the pattern graph with/without the statistics of the cliques.

input specification 
Input the pattern graph to pattern.txt.  
	first line : 
		n m b
			n: # of nodes, m: # of edges. Note that nodes are labeled with [1,n]. 
			b: a boolean value of 0 or 1, specifying that statistics are used (1) or not (0)
	followed by m lines, each line 
		x y 
			describes an undirected edge (x,y)

followed by a line, if b=1,  
		k M
			k: the largest clique with statistics, k should be at least = the largest clique size in the pattern graph
			M: memory size
	followed by k lines, the i-th line specifies 
		the total number of Clique_i in the target graph. Specifically, the first line is the # of nodes in the target graph and the second line is the # of edges in the target

```
Example input 1

4 4 0
1 2
1 3
2 4
3 
```
```
Example input 2
4 4 1
1 2
1 3
2 4
3 4

2 20
100
200
```
Please refer to patternpool.txt for further example

For citatation
```
@article{qiao2017subgraph,
  title={Subgraph matching: on compression and computation},
  author={Qiao, Miao and Zhang, Hao and Cheng, Hong},
  journal={Proceedings of the VLDB Endowment},
  volume={11},
  number={2},
  pages={176--188},
  year={2017},
  publisher={VLDB Endowment}
}
```

### contact me at [hzhang@se.cuhk.edu.hk](hzhang@se.cuhk.edu.hk)

Crystal

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README