ASDMatch

Compile

1. Compile and link to the glpk library. The glpk library is used to compute fractional hypertree decomposition.

cd utility/td/glpk-4.55
./configure -prefix={ABSOLUTE_PATH_TO_GLPK_LIB} # relative path: ../glpk_lib
make -j
make install
cd .. # at the 'td' directory

2. Build the project.

mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make

Input format

We use the same format as in RapidMatch.

Both the input query graph and data graph are vertex-labeled. Each graph starts with 't N M' where N is the number of vertices and M is the number of edges. A vertex and an edge are formatted as 'v VertexID LabelId Degree' and 'e VertexId VertexId' respectively. Note that we require that the vertex id is started from 0 and the range is [0,N - 1] where V is the vertex set. The following is an input sample.

Example:

t 5 6
v 0 0 2
v 1 1 3
v 2 2 3
v 3 1 2
v 4 2 2
e 0 1
e 0 2
e 1 2
e 1 3
e 2 4
e 3 4

Execution and output

ASDMatch.out:

Option	Description
-q	the query graph path
-d	the data graph path
-s	the cardinalities used in query optimizer (optional)
-m	the memory budget by KB (optional). The default value is 16GB
-r	the result path (optional)
-t	query-processing time limit in seconds; fractional seconds are accepted (optional, default: 0 = unlimited)
-n	maximum number of full-query matches, not intermediate tuples (optional, default: 0 = unlimited)

Example:

./ASDMatch.out -q ../dataset/yeast/query_graph/query_8_1.graph -d ../dataset/yeast/data_graph/yeast.graph -s ../dataset/yeast/query_graph/query_8_1.card -r ../result.txt

For example, stop after 300 seconds or 100 million matches, whichever comes first:

./ASDMatch.out -q query.graph -d data.graph -t 300 -n 100000000

The time limit starts after loading the input graphs and covers candidate-space construction, filtering, planning/cardinality estimation, and execution. Checks are cooperative: an ongoing library call (such as GLPK), allocation, or cleanup may finish after the deadline; this is not a hard process wall-clock limit. On either limit, the program exits normally, retains partial results, and prints a short diagnostic to stderr. Existing stdout statistics and result-file format are unchanged; Number of matches never exceeds a positive -n limit. The match limit does not apply to cardinality samples or materialized bag tuples. Omitting both options preserves unlimited execution. Negative, malformed, and out-of-range values are rejected. -n accepts integers up to SIZE_MAX. With LOCAL_COUNT, counts describe only the matches processed before stopping; with COLLECT_RESULT, only those matches are written to the result file.

We can also use 'prepare.out' to precompute cardinalities.

./prepare.out -q {query_graph_path} -d {data_graph_path} -s {card_result_path}

Local subgraph counting

We support local subgraph counting. First, define some MACRO in the config.h:

#define ALL_LEVEL
#define LOCAL_COUNT

Next, recomplie the project.

For execution, add the '-c {path_to_local_count_output}' parameter. The local count output is a csv file that has $|V_g|$ rows and $|V_q|$ columns, where each row is the local subgraph count of a data graph node for every query graph node.

Limit regression tests

The CLI tests generate their own small graphs and require only Python's standard library. Run them against the build configuration being tested:

python tests/test_limits.py /absolute/path/to/ASDMatch.out
# For COLLECT_RESULT builds, add --mode collect.
# For ALL_LEVEL + LOCAL_COUNT builds, add --mode local.
c++ -std=c++17 -pthread -I utility tests/runtime_control_test.cpp -o /tmp/asdmatch-runtime-test
/tmp/asdmatch-runtime-test