Measuring Similarity for Directed Path in Geometric Data
Subject Areas :
Mohammad Farshi
1
,
Zeinab Saeidi
2
1 - Assistant Professor
2 - University student
Keywords: Data structure, Fréchet distance, Hausdorff distance, Similarity, Directed Path,
Abstract :
We consider the following similarity problem concerning the Fréchet distance. A directed path π is given as input and a horizontal segment Q is defined at query time by the user. Our goal is to preprocess and save the directed path π into a data structure such that based on the information saved in the data structure, one sub-path of the directed path can be reported which Fréchet distance between the sub-path and the horizontal query segment Q is minimum between all possible sub-paths. To the best of our knowledge, no theoretical results have been reported for this problem. In this paper, the first heuristic algorithm is proposed. We only experimentally show the quality of the algorithm in several datasets due to no existing algorithm.