A prefix tree-based user interface for exploring abstract structure in Irish folk tunes

by James McDermott

When writing a tune, when do composers repeat some material; when do they introduce a variation of previous material; and when do they introduce totally new material? To ask the same questions in a different way: what are the abstract syntactical structures in melodies?

In 2020, composer, musicologist, and traditional Irish fiddle player Seán Doherty (Dublin City University) set out to answer these questions in the context of Irish traditional music. He used “the bible”, O’Neill’s The Dance Music of Ireland: 1001 Gems as his source.

Doherty developed a simple system for analysing repetition and variation in these tunes, working at the bar level. We’ll explain it using the first tune, Shandon Bells, as an example.

In these tunes there are usually 2 or 3 main parts, of 8 bars each, usually repeated, possibly with alternate endings for each repeat. Shandon Bells has 2 parts, labelled A and B above.

In the repetition/variation annotation system, the first bar is labelled a as shown above. (These letters A and a are part labels and bar labels, not musical notes.) Then for each subsequent bar:

• If it’s the same or almost the same as a previous bar, it gets the same label.
• If it’s similar to a previous bar (50% or more, or a transposition), it’s labelled as a variation, eg a¹, as in bar 3 above.
• Otherwise, it gets the next sequential letter, eg bar 2 above is labelled b.
• If a bar is similar to a bar in a previous part, the label is prefixed with the part name, eg bar 7 in part B is labelled Ad.

With this system, Doherty annotated all 1001 Gems. He found for example the following structures (focussing just on the A part in each case):

We observe that multiple tunes, even quite different ones, can share the same abstract syntactical structure (eg Johnny’s Wedding and Lough Allen, above). Doherty went on to analyse several different types of structure and their frequency in different tune types, eg jigs and reels.

At this point, Doherty contacted James McDermott (University of Galway), the leader of Polifonia Work Package 3 (on Mining Musical Patterns), and McDermott brought in Kieran Jayes, a student in University of Galway. As computer scientists, McDermott and Jayes were keen to introduce an appropriate data structure and user interface to explore the analyses produced by Doherty.

In collaboration, then, we began by observing that of course all structures start with a by definition, but more importantly there is a prefix structure: every pair of tunes shares some prefix, for example Shandon Bells and The Pipers’ Picnic share a, b before they diverge. This suggests the prefix tree or trie data structure. This is a tree where every node label is a prefix of the labels of its children. For example, in Figure 2, we see that node a has a child a, a¹, and that child has a child labelled a, a¹, a². However, when we visualise all 1001 tunes in a prefix tree, it quickly becomes unwieldy (Figure 3).

We decided to base the user interface on visualising and exploring that data structure in a more manageable way. Using Firebase, Node, Typescript, React, and D3, Jayes created an online user interface in which the user can expand and collapse levels of the tree, filter and search (Figure 4). The nodes in the final level of the tree are now labelled with tune names (Figure 5), which can be clicked to access a score and audio rendering (Figure 6).

Exploring this user interface we find interesting results, such as structures which are unique across the corpus (eg Petticoat Loose is the only tune with structure a, b, a, c, a, d, e, c¹,  see top of Figure 5) and others which are extremely common (eg there are 89 tunes with structure a, b, c, d, a, b, c, f).  

The user interface is available at: https://fyproject-98a82.firebaseapp.com/ and necessary data files are available at: https://gist.github.com/jmmcd/7fefb0fea2a4d00d74f6a3a8eaab81cf

This work was presented at the HCI International 2023 Workshop on Interactive Technologies for Analysing and Visualizing Musical Structure, Sunday 23 July 2023, Copenhagen, Denmark https://2023.hci.international/W1.html. The workshop organiser was David Meredith. The full programme is available at: http://www.titanmusic.com/events/hcii2023/workshop/accepted-papers/hcii2023workshopprogramme.html

Kieran Jayes, School of Computer Science, University of Galway

Seán Doherty, School of Theology, Philosophy, and Music, Dublin City University

James McDermott, School of Computer Science, University of Galway