RECURSIA-RRT: Recursive translatable point-set pattern discovery with removal of redundant translators

David Meredith

doi:10.1007/978-3-030-43887-6_42

RECURSIA-RRT: Recursive translatable point-set pattern discovery with removal of redundant translators

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

1 Citation (Scopus)

12 Downloads (Pure)

Abstract

We introduce two algorithms, RecurSIA and RRT, designed to increase the compression factor achievable using point-set cover algorithms based on the SIA and SIATEC pattern discovery algorithms. SIA computes the maximal translatable patterns (MTPs) in a point set, while SIATEC computes the translational equivalence class (TEC) of every MTP in a point set, where the TEC of an MTP is the set of translationally invariant occurrences of that MTP in the point set. In its output, SIATEC encodes each MTP TEC as a pair, ⟨P,V⟩, where P is the first occurrence of the MTP and V is the set of non-zero vectors that map P onto its other occurrences. RecurSIA recursively applies a TEC cover algorithm to the pattern P, in each TEC, ⟨P,V⟩, that it discovers. RRT attempts to remove translators from V in each TEC without reducing the total set of points covered by the TEC. When evaluated with COSIATEC, SIATECCompress and Forth’s algorithm on the JKU Patterns Development Database, using RecurSIA with or without RRT increased compression factor and recall but reduced precision. Using RRT alone increased compression factor and reduced recall and precision, but had a smaller effect than RecurSIA.

Original language	English
Title of host publication	Machin Learning and Knowledge Discovery in Databases : International Workshops of ECML PKDD 2019 Würzburg, Germany, September 16–20, 2019 Proceedings, Part II
Editors	Peggy Cellier, Kurt Driessens
Number of pages	9
Volume	1168
Place of Publication	Cham, Switzerland
Publisher	Springer
Publication date	2020
Pages	485-493
ISBN (Print)	978-3-030-43886-9
ISBN (Electronic)	978-3-030-43887-6
DOIs	https://doi.org/10.1007/978-3-030-43887-6_42
Publication status	Published - 2020
Event	International Workshop on Machine Learning and Music - Würzburg, Germany Duration: 16 Sept 2019 → 16 Sept 2019 Conference number: 12 https://musml2019.weebly.com/

Conference

Conference	International Workshop on Machine Learning and Music
Number	12
Country/Territory	Germany
City	Würzburg
Period	16/09/2019 → 16/09/2019
Internet address	https://musml2019.weebly.com/

Series	Communications in Computer and Information Science
Volume	1168
ISSN	1865-0929

Keywords

COSIATEC
Data compression
Forth’s algorithm
Geometric pattern discovery in music
Music analysis
Pattern discovery
Point sets
SIATEC
SIATECCompress

Access to Document

10.1007/978-3-030-43887-6_42Licence: Unspecified

MeredithRecurSIAMML2019Accepted author manuscript, 234 KB

https://arxiv.org/pdf/1906.12286.pdf

AUB Link

Search for the material in Aalborg University Library's search engine

Cite this

Meredith, D. (2020). RECURSIA-RRT: Recursive translatable point-set pattern discovery with removal of redundant translators. In P. Cellier, & K. Driessens (Eds.), Machin Learning and Knowledge Discovery in Databases: International Workshops of ECML PKDD 2019 Würzburg, Germany, September 16–20, 2019 Proceedings, Part II (Vol. 1168, pp. 485-493). Springer. Communications in Computer and Information Science Vol. 1168 https://doi.org/10.1007/978-3-030-43887-6_42

Meredith, David. / RECURSIA-RRT : Recursive translatable point-set pattern discovery with removal of redundant translators. Machin Learning and Knowledge Discovery in Databases: International Workshops of ECML PKDD 2019 Würzburg, Germany, September 16–20, 2019 Proceedings, Part II. editor / Peggy Cellier ; Kurt Driessens. Vol. 1168 Cham, Switzerland : Springer, 2020. pp. 485-493 (Communications in Computer and Information Science, Vol. 1168).

@inproceedings{7756f9431cca4e4d9c36b1a9860f3bc0,

title = "RECURSIA-RRT: Recursive translatable point-set pattern discovery with removal of redundant translators",

abstract = "We introduce two algorithms, RecurSIA and RRT, designed to increase the compression factor achievable using point-set cover algorithms based on the SIA and SIATEC pattern discovery algorithms. SIA computes the maximal translatable patterns (MTPs) in a point set, while SIATEC computes the translational equivalence class (TEC) of every MTP in a point set, where the TEC of an MTP is the set of translationally invariant occurrences of that MTP in the point set. In its output, SIATEC encodes each MTP TEC as a pair, ⟨P,V⟩, where P is the first occurrence of the MTP and V is the set of non-zero vectors that map P onto its other occurrences. RecurSIA recursively applies a TEC cover algorithm to the pattern P, in each TEC, ⟨P,V⟩, that it discovers. RRT attempts to remove translators from V in each TEC without reducing the total set of points covered by the TEC. When evaluated with COSIATEC, SIATECCompress and Forth{\textquoteright}s algorithm on the JKU Patterns Development Database, using RecurSIA with or without RRT increased compression factor and recall but reduced precision. Using RRT alone increased compression factor and reduced recall and precision, but had a smaller effect than RecurSIA.",

keywords = "COSIATEC, Data compression, Forth{\textquoteright}s algorithm, Geometric pattern discovery in music, Music analysis, Pattern discovery, Point sets, SIATEC, SIATECCompress",

author = "David Meredith",

year = "2020",

doi = "10.1007/978-3-030-43887-6_42",

language = "English",

isbn = "978-3-030-43886-9",

volume = "1168",

series = "Communications in Computer and Information Science",

publisher = "Springer",

pages = "485--493",

editor = "Peggy Cellier and Kurt Driessens",

booktitle = "Machin Learning and Knowledge Discovery in Databases",

address = "Germany",

note = "International Workshop on Machine Learning and Music, MML 2019 ; Conference date: 16-09-2019 Through 16-09-2019",

url = "https://musml2019.weebly.com/",

}

