Skip to content
Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together
Branch: master
Clone or download
Pull request Compare This branch is 26 commits behind SNUCSE-CTA:master.
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
README.md
compile.sh
daf_1min
daf_1min.exe
dag.cpp
dag.h
main.cpp
sort_result.py

README.md

DAF [SIGMOD 2019]

Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together

Compile

To compile the query DAG construction program:

  • Linux: type ./compile.sh or g++ -std=c++11 main.cpp dag.cpp -o program

Binary files of DAF are available

  • Linux: daf_1min
  • Windows: daf_1min.exe

Run

To run the query DAG construction program:

Usage: ./program datagraphFile querygraphFile #queries > outputFile
Example: ./program human human_10n 100 > human_10n.dag

To run DAF (time limit is set to 60 sec and #matches is set to 100,000)

Usages:

./daf_1min -d datagraphFile -q querygraphFile -a dagFile -n #queries // with input dagFile
or
./daf_1min -d datagraphFile -q querygraphFile -n # queries // query DAG is constructed by DAF
Examples:

./daf_1min -d human -q human_10n -a human_10n.dag -n 100
./daf_1min -d human -q human_10n -n 100

Compare Results

To evaluate two results for a query set, use sort_result.py script as follows.

./daf_1min -d human -q human_10n -a human_10n.dag -n 100 > result1
./daf_1min -d human -q human_10n -n 100 > result2
python sort_result.py result1 result2
You can’t perform that action at this time.