Sub trajectory Proximity Queries - japfeifer/frechet-queries GitHub Wiki

This page contains details on our Sub-trajectory Proximity search work. Our work is published in the SIGSPATIAL21 conference and can be accessed here, as well as in the Journal ACM Transactions on Spatial Algorithms and Systems and can be accessed here.

Data Sets

Real and synthetic datasets were used to test our contribution. For real data sets, we pre-processed them into different input trajectory P sizes, from |P|=500 up to |P|=1,000,000. To run our HST construction and Query experiments, you only need the Matlab data files with the pre-processed input trajectories P. Click here to download the Matlab HST data files, and here to download the Matlab CCT files for the Baseline 3 experiments.

Experiments

Experiments are run by executing Process*.m script files, which are located in the Process folder.

CCT Construction Experiments on smaller input P sizes:

  • ProcessHSTCCTConst.m
  • ProcessHSTCCTConst_Football2500.m
  • ProcessHSTCCTConst_P500.m
  • ProcessHSTCCTConst_Pigeon2500.m

HST Construction Experiments:

  • ProcessHSTConstHalfRadius.m
  • ProcessHSTConstHalfRadiusMeth2.m
  • ProcessHSTConstHalfRadiusMeth3_other.m
  • ProcessHSTConstHalfRadiusMeth3_P500.m
  • ProcessHSTConstHalfRadiusMeth3.m
  • ProcessHSTConstHalfRadiusMeth3Taxi.m

Baseline 1 Algorithm Experiments:

  • ProcessHSTQueryBase1_others.m
  • ProcessHSTQueryBase1_pt2.m
  • ProcessHSTQueryBase1.m

Baseline 2 Algorithm Experiments:

  • ProcessHSTQueryBase2TwoApprox.m
  • ProcessHSTQueryBase2TwoApprox_others.m
  • ProcessHSTQueryBase2TwoApprox_P500.m
  • ProcessHSTQueryBase2TwoApprox_pt2.m
  • ProcessHSTQueryBase2TwoApproxTaxi.m

Baseline 3 Algorithm Experiments:

  • ProcessHSTQueryBase3_P500.m
  • ProcessHSTQueryBase3.m

New Proposed Algorithm 1 Experiments:

  • ProcessHSTQueryAlgo1_others.m
  • ProcessHSTQueryAlgo1.m

New Proposed Algorithm 2 Experiments:

  • ProcessHSTQueryAlgo2_others.m
  • ProcessHSTQueryAlgo2_pt2.m
  • ProcessHSTQueryAlgo2.m

New Proposed Algorithm 3 Experiments:

  • ProcessHSTQueryAlgo3_others.m
  • ProcessHSTQueryAlgo3Meth3Taxi.m
  • ProcessHSTQueryAlgo3Meth3Taxi_apx.m
  • ProcessHSTQueryAlgo3TwoApprox.m

|P|=500 Query Experiments:

  • ProcessHSTQueryMeth3_P500.m