Improving map generalisation with new pruning heuristics created by Patrick Taillandier &Julien Gaffuri

Many automated generalisation methods are based on local search optimisation techniques: Starting from an initial state of the data, one or several new child states are produced using some transformation algorithms. These child states are then evaluated according to the final data requirements, and possibly used as new candidate state to transform. According to this approach, the generalisation process can be seen as a walk in a tree, each node representing a state of the data, and each link a transformation. In such an approach, the tree exploration heuristic has a great impact on the final result: Depending on which parts of the tree are either explored or pruned, the final result is different, and the process more or less computationally prohibitive. This article investigates the importance of exploration heuristic choice in automated generalisation. Different pruning criteria are proposed and tested on real generalisation cases. Recommendations on how to choose the pruning criterion depending on the need are provided.