On the Memory Usage of the SIA Algorithm Family for Symbolic Music Pattern Discovery

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


SIA is a fundamental algorithm in symbolic musical pattern discovery, which reports all maximal translatable patterns in a point set. The original SIA algorithm requires 𝑂(𝑘𝑛^2log𝑛) time and 𝑂(𝑘𝑛^2) space, where n is the number of points in the data set, and k is the number of coordinates in each point. In this paper, we present a sweepline algorithm that shares the running time of SIA but requires only O(kn) space, enabling to process of larger data sets without running out of memory. Since SIA is the first step in many pattern discovery tasks, our new algorithm can have a broad impact. For example, we discuss the problem of finding all occurrences of maximal translatable patterns with specific properties. We also compare the algorithms in practice and show that reduced memory usage can benefit real data sets.
Original languageEnglish
Title of host publicationMATHEMATICS AND COMPUTATION IN MUSIC (MCM 2022) : Proc. 8th International MCM Conference, Atlanta
EditorsM Montiel, O A Agustín-Aquino, F Gómez, F Kastine, J Lluis-Puebla, E Milam
Number of pages12
PublisherSpringer LNCS
Publication date2022
ISBN (Print)978-3-031-07014-3
ISBN (Electronic)978-3-031-07015-0
Publication statusPublished - 2022
MoE publication typeA4 Article in conference proceedings
EventInternational Conference on Mathematics and Computation in Music - Atlanta, United States
Duration: 21 Jun 202224 Jun 2022
Conference number: 8

Publication series

Name Lecture Notes in Computer Science book series (LNAI)

Fields of Science

  • 6131 Theatre, dance, music, other performing arts
  • 113 Computer and information sciences
  • Pattern discovery
  • SIA algorithms
  • Memory usage

Cite this