Accelerating Computation of Stable Merge Tree Edit Distances Using Parameterized Heuristics

Area of Science:

• Computational topology
• Data analysis

Background:

• Edit distance calculations on merge trees are crucial for data analysis but computationally challenging (NP-complete).
• Existing methods struggle with specific data perturbations like saddle swaps, limiting their practical application.

Purpose of the Study:

• To introduce a novel heuristic algorithm for deformation-based edit distance on merge trees.
• To enable a trade-off between accuracy and computational cost using a user-controlled look-ahead parameter.

Main Methods:

• Developed a heuristic algorithm for deformation-based edit distance.
• Incorporated a user-controlled look-ahead parameter to manage accuracy and computational complexity.
• Achieved a fixed parameter tractable running time, polynomial in input size and exponential in the look-ahead value.

Main Results:

• The algorithm efficiently handles saddle swaps, a common challenge in merge tree analysis.
• Demonstrated computational efficiency and effectiveness in experimental results.
• Maintained feasible computation times despite increased complexity.

Conclusions:

• The novel heuristic algorithm enhances the applicability of deformation-based edit distance for merge trees.
• The look-ahead parameter provides practical control over computational resources.
• This method effectively addresses specific data perturbations, improving data analysis capabilities.