Scaling and compressing melodies using geometric similarity measures

Scaling and compressing melodies using geometric similarity1 measures2 L.E. Caraballo * J.M. D´ıaz-B´a˜nez ∗F. Rodr´ıguez ∗V. S´anchez-Canales ∗ 3 I. Ventura ∗  4 March 24, 20225 Abstract6 Melodic similarity measurement is of key importance in music information retrieval. In this 7 paper, we use geometric matching techniques to measure the similarity between two melodies. 8 We represent music as sets of points or sets of horizontal line segments in the Euclidean plane and 9 propose efficient algorithms for optimization problems inspired in two operations on melodies; 10 linear scaling and audio compression. In the scaling problem, an incoming query melody is scaled 11 forward until the similarity measure between the query and a reference melody is minimized. 12 The compression problem asks for a subset of notes of a given melody such that the matching 13 cost between the selected notes and the reference melody is minimized.14 Keywords: Melodic similarity, geometric matching, algorithm, scaling, compressing.15 16 1 Introduction17 Musical information retrieval (MIR) is a flourishing field that takes advantage of techniques developed 18 in computer science and mathematics. With the increased availability of large musical data comes 19 the need to design methods for searching and analysing this information. Musicological and 20 computational studies on rhythmic and melodic similarity have given rise to a number of geometric 21 problems [ 1 , 2 , 3 ]. A melody can be codified as a consecutive sequence of musical notes and each 22 note can be represented by a point (point representation) [ 4 ] or a horizontal segment (segment 23 representation) with a time/pitch value [ 5 ]. In this paper we study two problems that arise in 24 MIR; linear scaling and melody compressing. Linear scaling is used for tempo variation and melody 25 matching [ 6 , 7 ], while an important application of data compression is clustering and classification 26 [ 8 ]. Given a reference melody, a query melody, and a similarity measure, in the scaling problem the 27 incoming query is scaled forward in the horizontal direction to find the minimum similarity measure 28 * Department of Applied Mathematics II, University of Seville, Camino de los descubrimientos s/n, 41092 Seville, Spain. Email: v[email protected], {dbanez, frodriguex, vscanales, iventura}@us.es  Corresponding author. This research has been supported by projects MTM2016-76272-R of the Spanish Ministry of Economy and Competitiveness (AEI/FEDER,UE), PID2020-114154RB-I00 of the Ministry of Science and Innovation (CIN/AEI/10.13039/501100011033/) and the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No. 734922. Research of V. S´anchez- Canales was partially supported by San Pablo Andalucia CEU Foundation. 1 between it and the reference melody. The compression problem seeks to select k notes of a given 29 melody such that the similarity measure between the reference melody and the simplified melody is 30 minimized.31 The main techniques that have been explored in the literature for melodic similarity are based 32 on string matching and geometric measures. String matching techniques are more efficient but 33 techniques based on geometric similarity measures have a higher accuracy search rate.34 Some strategies based on string matching are longest common subsequence (LCS)-based algo- 35 rithms, dynamic time warping (DTW) and edit distance (ED)-based methods. The LCS approach 36 represents a global alignment since it does not characterize local information such as gaps or mis- 37 matched symbols of the common sequence. To overcome this problem, most LCS-based algorithms 38 use penalty functions [ 9 ]. DTW adapts two sequences non-linearly in the time dimension to calculate 39 the similarity, and it has been extensively explored for audio comparison [ 10 ]. The edit distance can 40 be expressed as the minimum number of edit operations to convert one sequence into the other. 41 Edit distance–based methods have been proposed as a music dissimilarity measure [ 11 , 12 ], and 42 they have been combined with the use of a specific set of representative mid-level melodic features 43 in specific musical repertoires [13].44 The scaling problem in this paper assumes the symbolic melodic representation and measures 45 similarities with a geometric matching. A closely related problem is to compute the best matching 46 between a short melodic query phrase and a longer reference melody. A geometric technique that 47 considers both pitch and rhythm information was proposed by [ 5 ]: Each note is represented as a 48 horizontal line segment, so a sequence of notes can be described as a rectangular contour in a 2D 49 coordinate system, in which the horizontal and vertical coordinates correspond to time and pitch 50 value, respectively. Then the similarity measure between two melodies is the minimum area between 51 them. The optimal matching is obtained by moving the query segment from left to right and from 52 down to up until the matched area is minimized. Using a binary search tree, in [ 14 ] this geometric 53 similarity measure is computed in O ( nm ( m + log n )) time, where n and m are the lengths of the 54 reference and the query melodies, respectively. Later, the approach was improved by using pitch 55 intervals and a branch-and-prune technique to discard the incorrect horizontal positions of the query 56 [ 15 ]. Finally, the complexity was improved to O ( nm log n ) by [ 16 ] by using a balanced binary search 57 tree.58 Audio data compression is a fundamental component of multimedia big data and a challenge 59 addressed in the field of MIR since its inception. In fact, a major innovation that enabled the 60 explosive growth of digitally represented music is audio compression [ 17 ], which is frequently used to 61 reduce the high data requirements of audio and music. Early works focused mainly on the MPEG 62 audio compression standard and the extraction of timbral texture features [ 18 ]. More recently, the 63 use of newer sparse representations as the basis for audio feature extraction has been explored, 64 covering timbral texture, rhythmic content and pitch content [ 19 ]. Motivated by this task, in this 65 paper we have introduced a new theoretical problem that, given a melody with n notes and a 66 positive integer k < n , asks for k notes to be selected such that the cost given by a geometric 67 matching is minimized. It is clear that the goal here is to efficiently solve this problem from a 68 geometric optimization point of view and important aspects as psychoacoustics (i.e., the study of 69 sound perception by humans) are not used to guide the process.70 2 1.1 Problem Statement71 A melody is made up of musical notes, each of which has attributes such as pitch, duration, timbre, 72 loudness, etc., and the melody can be coded in a symbolic representation or an audio wave format. 73 In this paper, we adopt the symbolic representation, so a melody is represented by a sequence 74 of notes in a time-pitch plane. Each note can be described by a point in 2D representing the 75 pitch at a specific time (point representation) or a horizontal line segment, of which the height 76 and width denote its pitch value and duration, respectively (segment representation). In segment 77 representation, a melody is a consecutive sequence of horizontal segments; that is, a melody can be 78 seen as a step function of time. We also call this representation a melodic contour.79 In either case, for the sake of key-invariance, we will use a pitch interval sequence to represent 80 a melody. Note that with the key-invariance property of this representation, the query melody 81 only needs to move horizontally for the scaling problem. We assume that the melodies are given in 82 lexicographic order of the starting points of the line segments.83 Let R = ( R1, R2, . . . , Rn ) and Q = ( Q1, Q2, . . . , Qm ) be sequences representing two melodies. R84 is the reference melody from the dataset and Q is the query melody to be matched. From here on, 85 we suppose that the duration of melody Q is less than that of R . The elements of R and Q can be 86 consecutive horizontal segments or points in 2D depending on the representation to be used. In the 87 point representation, we assume that the points representing the notes are just the middle points of 88 the horizontal segments in the corresponding segment representation. However, the same approach 89 works if the points correspond to endpoints of the segments.90 In the following we introduce two geometric measures to compute similarity and two operations 91 on a melody that are the main ingredients of the problems.92 Area measure: The region between two melodies with the same duration in the segment represen- 93 tation can be partitioned into rectangles with vertical edges supported by vertical straight lines 94 passing through ending points of the segments. The area between two melodies is defined as the 95 sum of the areas of the rectangular regions of the partition. Since the duration of Q is less than the 96 duration of R , we extend the last segment of Q so that the durations of R and Q are the same. See 97 Figure 1a).98 t-Monotone matching measure: Let R = {Ri = ( xi, pi ) , i = 1 , . . . , n} and Q = {Qj = 99 (tj, qj), j = 1, . . . , m}be two melodies in point representation. In a t-monotone matching between100 R and Q , we map each point of the reference melody R to its t -monotone nearest point in Q ; 101 that is, the left or the right point in time. The unmatched points of Q are associated to their 102 t -monotone nearest point in R . More formally, given Ri = ( xi, pi ) ∈R : if xi< t1 then Ri is assigned 103 to Q1 ; if xi> tm then Ri is assigned to Qm ; if tj< xi< ( tj + tj+1 ) / 2 then Ri is assigned to Qj ; 104 if ( tj + tj+1 ) / 2 < xi< tj+1 then Ri is assigned to Qj+1 . Finally, if xi = ( tj + tj+1 ) / 2 then Ri is 105 assigned to the l1 -nearest point among Qj and Qj+1 (with preference for Qj in the case of a tie), 106 where l1denotes the Manhattan metric. For unmatched points of Q, we follow the analogous rule.107 See Figure 1(b). The cost of the note Qj , φ ( Qj ), is given by the sum of the l1 -distances between Qj 108 and its matched points in R, and the total cost of the matching is109 φ(R, Q) = X Qj∈Q φ(Qj). ε -scaling operation: Consider a segment representation of two melodies R and Q . Let X = 110 ( x0 = 0 , x1, x2, . . . , xn ) and T = ( t0 = 0 , t1, t2, . . . , tm ) be the time partitions given by the segment 111 3 representation of R and Q , respectively, with tm≤xn . Given ε > 0, we define the ε -scaling on the 112 query Q , SQ ( ε ), as the operation of increasing the length of each segment of Q by ε but keeping 113 the starting point of the first segment of Q static. Thus, after an ε -scaling, X does not change 114 and T is transformed to T + ε = ( t0, t1 + ε, t2 + 2 ε, . . . , tm + mε ). The query can be scaled until 115 the two melodies have the same time duration. Thus, 0 ≤ε≤xn−tm m . Note that the pitches of 116 the notes are unchanged in the scaling operation. Now, for a point representation of R and Q , 117 R={(xi, pi), i = 1, . . . , n}and Q={(tj, qj), j = 1, . . . , m }, the ε-scaling of Qis given by118 SQ(ε) = t1+ε 2, q1,t2+3 2ε, q2,...,tm+ (m−1)ε+ε 2, qm. Let tj ( ε ) denote the time associated with the j -th note of SQ ( ε ). Notice that tj ( ε ) = tj + jε in 119 the segment representation and tj(ε) = tj+2j−1 2εin the point representation.120 k -compressed melody operation: Given a melody R with n notes in segment representation 121 and a positive integer k < n , a k -compressed melody or k -compression of R , Ck ( R ), is a melody 122 composed of k segments such that Ck ( R ) and R have the same duration and each segment of Ck ( R ) 123 contains at least a segment of R . See Figure 2(b). For the point representation, a k -compressed 124 melody Ck(R) is a subset of knotes of R. See Figure 2(a).125 0 t1 t2 t3 t4 x1 x2 x3 x4 (x5, t5) R Q 0 x1 x2 x3 x4 x5 x6 x7 t6 t1 t4 t2 t3 t5 a) b) x8 Figure 1: a) Area between the reference melody R and the query Q , Problem 1. b) t -Monotone matching between the reference R(blue) and the query Q(red), Problem 2. In this paper we study the following optimization problems:126 Problem 1. Given two melodies R and Q in segment representation, compute the value of ε > 0 127 such that the area between Rand SQ(ε) is minimized.128 Problem 2. Given two melodies R and Q in point representation, compute the value of ε > 0 such 129 that the cost of the t-monotone matching between Rand SQ(ε) is minimized.130 Problem 3. Given a melody R with n notes in point representation and k < n , compute a 131 k -compressed melody Ck ( R ) such that the cost of the t -monotone matching between R and Ck ( R ) 132 is minimized.133 4 x5 x6 x7 x1 x2 x3 x4 x9 x10 0 x8 0 x1 x2 x3 x4 x5 x6 x7 x8 R C2(R) a) b) Figure 2: a) A 3-compressed melody from an input of 10 notes, Problem 3. b) Area between a melody Rand a 2-compressed melody C2(R), Problem 4. Problem 4. Given a melody R with n notes in segment representation and k , k < n , compute a 134 k-compressed melody Ck(R) such that the area between Rand Ck(R) is minimized.135 Note that in the scaling problems, the reference melody is static whereas the query melody is 136 dynamic. However, the compressing problems ask for an optimal selection of the notes in the input 137 melody. Figures 1 and 2 illustrate the problems.138 1.2 Results and Overview139 In this article, we tackle two geometric problems related to tasks addressed in music information 140 retrieval. Problems 1 and 2 are solved with similar sweeping algorithms in Section 2. Problem 2 141 requires more insight and is, in fact, a constrained case of what is called many-to-many problem 142 studied in areas such as computational biology [ 20 ] and music theory and computational geometry 143 [ 21 ]. Given two sets of two-dimensional points R and B with total cardinality N , a many-to-many 144 matching between R and B pairs each element of R to at least one element of B and vice versa. 145 Given a cost function c ( r, b ), with r∈R and b∈B , the cost of a matching is defined as the 146 sum of the costs of all matched pairs. The problem is to compute a minimum-cost many-to-many 147 matching. In this general setting, the problem can be solved in O ( N3 ) time by reducing it to the 148 minimum-weight perfect matching problem in a bipartite graph [ 22 ], and no best complexity is 149 known. We study the particular case of a t -monotone matching; i.e., the assignment is monotone 150 with respect to the time direction, following the principle that the matching is made between notes 151 that are close in time. We prove that both problems can be solved in O(nm log m).152 In Section 3, we address the compression problem in both variants, using segment and point 153 representation. First, we apply dynamic programming to solve Problem 3, where the monotone 154 nature of the matching is exploited. We show how to solve the problem in O ( kn2 ) time. It is 155 important to note that Problem 3 is a constrained case of a well known problem in operational 156 research, the k -discrete median problem, defined as follows: Given n points in the plane and an 157 integer k , choose k out of the n input points as medians such that the sum of the distances from 158 the input points to their nearest medians is minimized. This problem is shown to be NP-hard [ 23 ]. 159 5 Using some remarkable properties of a solution of Problem 4, we also use dynamic programming 160 to efficiently solve the compression problem for the segment representation in O ( kρn ) time, where ρ161 is the number of different pitch values among the notes of R . Note that if ρ << n , the algorithm is 162 subquadratic. Finally, in Section 4 we draw our conclusions and present some lines for future work. 163 2 Scaling Operation164 2.1 Area as Similarity Measure165 The area between the melodies R and Q is the sum of O ( m + n ) rectangles, as illustrated in Figure 166 1a). Denote by ARQ ( ε ) the area between R and SQ ( ε ) as a function of ε . Observe that if we scale Q167 by continuously increasing ε , eventually, for some value of ε , there exist i and j such that xi = tj ( ε ). 168 At this instant, some rectangles disappear and after that, new rectangles appear. We call this 169 value of ε an event. There are O ( nm ) events. Also note that between two events, the areas of 170 some rectangles increase, others decrease and others are unaffected. The type of a rectangle can 171 be characterised by its vertical edges. Rectangles can be classified into four types: type C0 , with 172 vertical edges passing through xi and xi+1 ; type C1 , with vertical edges passing through tj and tj+1 ; 173 type C2 , with vertical edges passing through xi and tj and type C3 , with vertical edges passing 174 through tjand xi. Figure 3 illustrates an event in which a rectangle of type C3disappears.175 ... ... ... ... ... ... xi xi+1 tj+1 tj tj(ε) = xi ... ... ... ... ... ... xi+1 tj+1(ε) ε ε rj+11 rj+12 rj2 rj1 r0 j1 rj+11 rj+12 a) b) Figure 3: a) Rectangles between R and Q . b) After the scaling SQ ( ε ), an event is found when tj touches xi. Rectangle rj1disappears and rj2is renamed to r0 j1. The following result allows us to discretize the problem:176 Lemma 5. ARQ(ε)is a piecewise linear function.177 Proof. Let rjk be the kth rectangle generated by the jth segment of Q as illustrated in Figure 3. Since only the widths of the rectangles change in the scaling operation, we denote the base and the height of rjk by bjk ( ε ) and hjk , respectively. According to the types of rectangles, the area function between two consecutive events can be expressed as: ARQ(ε) = X rjk∈C0 bjk(ε)hjk+X rjk∈C1 bjk(ε)hjk+X rjk∈C2 bjk(ε)hjk+X rjk∈C3 bjk(ε)hjk. 6 Now let ε0< ε00 be two scaling moves between two consecutive events. Then178 ARQ(ε00) = ARQ(ε0)+(ε00 −ε0) X rjk∈C1 hjk+X rjk∈C2 jhjk−X rjk∈C3 (j−1)hjk .(1) Thus the area function is linear between two consecutive events.179 As a consequence of Lemma 5, a solution of Problem 1; i.e., the minimum area in the scaling 180 operation, is reached at the events and our approach is to efficiently sweep the events from left to 181 right, keeping the minimum value of area. The following result shows how to update the area value 182 at each event.183 Lemma 6. ARQ(ε)can be updated between two consecutive events in O(1) time.184 Proof. Let εi , εi+1 be two consecutive events. ARQ ( ε ) is a continuous piecewise linear function 185 whose value at εi+1 can easily be computed from ARQ ( εi ) as follows. Note that an event can be 186 viewed in the abscissa axis as a swap between points tj and xj (see Figure 3). Indeed, the points 187 involved in the event are tj , xi and their neighbors. Thus, the changes at any event are: a type C3 188 rectangle disappears, a type C2 appears and two neighbouring rectangles change their types. All 189 the other rectangles maintain their type. Thus, Equation (1) can be used to compute the area at 190 the new event εi+1 in O(1) time.191 We are ready to efficiently solve the problem.192 Theorem 7. Problem 1 can be solved in O(nm log m) time.193 Proof. First, for every segment of the query Q , we store its events in an ordered list. Each element 194 in the list holds the epsilon value, the height, and the type of the rectangles involved. We have m195 lists overall. Since the input for R is an ordered sequence of segments, each list can be computed in 196 O(n) time; thus we spend O(nm) time to compute the mlists.197 Given the area for ε = 0, ARQ (0), we build a min-heap whose nodes are m events, the first 198 of each list. Sweeping with a vertical line from left to right we use the lists to maintain the next 199 event in the heap and update the area at each event. The process ends when there are no events in 200 the heap. Since updating the area spends O (1) time, by Lemma 6, the sweeping algorithm spends 201 O(mn log m) time.202 2.2 t-Monotone Matching as Similarity Measure203 Let R = {Ri = ( xi, pi ) , i = 1 , . . . , n} and Q = {Qj = ( tj, qj ) , j = 1 , . . . , m} be two melodies in 204 point representation. For the sake of simplicity, we denote the pair (Ri, Qj) as (i, j).205 Given ε > 0, a t -monotone matching between R and SQ ( ε ) can be partitioned into two sets 206 A− ( ε ) and A+ ( ε ) formed by the pairs of matched points ( i, j ) where xi< tj ( ε ) and xi≥tj ( ε ), 207 respectively. The matching in Figure 1(b) gives rise to sets A− ( ε ) = { (1 , 1) , (3 , 2) , (5 , 4) , (6 , 4) , (8 , 6) }208 and A+ ( ε ) = { (1 , 2) , (3 , 4) , (4 , 7) , (5 , 8) } . We call the values of ε > 0 where the sets A− and A+ may 209 change according the t -monotone matching definition events. There are three different types of 210 events (see Figure 4):211 7 Type 1. tj ( ε ) = xi : In this case, the pair ( i, j )disappears from A+ and enters in A− . That is, for a small enough value δε: A+(ε) = A+(ε−δε)\ {(i, j)},and A−(ε) = A(ε−δε)∪ {(i, j)}. Type 2. tj(ε)+tj+1(ε) 2 = xi : The pair ( i, j + 1) disappears from A− and ( i, j )enters in A+ . That is, A+(ε) = A+(ε−δε)∪ {(i, j)},and A−(ε) = A−(ε−δε)\ {(i, j + 1)}. In addition to the changes in A−and A+, we point out the following:212  If Qj was an unmatched point in SQ ( ε−δε ); that is, it was not the t -monotone nearest 213 point from any R , then it was matched with its t -monotone nearest point among Ri−1 and 214 Ri . If Qj was matched with Ri , then ( i, j ) is already in A+ ( ε ) (i.e., A+ ( ε ) = A+ ( ε−δε )). 215 If Qj was matched with Ri−1 (i.e., ( i− 1 , j ) ∈A− ( ε−δε )), then when ( i, j )enters A+ ( ε ) 216 the pair (i−1, j) must disappear from A−(ε).217  Also, note that Qj+1 may become unmatched when ( i, j + 1) disappears from A− ( ε ) (i.e., 218 xi+1 > tj+1 ( ε + δε ) and Qj+2 is t -monotone nearer to Ri+1 than Qj+1 ). In this case Qj+1 219 must be matched with its t -monotone nearest point, Ri or Ri+1 . If Ri is t -monotone 220 nearer to Qj+1 than Ri+1 , then ( i, j + 1) must remain in A− ( ε ). Otherwise, ( i + 1 , j + 1) 221 must enter A+.222 Type 3. tj ( ε ) = xi+xi+1 2 and in SQ ( ε ), Qj is not the nearest t -coordinate point from any R note (i.e., Qj−1 and Qj+1 are t -monotone nearer to Ri and Ri+1 , respectively, than Qj ): The pair (i, j)disappears from A−(ε) and (i+ 1, j)enters in A+(ε). That is, A+(ε) = A+(ε−δε)∪ {(i+ 1, j)},and A−(ε) = A−(ε−∆ε)\ {(i, j)}. tj(ε) xi qj pi tj(ε) xi tj+1(ε) (tj(ε) + tj+1(ε))/2 ... qj pi qj+1 tj−1 a) b) c) ... xi=tj(ε) tj tj+1 xi xi+1 qj−1 pi pi+1 qj qj+1 ... (xi+xi+1)/2 Figure 4: Events of a) type 1, b) type 2, and c) type 3. Note that when no events occur for a small enough value δε , the set of pairs does not change; 223 i.e., A− ( ε−δε ) = A− ( ε + δε ) and A+ ( ε−δε ) = A+ ( ε + δε ). Thus, we denote the sets A− and 224 A+ between two consecutive events ε` and ε`+1 , A− ` (resp. A+ ` ) the set A− ( ε ) (resp. A+ ( ε )), for all 225 ε∈(ε`, ε`+1). Moreover, the costs related to pairs in A− `(resp. A+ `) increase (resp. decrease).226 8 Lemma 8. The ordered sequence of events ε1< ε2<· · · < ε`< ε`+1 <· · · with the pairs of 227 disappearing and entering matched points involved can be computed in O(nm log m)time.228 Proof. For every note Qj in Q we can sweep R from left to right with a vertical line starting at 229 tj and compute an ordered sequence ε1< ε2< . . . of scaling events, such that tj ( ε` ) = xi (type 1 230 event) or tj ( ε` )=( xi + xi+1 ) / 2 (type 3 event). Notice that for each ε` scaling event detected when 231 sweeping R , we can compute the set of disappearing and entering pairs by analysing a constant 232 number of notes (of R and SQ ( ε` )) around tj ( ε` ). This processing takes O ( n ) for each note in Q . In 233 total we get mordered sequences (one per note in Q) in O(nm) time.234 Analogously to this sweeping, for every vertical bisector between two notes Qj and Qj+1 , we 235 can sweep R from left to right with a vertical line starting at ( tj + tj+1 ) / 2 and compute an ordered 236 sequence ε1< ε2< . . . of scaling events such that ( tj ( ε` ) + tj+1 ( ε` )) / 2 = xi (type 2 event). As 237 before, we can compute the set of disappearing and entering pairs for every ε` in constant time. 238 This processing takes O ( n ) for each pair of consecutive notes in Q . In total we get m− 1 ordered 239 sequences in O(nm) time.240 After all the sweeping processes are completed, we have O ( m ) ordered sequences of length O ( n ). 241 We can merge all these sequences into a single ordered sequence of events in O ( nm log m ) time. 242 Lemma 9. The cost φ(R, SQ(ε)) is a linear function between two consecutive events.243 Proof. Let ε`< ε < ε0< ε`+1, where ε`, ε`+1 are consecutive events. φ(R, SQ(ε)) = X (i,j)∈A− ` (tj(ε)−xi) + X (i,j)∈A+ ` (xi−tj(ε)) + X (i,j)∈A− `∪A+ ` |pi−qj|. Now, using that tj(ε0) = tj(ε) + (2j−1)(ε0−ε)/2, we get that244 φ(R, SQ(ε0)) = φ(R, SQ(ε)) + (ε0−ε) 2  X (i,j)∈A− ` (2j−1) −X (i,j)∈A+ ` (2j−1)  ,(2) and the result follows.245 We are ready to introduce the main result of this section.246 Theorem 10. Problem 2 can be solved in O(nm log m)time.247 Proof. From Lemma 9, we have that the minimum value for φ ( R, SQ ( ε )) is attained at some value of 248 the sequence ε0 = 0 ≤ε1< ε2<· · · < ε`< ε`+1 <· · · , where ε0 represents the initial t -monotone 249 matching between R and Q . Note that the piecewise linear function φ can be discontinuous at the 250 events and the solution is then found by evaluating the cost at the endpoints of each piece. See 251 Figure 5 for an illustration. At events of type 1, the cost function is continuous but for type 2 and 252 type 3, it may not be.253 The algorithm is as follows. First, compute the sequence of events ε1< ε2<· · · < ε`< . . . with 254 the set of entering and disappearing pairs in each event (this can be done in O ( nm log m ) time; 255 Lemma 8). We know that φ ( R, SQ ( ε )) is a piecewise linear function (Lemma 9), so we conveniently 256 denote by φ` ( ε ) the piece of φ ( R, SQ ( ε )) between ε` and ε`+1 for all `≥ 0 (see Figure 5). Note that 257 φ(R, SQ(ε)) = φ`(ε) if ε`< ε < ε`+1, min{φ`−1(ε`), φ`(ε`)}if ε=ε`.(3) 9 Lemma 28. Fix a value 1 ≤i≤n . Assume that tables Ai and Ti are already computed. Assume that the i -th row of tables A∗ and T∗ are already computed as well. Then tables Ai+1 and Ti+1 can be obtained as follows: Ai+1[j, p] = min{Ai[j, p] + A(p), A∗[i, j −1]} Ti+1[j, p] = Ti[j, p]if Ai[j, p] + A(p)≤A∗[i, j −1], iotherwise, where A(p) denotes the area between the segment [ xi, xi+1 ]of R and the last compressing segment 423 with pitch p, (i.e., A(p)=|p−R(xi)| · (xi+1 −xi))424 Proof. Let C be the melody with minimum difference in area from R←−− xi+1 formed by j segments 425 starting at time x0 and ending at time xi+1 whose last segment has pitch p∈P and starts at some 426 time x∈Xwith x<xi+1.427 If the last segment of C starts at time xi0< xi , then the difference in area between C←− xi and R←− xi 428 is Ai [ j, p ]. Therefore, the difference in area between C and R←−− xi+1 is Ai+1 [ j, p ] = Ai [ j, p ] + A(p) and 429 its last segment starts at time Ti+1 [ j, p ] = Ti [ j, p ] = i0 . In this case, the last segment of the previous 430 compression is extended to xi+1.431 If the last segment of C starts at time xi , then obviously Ti+1 [ j, p ] = i . Moreover, by Lemma 23 432 we have that C←− xi is a ( j− 1)-compression of R←− xi with minimum difference in area A∗ [ i, j − 1]. 433 Therefore, the difference in area between C and R←−− xi+1 is Ai+1 [ j, p ] = A∗ [ i, j − 1] and the result 434 follows.435 Using Corollary 27 and Lemma 28 we are ready to implement a dynamic programming algorithm 436 to fill tables A∗ , T∗ and H∗ , from which we can obtain the k -compression with minimum difference 437 in area.438 Theorem 29. An optimum k -compressed melody of R can be found in O ( kρn )time and using 439 O ( kn )memory space, where n is the number of segments in melody R and ρ is the number of 440 different pitch values of the segments in R.441 Proof. Note that the size of tables Ti and Ai is O ( kρ ), and computing a cell of these tables takes 442 constant time assuming that the values of tables Ti−1 and Ai−1 as well as the values of the cells in 443 the (i−1)-th row of T∗,A∗and H∗are known.444 Now, the size of tables T∗ , A∗ and H∗ is O ( kn ) and computing a cell of the i -th row of these 445 tables takes O ( ρ ) time assuming that we already know the values of tables Ti and Ai . Since we 446 need to repeat the process for i= 1, . . . , n, the total computation time is O(kρn).447 Note that the difference in area from the optimal k -compression is in A∗ [ k, n ] and it can be 448 obtained in O(k) time by navigating backwards using the tables T∗and H∗(i.e., the last segment449 starts at xik time where T∗ [ k, n ] = ik and its pitch is H∗ [ k, n ], the ( k− 1)-th segment starts at xik−1 450 time where T∗[k−1, ik] = ik−1and its pitch is H∗[k, ik], etc.).451 Finally, tables A1, A2, . . . , An can be modeled as a single table of size k×ρ that updates its cell 452 values for i = 1 , 2 ...,n . The same occurs for T1, T2, . . . , Tn . Then these two sequences of tables can 453 be modeled using two single tables of size k×ρ , which require O ( kρ ) memory space. Tables T∗ , A∗ 454 and H∗requires O(kn) memory space. Taking into account that ρ≤n, the result follows.455 16 4 Conclusions456 In this work, we developed efficient algorithms for two geometric problems that arise in MIR; linear 457 scaling and data compression. The geometric nature of the problem comes from the use of two 458 geometric metrics to measure the similarity between two melodies. Our algorithms take advantage 459 of the properties of an optimal solution and are based on line sweeping and dynamic programming 460 techniques. For a segment representation of the melodies, we considered the difference in area 461 between the melodic contours and for the point representation we introduced a constrained matching, 462 the t -monotone matching, in which a point of a melody is assigned to its neighbor to the left or to 463 the right of the other melody. Both difference in area and geometric matching have been considered 464 in the literature.465 Our future work will concentrate on experiments with real music data to explore the behavior 466 of these similarity measures. In the experiments, the definition in the scaling operation can be 467 extended by considering a different way of increasing the lengths of the segments. For example, in 468 an ε -scaling, instead of increasing ε the lengths of all segments, we could increase each segment 469 by αε , where the parameter α∈ [0 , 1] depends on the length of the segment. For the compression 470 problem, we plan to explore the accuracy, flexibility and speed of of our techniques for clustering 471 and classification tasks.472 Acknowledgment. This work was initiated at the VIII Spanish Workshop on Geometric Opti- 473 mization, El Roc´ıo, Huelva, Spain, June 20–24, 2016. We thank all participants in the workshop, 474 especially Jorge Urrutia, for helpful discussions and their contribution to a creative atmosphere.475 References476 [1] G. Toussaint, Computational geometric aspects of rhythm, melody, and voice-leading, Compu- 477 tational Geometry 43 (1) (2010) 2–22.478 [2] L. Barba, L. E. Caraballo, J. M. D´ıaz-B´a˜nez, R. Fabila-Monroy, E. P´erez-Castillo, Asymmetric 479 polygons with maximum area, European Journal of Operational Research 248 (3) (2016) 480 1123–1131.481 [3] S. Bereg, J.-M. D´ıaz-B´a˜nez, N. Kroher, I. Ventura, Computing melodic templates in oral music 482 traditions, Applied Mathematics and Computation 344 (2019) 219–229.483 [4] R. Clifford, M. Christodoulakis, T. Crawford, D. Meredith, G. A. Wiggins, A fast, randomised, 484 maximal subset matching algorithm for document-level music retrieval., in: ISMIR, 2006, pp. 485 150–155.486 [5] D. O. Maid´ın, A geometrical algorithm for melodic difference, Computing in musicology: a 487 directory of research (11) (1998) 65–72.488 [6] W. Cao, D. Jiang, J. Hou, Y. Qin, T. F. Zheng, Y. Liu, A phrase-level piecewise linear 489 scaling algorithm for melody match in query-by-humming systems, in: 2009 IEEE International 490 Conference on Multimedia and Expo, IEEE, 2009, pp. 942–945.491 [7] J.-S. R. Jang, H.-R. Lee, M.-Y. K., Content-based music retrieval using linear scaling and 492 branch-and-bound tree search, in: IEEE International Conference on Multimedia and Expo, 493 2001. ICME 2001., 2001, pp. 74–74.494 17 [8] R. Cilibrasi, P. Vit´anyi, R. d. Wolf, Algorithmic clustering of music based on string compression, 495 Computer Music Journal 28 (4) (2004) 49–67.496 [9] I. Suyoto, A. L. Uitdenbogerd, F. Scholer, Searching musical audio using symbolic queries, 497 IEEE Transactions on Audio, Speech, and Language Processing 16 (2) (2008) 372–381.498 [10] D. Byrd, T. Crawford, Problems of music information retrieval in the real world, Information 499 processing & management 38 (2) (2002) 249–272.500 [11] M. Mongeau, D. Sankoff, Comparison of musical sequences, Computers and the Humanities 501 24 (3) (1990) 161–175.502 [12] M. Robine, P. Hanna, P. Ferraro, Music similarity: Improvements of edit-based algorithms 503 by considering music theory, in: Proceedings of the international workshop on Workshop on 504 multimedia information retrieval, 2007, pp. 135–142.505 [13] J. Mora, F. G´omez, E. G´omez, J. M. D´ıaz-B´a˜nez, Melodic contour and mid-level global features 506 applied to the analysis of flamenco cantes, Journal of New Music Research 45 (2) (2016) 507 145–159.508 [14] G. Aloupis, T. Fevens, S. Langerman, T. Matsui, A. Mesa, Y. Nu˜nez, D. Rappaport, G. Tous- 509 saint, Algorithms for computing geometric measures of melodic similarity, Computer Music 510 Journal 30 (3) (2006) 67–76.511 [15] H.-J. Lin, H.-H. Wu, Y.-T. Kao, Geometric measures of distance between two pitch contour 512 sequences, Journal of Computers 19 (2) (2008) 44–66.513 [16] H.-J. Lin, H.-H. Wu, Efficient geometric measure of music similarity, Information processing 514 letters 109 (2) (2008) 116–120.515 [17] T. Painter, A. Spanias, Perceptual coding of digital audio, Proceedings of the IEEE 88 (4) 516 (2000) 451–515.517 [18] G. Tzanetakis, F. Cook, Sound analysis using mpeg compressed audio, in: 2000 IEEE In- 518 ternational Conference on Acoustics, Speech, and Signal Processing. Proceedings (Cat. No. 519 00CH37100), Vol. 2, IEEE, 2000, pp. II761–II764.520 [19] E. Ravelli, G. Richard, L. Daudet, Audio signal representations for indexing in the transform521 domain, IEEE Transactions on Audio, Speech, and Language Processing 18 (3) (2010) 434–446. 522 [20] A. Ben-Dor, R. M. Karp, B. Schwikowski, R. Shamir, The restriction scaffold problem, Journal 523 of Computational Biology 10 (3-4) (2003) 385–398.524 [21] G. Toussaint, The geometry of musical rhythm, in: Japanese Conference on Discrete and 525 Computational Geometry, Springer, 2004, pp. 198–212.526 [22] T. Eiter, H. Mannila, Distance measures for point sets and their computation, Acta informatica 527 34 (2) (1997) 109–133.528 [23] N. Megiddo, K. J. Supowit, On the complexity of some common geometric location problems, 529 SIAM journal on computing 13 (1) (1984) 182–196.530 18