Meredith, D 2020, RECURSIA-RRT: Recursive translatable point-set pattern discovery with removal of redundant translators. in P Cellier & K Driessens (eds), Machin Learning and Knowledge Discovery in Databases: International Workshops of ECML PKDD 2019 Würzburg, Germany, September 16–20, 2019 Proceedings, Part II. vol. 1168, Springer, Cham, Switzerland, Communications in Computer and Information Science, vol. 1168, pp. 485-493, International Workshop on Machine Learning and Music, Würzburg, Germany, 16/09/2019. https://doi.org/10.1007/978-3-030-43887-6_42

RECURSIA-RRT: Recursive translatable point-set pattern discovery with removal of redundant translators. / Meredith, David.
Machin Learning and Knowledge Discovery in Databases: International Workshops of ECML PKDD 2019 Würzburg, Germany, September 16–20, 2019 Proceedings, Part II. ed. / Peggy Cellier; Kurt Driessens. Vol. 1168 Cham, Switzerland: Springer, 2020. p. 485-493 (Communications in Computer and Information Science, Vol. 1168).

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

TY - GEN

T1 - RECURSIA-RRT

T2 - International Workshop on Machine Learning and Music

AU - Meredith, David

N1 - Conference code: 12

PY - 2020

Y1 - 2020

N2 - We introduce two algorithms, RecurSIA and RRT, designed to increase the compression factor achievable using point-set cover algorithms based on the SIA and SIATEC pattern discovery algorithms. SIA computes the maximal translatable patterns (MTPs) in a point set, while SIATEC computes the translational equivalence class (TEC) of every MTP in a point set, where the TEC of an MTP is the set of translationally invariant occurrences of that MTP in the point set. In its output, SIATEC encodes each MTP TEC as a pair, ⟨P,V⟩, where P is the first occurrence of the MTP and V is the set of non-zero vectors that map P onto its other occurrences. RecurSIA recursively applies a TEC cover algorithm to the pattern P, in each TEC, ⟨P,V⟩, that it discovers. RRT attempts to remove translators from V in each TEC without reducing the total set of points covered by the TEC. When evaluated with COSIATEC, SIATECCompress and Forth’s algorithm on the JKU Patterns Development Database, using RecurSIA with or without RRT increased compression factor and recall but reduced precision. Using RRT alone increased compression factor and reduced recall and precision, but had a smaller effect than RecurSIA.

AB - We introduce two algorithms, RecurSIA and RRT, designed to increase the compression factor achievable using point-set cover algorithms based on the SIA and SIATEC pattern discovery algorithms. SIA computes the maximal translatable patterns (MTPs) in a point set, while SIATEC computes the translational equivalence class (TEC) of every MTP in a point set, where the TEC of an MTP is the set of translationally invariant occurrences of that MTP in the point set. In its output, SIATEC encodes each MTP TEC as a pair, ⟨P,V⟩, where P is the first occurrence of the MTP and V is the set of non-zero vectors that map P onto its other occurrences. RecurSIA recursively applies a TEC cover algorithm to the pattern P, in each TEC, ⟨P,V⟩, that it discovers. RRT attempts to remove translators from V in each TEC without reducing the total set of points covered by the TEC. When evaluated with COSIATEC, SIATECCompress and Forth’s algorithm on the JKU Patterns Development Database, using RecurSIA with or without RRT increased compression factor and recall but reduced precision. Using RRT alone increased compression factor and reduced recall and precision, but had a smaller effect than RecurSIA.

KW - COSIATEC

KW - Data compression

KW - Forth’s algorithm

KW - Geometric pattern discovery in music

KW - Music analysis

KW - Pattern discovery

KW - Point sets

KW - SIATEC

KW - SIATECCompress

UR - https://arxiv.org/abs/1906.12286

UR - https://github.com/chromamorph/omnisia-recursia-rrt-mml-2019

UR - http://www.scopus.com/inward/record.url?scp=85083658139&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-43887-6_42

DO - 10.1007/978-3-030-43887-6_42

M3 - Article in proceeding

SN - 978-3-030-43886-9

VL - 1168

T3 - Communications in Computer and Information Science

SP - 485

EP - 493

BT - Machin Learning and Knowledge Discovery in Databases

A2 - Cellier, Peggy

A2 - Driessens, Kurt

PB - Springer

CY - Cham, Switzerland

Y2 - 16 September 2019 through 16 September 2019

ER -

Meredith D. RECURSIA-RRT: Recursive translatable point-set pattern discovery with removal of redundant translators. In Cellier P, Driessens K, editors, Machin Learning and Knowledge Discovery in Databases: International Workshops of ECML PKDD 2019 Würzburg, Germany, September 16–20, 2019 Proceedings, Part II. Vol. 1168. Cham, Switzerland: Springer. 2020. p. 485-493. (Communications in Computer and Information Science, Vol. 1168). doi: 10.1007/978-3-030-43887-6_42

RECURSIA-RRT: Recursive translatable point-set pattern discovery with removal of redundant translators

Abstract

Conference

Keywords

Access to Document

AUB Link

Other files and links

Fingerprint

Cite this