Efficient Graph Isomorphism Query Processing using Degree Sequences and Color-Label Distributions
Options:
-m, specify the mode
-f, specify the file containing data graphs
-q, specify the file containing query graphs
To run the program for graph isomorphism query processing:
./DCQ -m all -f [data file] -q [query file]
To compute the average false positive ratio of each technique used in our index:
./DCQ -m filter -f [data file] -q [query file]
./DCQ -m all -f data/amazon_D4000_d2.igraph -q query/amazon_d2.igraph
./scripts/run_amazon.sh //a batch script for amazon
./scripts/run_hprd.sh //a batch script for HPRD
DCQ outputs indexing time and query processing time in milliseconds, and the answer file for a set of data graphs and a query set (answer.txt).
Each line of the answer file is as follows.
[query ID]: [data graph ID] [data graph ID] ...
The file format is a text format to store an undirected graph. A file contans a set of data graphs (or a set of query graphs).
- The first line of the file should be "t ID #vertices" which means the start of a graph with graph id=ID
- Following lines of "v [vertex ID] [vertex label]" indicate the vertices in the graph.
- The vertices should be written in the file in ascending order of their IDs, and a vertex ID should be in range [0, #vertices - 1].
- Following lines of "e [vertex ID] [vertex ID] 0" after the vertices indicate the undirected edges in the graph.
For example:
Line "t 1 3112" means that the start of a graph with ID=1 and #vertices=3112.
Line "v 0 1" means that there is a vertex with ID=0 and vertex-label=1 in the graph.
Line "e 1 133 0" means that there is an undirected edge between vertices with IDs 1 and 133.
This project is provided under the Apache License 2.0.