Structural Similarity Basedon Time-span Sub-trees
Masatoshi Hamanaka, Keiji Hirata, and Satoshi Tojo
1
2

Kyoto University, masatosh@kuhp.kyoto-u.ac.jp
Future University Hakodate, hirata@fun.ac.jp
3
JAIST, tojo@jaist.ac.jp

Abstract. We propose structural similarity of two melodies based on
sub-trees from the time-span tree provided by the Generative Theory ofTonal Music. The structural distance of the tree was previously deﬁned
and called the “maximal time-span distance,” and experimental results
showed to some extent a correspondence between the maximal time-spandistance and psychological similarity. However, there is a big problem
in that almost all pairs of melodies are not similar on the basis of the
maximal time-span distance because the deﬁnition of the similarity is toostrict. Therefore, we attempt to express a melodic structural similarity byusing the coincidence rate of time-span sub-trees to weaken the condition
for calculating similarity. We have set up three experimental conditions
and compared their results.
Keywords: GTTM, time-span tree, similarity, meet, join

1

Introduction

We have been developing music analyzers based on the Generative Theory ofTonal Music (GTTM) [1, 2]. The main advantage of analysis with GTTM is thatit can acquire a tree structure called a “time-span tree” from a score, and thistree structure provides a method for manipulating a piece of music [3].
Before using such manipulation, we have to manually select a melody similar
to the target melody. For example, the melody morphing method [3] that generates an intermediate melody between a melody and another melody requires
similar melodies for input; otherwise, the two melodies cannot be aligned, andthen, a melody cannot be made that has the ﬂavor from both input melodies.
If the values of similarity are not distributed appropriately, it is diﬃcult torepresent the search or recommendation result. For example, when there aremany pieces of music for which similarity is 1.0 between query pieces, as a resultof search or recommendation, there are too many top ranking pieces, and weneed a lot of time to preview the top ranking pieces. Therefore, it is desirable
that the similarity value is appropriately distributed without duplication.It is
desirable that the obtained subjective similarity results of listening experiments
become close to similarity by calculation.

The maximal time-span distance is the sum of the lengths of time spansthat match perfectly from root to leaf and is good for measuring the similarity
between variations because these variations have a common structure [4]. However, the maximal time-span distance cannot measure the similarity between two
diﬀerent melodies because they usually do not have a common structure.
To measure this similarity, we attempted to weaken the condition for matching time-span trees by using the coincidence rate of time-span sub-trees. We
compare three kinds of matching conditions: tight, middle, and weak. Experimental results show that the middle condition is better for the use tasks ofsearching or recommendation. In the maximal time-span, similarity is calculated by using the sum of matched numbers of notes weighted by the length ofthe maximal time-span. We also discuss whether this weight is proper or not by
considering the subjective similarity and similarity by calculation.

2

Maximal Time-span Similarity

The time-span tree is a binary tree and is a hierarchical structure describing therelative structural importance of notes that diﬀerentiate the essential parts of a
melody from the ornamentation. In the tree, the essential notes are connected toa branch nearer to the root of the tree. In contrast, the ornamentation notes areconnected to the leaves of the tree. In a separation, we hereafter call the branch“primary” and leaf “secondary” (Fig. 1a). The time-span tree can extract anabstracted melody by reducing ornamentation notes.
Distance between melodies before and after reduction can be expressed as
the length of the maximal time-span mi of a reduced note. Maximal time-span
mi is a sum of time spans ti s of the entire notes, which are recursively connectedto the note as secondary. In Fig. 1b, note 2 is connected to note 1 as secondary.
Therefore, m2 is the same as t2 , and m1 is the sum of t1 and t2 . In the same way,
m3 is the sum of t3 and m1 because note 1 is connected to note 3 as secondary.
We equate melody A with its time-span tree A hereafter. The distance between A and B in Fig. 1b is the sum of maximal time-spans of reduced notes,
which we express as |B − A| The maximal time-span distance [4] between P
and Q can be expressed as the distance via meet |P − P ⊓ Q| + |Q − P ⊓ Q| or
distance via join |P ⊔ Q − P | + |P ⊔ Q − Q|.The meet operator P ⊓ Q extracts thelargest common part or the most common information of the time-span trees(a) Primary and secondary
Parent !me-span(b) Maximal time-span distancePrimary (salient) branchPrimary!me-span

