SIA(M)ESE: An efficient algorithm for transposition invariant pattern matching in multidimensional datasets
Geraínt A. Wiggins, Kjell Lemström, David B. Meredith · 2001
In this paper, we study pattern matching in multidimensional datasets. The aim is to find translation (transposition) invariant occurrences of a given query pattern, called template, in an arbitrary multidimensional dataset. Between the points in the dataset that have been found to match the consecutive points in the template, there may be any finite number of other intervening datapoints. For this task, we introduce an algorithm, called SIA(M)ESE, which is based on the SIA pattern induction algorithm (Meredith et al., prep). The algorithm is first introduced in abstract mathematical form, then we show how we have implemented it using sophisticated techniques and equipped it with sensible heuristics. The resulting efficient algorithm has a worst case running time of O(mnlog(mn)), where m and n are the size of the template and the dataset, respectively. We consider several application domains, such as cognitive modeling of music and matching of polyphonic music and bitmap images, and show the flexibility of SIA(M)ESE. It not only solves the problem it is developed for, but without any change to its original time complexity, it can also simulate the working of several existing algorithms developed for distinct pattern matching problems.