Advanced search


Ramón A. Mollineda, Enrique Vidal, Francisco Casacuberta. A Windowed Version of the Bunke and Bühler Algorithm to Better Approximate Dissimilarities between Cyclic Patterns. Proceedings of 5th Iberoamerican Symposium on Pattern Recognition, 2000. pp. 311-321. Portuguese Association of Pattern Recognition.

An efficient approximate technique for measuring dissimilarities between cyclic patterns is presented. It is inspired on the quadratic time algorithm proposed by Bunke and Buhler (BBA). This algorithm computes an estimation of the distance measured between two cyclic strings 'x' and 'y', by finding in an edit graph, an alignment between 'x' with its most similar substring of some rotation of 'y'. The technique presented in this paper defines a diagonal window on the edit graph for each starting node where alignments originate from. Each alignment will be constrained to be within the window associated to its starting node. It guarantees alignments between 'x' and substrings very close to some rotation of 'y', leading to a much better approximation to the exact cyclic distance value between 'x' and 'y'. Experiments were conducted on both artificial and real data, to demonstrate the capabilities of the new technique in both accurateness and quadratic computing time.