Secondary (nonsalient) branchSecondary!me-spanNoteTimespan

n1
t1

n2
t2

Maximal !me-span

m1

Fig. 1. Time-span trees

n3
t3
m3

m2

in a top-down manner (Fig. 2a). The join operator P ⊔ Q unites two time-spantrees in a top-down manner as long as the structures of the two time-span trees
are consistent . In fact, the distances via join and meet are the same[4]. The
distance between P and Q is maximized when P and Q do not have a common
part, which means P ⊓ Q is empty ⊥ (bottom) as |P − ⊥ | + |Q− ⊥ |.
The maximal time-span similarity is calculated by normalizing the maximal
time-span distance by dividing the maximized maximal time-span distances andsubtracting them from 1.4
1−|P − P ⊓ Q| |Q − P ⊓ Q|−
2 · |P − ⊥ |2 · |Q− ⊥ |(1)

The maximal time-span similarity is higher when the common part of P and Q,
which can be expressed as P ⊓Q, is larger. However, the condition for matching is
too strict because it compares perfectly from root to leaf through the separationof branches. This strict matching is very good at comparing very similar melodies
such as themes and variations [4].
In comparison, the maximal time-span similarity is usually zero between two
diﬀerent melodies.5 In the experiments, we use time-span trees of 300 8-bar-longmonophonic classical music in the GTTM database [5]. In fact, 32 out of 300
pieces in the GTTM database can be interpreted as two kinds of time-span trees.
Therefore, we use all the pairs of 332 time-span trees and 32 pairs of the maximal
time-span similarity that are bigger than zero.

3

Time-span Sub-trees Similarity

In the time-span tree, each note is connected to the root through the separations.
The matching of maximal time-span similarity is done by comparing all the
separations of each note that is a primary or secondary. If the primary/secondary
separation was diﬀerent at some level, all the branches below the separation werediscarded as unmatched. In this sub-tree matching, we only pay attention to theﬁnal primary/secondary separation, i.e., the separation to leaf note. From now
on, we call a pair of a primary branch and a secondary branch with no otherseparation a sub-tree. Figure 2b is an example of matching in the maximal timespan tree, where n1 is the secondary of the ﬁrst separation from the root and also
the secondary of the second separation from the root, while n2 is the primary of
the ﬁrst separation from the root and secondary of the second separation. Thus,
n1 and n2 are unmatched. Figure 2c is an example of matching in time-span
sub-tree similarity, where n1 is the secondary of the last separation and also thesecondary of last separation. Thus, n1 and n2 match.
4

This deﬁnition of similarity is diﬀerent from general deﬁnitions such as of the Jaccard
coeﬃcient, the Simpson coeﬃcient, and Dice coeﬃcient in that we independently
normalize P − P ⊓ Q and Q − P ⊓ Q; otherwise, only one melody is inﬂuential when
one melody has a lot of notes and the other has little numbers of notes.
5
The distance by maximal time-span has been improved in [6], however, we here omit
its detail by our limited space. We will compare this improved distance by maximal
time-span with our sub-tree similarity in future.

(a) Meet and join

TBTA(b) Maximal time-span similarity

TA ⊓ TB(c) Time-span sub-tree similarity
Primary

Secondary=⊓

Secondary

SecondaryTA

TB

TA ⊔ TB

n

1

n

2

n

1

n

2

Fig. 2. Examples of meet ⊓, join ⊔, and matching of nodes

