Trajectory Proximity Queries - japfeifer/frechet-queries GitHub Wiki

This page contains details on our Trajectory Proximity search work. This work is published in the Journal ACM Transactions on Spatial Algorithms and Systems and can be accessed here.

Data Sets

A large number of real and synthetic datasets were used to test our contribution. There are 16 real-world and over 20 synthetic datasets. For real data sets, we downloaded source files, and then imported them into a standard Matlab format.

To run our experiments, you only need the Matlab data files. For the Relaxed CCT Matlab data files, click here, here, and here. For the Approximate CCT Matlab data files, click here, here, and here. For the Exact CCT Matlab data files, click here, and here.

If you are interested in obtaining the source files, and want to see how we imported them into Matlab, click here.

Experiments

Experiments are run by executing Process*.m script files, which are located in the Process folder. In the code, CCT1 = Relaxed CCT, CCT2 = Approximate CCT, and CCT3 = Exact CCT.

CCT Construction Experiments:

• ProcessConstCCT1Real.m
• ProcessConstCCT1RealTaxi.m
• ProcessConstCCT1Syn.m
• ProcessConstCCT1SynOneMillion.m
• ProcessConstCCT1SynTenMillion.m
• ProcessConstCCT2Real.m
• ProcessConstCCT2Syn.m
• ProcessConstCCT2SynTenMillion.m
• ProcessConstCCT3Real.m
• ProcessConstCCT3Synthetic.m

M-tree Construction Experiments:

• ProcessConstMtreeReal.m

Insert Experiments:

• ProcessInsertExactCompNoWeightReal.m
• ProcessInsertExactGreedyDepthReal.m
• ProcessInsertExactParentNodeOverlapReal.m
• ProcessInsertExactReal.m
• ProcessInsertExactSyn.m
• ProcessInsertExactTrajOverlapReal.m
• ProcessInsertImplicitCompNoWeightReal.m
• ProcessInsertImplicitGreedyDepthReal.m
• ProcessInsertImplicitParentNodeOverlapReal.m
• ProcessInsertImplicitReal.m
• ProcessInsertImplicitSyn.m
• ProcessInsertImplicitTrajOverlapReal.m
• ProcessInsertStandardReal.m
• ProcessInsertStandardSyn.m

NN Query Experiments:

• ProcessNNCCTvsNaiveReal.m
• ProcessNNCCTvsNaiveSyn.m
• ProcessNNeAddReal.m
• ProcessNNeMultReal.m
• ProcessNNeMultSyn.m
• ProcessNNExactApproxRadiiReal.m
• ProcessNNExactApproxRadiiSyn.m
• ProcessNNExactCountDistReal.m
• ProcessNNExactCountDistSyn.m
• ProcessNNExactCrossQueryReal.m
• ProcessNNExactReal.m
• ProcessNNExactRealBruteForce.m
• ProcessNNExactRealCCT3.m
• ProcessNNExactRealLessBnd.m
• ProcessNNExactRealMtree.m
• ProcessNNExactSyn.m
• ProcessNNExactSynBruteForce.m
• ProcessNNExactSynCCT3.m
• ProcessNNImplicitReal.m
• ProcessNNImplicitSyn.m
• ProcessNNReachReal.m
• ProcessNNReachSyn.m
• ProcessNNTaxiScale.m
• ProcessNNVaryeAddReal.m
• ProcessNNVaryeMultReal.m

kNN Query Experiments:

• ProcesskNNeAddReal.m
• ProcesskNNeMultReal.m
• ProcesskNNeMultSyn.m
• ProcesskNNExactReal.m
• ProcesskNNExactRealCCT3.m
• ProcesskNNExactRealMtree.m
• ProcesskNNExactRealMtreeBring.m
• ProcesskNNExactSyn.m
• ProcesskNNExactSynCCT3.m
• ProcesskNNImplicitReal.m
• ProcesskNNImplicitSyn.m
• ProcesskNNk1ExactReal.m
• ProcesskNNk1ExactSyn.m
• ProcesskNNVaryk.m

Range Query Experiments:

• ProcessRNNCCTvsBringReal.m
• ProcessRNNCCTvsBringSyn.m
• ProcessRNNeAddReal.m
• ProcessRNNeMultReal.m
• ProcessRNNExactReal.m
• ProcessRNNExactRealBringLessBnd.m
• ProcessRNNExactRealCCT3.m
• ProcessRNNImplicitReal.m
• ProcessRNNVaryTau.m