BAG Index: A Bound-Aware Graph Partitioned Index

This repository contains an implementation of the algorithms presented in the paper: "BAG: A Bound-Aware Graph Partitioned Index for Spatial Queries over Moving Objects on Road Networks."

The project provides the necessary data structures and algorithms for partitioning a large road network graph, building a skeleton index, and efficiently processing spatial queries like range and k-Nearest Neighbor (k-NN) queries for objects moving on that network.

Background

Querying moving objects on large-scale road networks is a fundamental challenge in spatial databases and location-based services. The BAG-Index approach addresses this by partitioning the main graph into smaller, manageable subgraphs. It then constructs a high-level "skeleton graph" consisting only of the boundary vertices between these subgraphs. This hierarchical structure allows queries to be pruned efficiently, significantly speeding up search operations by minimizing the traversal of the full, detailed graph.

This implementation focuses on the core contributions of the paper, including the VFIP partitioning algorithm and the BAG-kNN query processing algorithm.

Features

• Graph Data Structures: Efficient representation of large road networks (graph.rs).
• Graph Partitioning: An implementation of the Vertex First Insertion Partitioning (VFIP) algorithm to divide the graph into subgraphs while respecting the Bound-Restriction (BR) property (partition.rs).
• Skeleton Graph Index: Construction of the skeleton graph from the partitioned subgraphs (index.rs).
• Range Query: Implementation of the Graph-Coverage-Computation (GCC) algorithm for range queries (index.rs).
• k-NN Query: An implementation of the BAG-kNN algorithm for finding the k-nearest neighbors to a query point (knn.rs).

Getting Started

Prerequisites

• Rust programming language toolchain (latest stable version recommended). You can install it from rustup.rs.
• A Unix-like environment (Linux, macOS, WSL) is recommended for ease of use.

Data Source

The project is designed to work with road network data from the 9th DIMACS Implementation Challenge on Shortest Paths.

1. Download the data: You can obtain the graph data from the official website: https://www.diag.uniroma1.it//challenge9/competition.shtml. The datasets are typically provided as .gr files (e.g., USA-road-d.NY.gr).
2. Organize the data: Create a dataset/ directory in the root of this project and place the downloaded .gr files inside it.

The project will automatically create a cached, serialized version of the graph in a subdirectory (e.g., dataset/USA-road-d.NY/) for much faster loading on subsequent runs. Moving object sets (.mos files) can be generated automatically by the benchmark binaries.

Building the Project

Clone the repository and build the project in release mode for optimal performance:

git clone https://anonymous.4open.science/r/bap-public-8437 bag
cd bag
cargo build --release

Running the Benchmarks

The primary executables for benchmarking are located in the bin/ directory. You can run them using cargo run.

1. Benchmarking Graph Partitioning

The partition binary measures the time and results of the VFIP partitioning algorithm.

Usage:

cargo run --release --bin partition -- --path <PATH_TO_GRAPH> --theta <THETA>

Arguments:

• --path: The path to the graph .gr file.
• --theta: The maximum number of vertices per subgraph.

Example:

cargo run --release --bin partition -- --path dataset/USA-road-d.NY.gr --theta 30

This will run the VFIP algorithm on the New York dataset with a theta of 30 and output the results in JSON format, including execution time, number of subgraphs, average subgraph size, and skeleton graph size.

2. Running a Range Query

The run_init_rs binary demonstrates and times a single range query. It partitions the graph, builds the index, and executes the query for a predefined set of parameters.

Usage:

To run the binary, simply execute:

cargo run --release --bin run_init_rs

Configuration:

Unlike the other benchmarks, the parameters for this query are hardcoded within the main function of the src/bin/run_init_rs.rs file. To change the dataset, query point, radius, or other settings, you must edit this file.

Key parameters to modify in src/bin/run_init_rs.rs:

fn main() {
    // 1. Change the dataset path
    let path = "../dataset/USA-road-d.FLA.gr";

    // 2. Define the query point (on an edge between two vertices with a given offset)
    let v_q = MovingObject::new(0, (1, 2), 1);

    // 3. Set the parameters for the run_algorithm function
    run_algorithm(
        path,
        800000, // Number of moving objects to generate
        30,     // Theta: max vertices per subgraph
        v_q,    // The query point defined above
        1293 * 30 // The query radius
    );
}

3. Benchmarking k-NN Queries

The knn binary allows you to test the performance of the BAG-kNN algorithm by varying either the number of neighbors (k) or the subgraph size parameter (theta, referred to as z in the runner).

Usage:

cargo run --release --bin knn -- <DATASET> <TEST_TYPE>

Arguments:

• <DATASET>: The name of the dataset to use. Must be one of: NY, FLA, CAL, E, CTR.
• <TEST_TYPE>: The type of test to run.
  • k: Fixes theta (z) and tests with varying k values.
  • z: Fixes k and tests with varying theta (z) values.

Examples:

• To test k-NN performance on the New York dataset with a fixed theta and varying k:

  cargo run --release --bin knn -- NY k

• To test k-NN performance on the Florida dataset with a fixed k and varying theta:

  cargo run --release --bin knn -- FLA z