The matching of maximal time-span similarity is done by comparing thepitches of each note exactly same or not. In our sub-tree matching, we easethe matching condition only focusing on whether two notes of the sub-trees areascending or descending. Thus, we can regard two sub-trees are matching only
if this ascending/descending feature is common between them. Then, we canconsider the following three patterns: (i) the pitch of the primary note is higher
than that of the secondary, (ii) the pitch of the primary note is lower thanthat of the secondary, or (iii) the primary and secondary notes have the same
pitch. Now we name this classiﬁcation Mp = 3. Furthermore, we can loosen thecondition, as (i’) the pitch of the primary note is higher than or equal to that of
the secondary or (ii’) the primary is lower than or equal to the secondary, and wecall this classiﬁcation Mp = 2. On the contrary, we can tighten the condition; thepitch of two primary notes must be the same when two sub-trees are matched.
We will experiment all these conditions and will compare the results.
The matching of maximal time-spans is done by comparing the onset andlength of the maximal time-spans in all separations from the root to leaf thatare exactly same. Here we pay attention to the middle point of a maximal timespan as there may exist rests at either end of the span. The relative location of
the middle points of two time-spans is named gap. The matching of time-span
sub-tree similarity is done by comparing the gap of the middle of the maximal
time-span and the length ratio of the maximal time-span in the sub-trees thatare in a certain range. In other words, if the gap of the middle of maximal timespans is in Mg times of the length of a piece of music and the ratio of the longer
maximal time-span and shorter maximal time-span is in Mr , the time-span subtrees are matching. We will change Mg to 0.1, 0.2, and 0.3 and also change Mr
to 1.1, 1.3, and 1.5, and discuss which condition is appropriate.
In maximal time-span similarity, notes close to the root branch are more
important than notes far from the root branch because the weights for calculating
maximal time-span similarity are the lengths of the maximal time-spans. In theexperiment, we compare the calculation of time-span similarity has a weight(Mw =length of the maximal time-span) or has no weight (Mw = 1).

4

Experimental Results

The time-span sub-tree similarity proposed in Section 3 enables the condition
for matching pitch, time, the nodes of the tree, and weight for matiching to bechanged. We compare three kinds of matching conditions as follows: (a) Tight
condition, with Mp = 3, Mg = 0.1, Mr = 1.5, Mw = 1 and exactly match ofprimary pitch; (b) Middle condition, with Mp = 3, Mg = 0.2, Mr = 1.3, Mw = 1;(c) Loose condition, with Mp = 2, Mg = 0.3, Mr = 1.5, Mw = 1. Figure 3 ishistograms of similarities of each matching condition from the 300 pieces in the
database. Compared with the original maximal time-span similarity, Fig. 3a is
a decrease in the number of similarities, which is zero; however, most of thesimilarities are still zero, and all the similarities are under 0.5. In Fig. 3b, thesimilarities were distributed in a wide area, and the shape of the distribution was
similar to the standard distribution. In comparison, the center of the distributionof Fig. 3c leaned to the right, and very few similarities were in the area of zero
to 0.3. From the above results, (b) is appropriate in the three conditions.
We compared two kinds of weight for matching: (c) Mw = 1 and (d) Mw =the length of maximal time-span. Here, for the values of Mp , Mg , and Mr , weuse the condition of (b). Figure 3d is a histogram of similarity made by using
the weight as (d), which has also a long distribution.
As described in 2, the 32 out of 300 pieces in the GTTM database have twokinds of time-span trees corresponding to interpretation from musicologists. It
is preferable that each two kinds of time-span trees are similar because there
are interpretations of the same piece. We calculated the average similarity of
the 32 pieces by using the weights of (c) and (d). As a result, the average ofsimilarity for (c) was 0.77 and for (d) was 0.6. To compare the values from (c)and (d), we normalized the average to 0 and variance to 1 because the averageand distribution of similarities from (c) and (d) were diﬀerent. As a result of
normalization, the average similarity for (c) was 2.16 and for (d) was 2.65. These
values depend on the character of the corpus. In current 300 piece the weightfor matching is appropriately by using condition of (c) than (d).
We show some examples that show high similarities where the condition is(b). The similarities of Fig. 4a and b was 0.90, c and d was 0.88.

