Abstract
We present a polynomial-time algorithm that discovers all maximal patterns ina point set, $D\in\mathbb{R}^k$, that are related by transformations in auser-specified class, $F$, of bijections over $\mathbb{R}^k$. We also present asecond algorithm that discovers the set of occurrences for each of thesemaximal patterns and then uses compact encodings of these occurrence sets tocompute a losslessly compressed encoding of the input point set. This encodingtakes the form of a set of pairs, $E=\left\lbrace\left\langle P_1,T_1\right\rangle,\left\langle P_2, T_2\right\rangle,\ldots\left\langleP_{\ell}, T_{\ell}\right\rangle\right\rbrace$, where each $\langleP_i,T_i\rangle$ consists of a maximal pattern, $P_i\subseteq D$, and a set,$T_i\subset F$, of transformations that map $P_i$ onto other subsets of $D$.Each transformation is encoded by a vector of real values that uniquelyidentifies it within $F$ and the length of this vector is used as a measure ofthe complexity of $F$. We evaluate the new compression algorithm with threetransformation classes of differing complexity, on the task of classifyingfolk-song melodies into tune families. The most complex of the classes testedincludes all combinations of the musical transformations of transposition,inversion, retrograde, augmentation and diminution. We found that broadeningthe transformation class improved performance on this task. However, it didnot, on average, improve compression factor, which may be due to the datasets(in this case, folk-song melodies) being too short and simple to benefit fromthe potentially greater number of pattern relationships that are discoverablewith larger transformation classes.