BAG C++ METIS-RB Experiment

This directory contains a standalone C++ experimental line for BAG-style range and kNN queries on road networks.

The code in this directory focuses on:

• loading .gr road-network files
• importing external METIS-style partition assignments
• building the corresponding skeleton index
• running range and kNN query smoke tests / batch runs

Quick start

1. Build

Use CMake with a Release build:

cmake -S . -B build-metis -DCMAKE_BUILD_TYPE=Release
cmake --build build-metis --config Release

The executable will be generated at:

build-metis\Release\bag_cpp.exe

2. Run the built-in default experiment

This runs the built-in METIS-based default experiment with fixed internal settings and no query-point arguments:

build-metis\Release\bag_cpp.exe default

The default profile currently uses an internal NY graph / assignment / query configuration baked into the executable.

3. Run a partition-only probe

This command imports a pre-generated METIS assignment and prints partition / skeleton statistics:

build-metis\Release\bag_cpp.exe partition `
  --path <graph.gr> `
  --metis-assignment <assignment.csv> `
  --theta <theta>

4. Run a single-query probe

This command builds the index once and runs both range and kNN on one query point:

build-metis\Release\bag_cpp.exe probe `
  --path <graph.gr> `
  --metis-assignment <assignment.csv> `
  --theta <theta> `
  --query-u <u> `
  --query-v <v> `
  --offset <offset> `
  --objects <object_count> `
  --object-seed <seed> `
  --range-radius <radius> `
  --knn-k <k> `
  --repeat <times> `
  --fc-rule <rule>

5. Run a pure batch benchmark

This command builds the index once, then runs a batch of random range and kNN queries:

build-metis\Release\bag_cpp.exe batch `
  --path <graph.gr> `
  --metis-assignment <assignment.csv> `
  --theta <theta> `
  --query-count <count> `
  --query-seed <seed> `
  --objects <object_count> `
  --object-seed <seed> `
  --range-radius <radius> `
  --knn-k <k> `
  --fc-rule <rule>

Input files

Typical inputs are:

• graph: a DIMACS-style .gr road-network file
• assignment: a CSV file that provides one partition id per vertex

Source layout

• src/main.cpp: CLI entry
• src/metis_partition.*: METIS assignment import and partition reconstruction
• src/index.*: skeleton index build and query processing
• src/object.*: moving-object generation and storage
• src/distance.*: shortest-path utilities

Notes

• This directory is an experiment line and is intended for code study and reproducible local runs.
• Build artifacts under build/ and build-metis/ are ignored by git.