5Conclusion

Although maximal time-span similarity was previously proposed, the similarityof two diﬀerent pieces of music is usually zero. We proposed time-span sub-tree
similarity, for which similarity is made to be more than zero in many cases by
weakening the condition for matching maximal time-span similarity. In the experimental results obtained with three kinds of matching condition, the middle[Frequency] (a) Tight condition
30,00020,000[Frequency] (b) Middle condition[Frequency] (c) Loose condition [Frequency] (d) Mw = length of time-span

15,00015,00010,00010,000

5,000

5,000

20,00015,00010,00010,000

0.0

0.2

0.4
0.6
[Similarity]

0.8

1.0 0.0

5,000

0

0

0

0.2

0.4
0.6
0.8
[Similarity]

1.0 0.0

0

0.2

0.4
0.6
[Similarity]

0.8

1.0 0.0

Fig. 3. Histograms of time-span sub-trees similarity

0.2

0.4
0.6
[Similarity]

0.8

1.0

(a) The nutcracker suite Op.71a
̀̀Miniature overture''(Pyotr Il'yich Tchaikovsky).
b
œ. ≈ œ œ œ œ. œ.
& b 42 Jœ ‰>œ œ œ. œ.

>œœ œ œ. œ œ œ.

œ œ œ. œ. œ.

π

œ ‰
J

(b) Annen-Polka Op.117(Johann Baptist Strauß)#& 42 œ œ œ. œ œ œ.

œ œ œ. œ. œ.

.
œ. . >œ
œ. ‰ œ ≈ œ œ œJœ œ. œ. œ.

œ. œ. . œ.
œœ. œ. œ.

œ. œ. . œ.
œœ. œ. œ. ‰Jœ.

j
œ œ œ ‰(c) Sonatine Op.20-1 C dur(Daniel Friedrich Rudolph Kuhlau)& 42œ œ œ . œ #œ œ œ œ œ . œ #œ œ œ œ œ . œ œ œ œ œ #œp(d)Sonatine Op.36-5 G dur(Muzio Filippo Vincenzo
Francesco Saverio Clementi)# œœ œ œ& 42pœœ œ œœ œœ œ œ œ œ. œ. œ œ œ œ œœ œ œ œ . œ œ œ œ œ œ . œ #œ œ œ œ œ œ œ œ>œœœœ œœœJ ‰œ œ œ œ œ̆ œ. œ œ œ œ œ̆ œ. œ œ œ œœ J ‰ ŒFig. 4. Example of Analysis

one was better than the other conditions with the GTTM database. We plan toconstruct applications for similarity with the time-span tree because the appropriate deﬁnition of similarity depends on the application.

Acknowledgments
This work was supported in part by JSPS KAKENHI Grant Numbers 23500145,
25330434, and 25700036 and PRESTO, JST.

References
1. Lerdahl, F., Jackendoﬀ, R.: A Generative Theory of Tonal Music. MIT Press, Cambridge (1983)
2. Hamanaka, M., Hirata, K., Tojo, S.: Implementing “A Generative Theory of Tonal
Music” Journal of New Music Research, 35:4, 249-277, (2007)
3. Hamanaka, M., Hirata, K., Tojo, S.: Melody morphing method based on GTTM.
In: Proceeding of ICMC2008 , pp. 155–158. Belfast (2008)
4. Tojo, S., Hirata, K.: Structural Similarity Based on Time-span Tree. In: Proceedingof CMMR2012 , pp. 645–660. London (2012)
5. Hamanaka, M., Hirata, K., Tojo, S.: Music Structural Analysis Database based on
GTTM. In: Proceeding of ISMIR2014 , pp. 325–330. Taipei (2014)
6. Hirata, K., Tojo, S., Hamanaka, M.: Cognitive Similarity grounded by tree distancefrom the analysis of K.265/300e. In: Proceeding of CMMR2013, pp. 415–430. Marseille (2013)