Necklace swap problem for rhythmic similarity measures

Yoan José Pinzó Ardila; Raphaël Clifford; Costas S. Iliopoulos; Gad M. Landau; Manal Mohamed

doi:10.1142/S0219876208001583

Necklace swap problem for rhythmic similarity measures

Yoan José Pinzó Ardila, Raphaël Clifford, Costas S. Iliopoulos, Gad M. Landau, Manal Mohamed

חוג למדעי המחשב

פרסום מחקרי: פרסום בכתב עת › מאמר › ביקורת עמיתים

תקציר

Given two n-bit (cyclic) binary strings, A and B, represented on a circle (necklace instances), let each sequence have the same number (k) of 1's. We are interested in computing the cyclic swap distance between A and B, i.e. the minimum number of swaps needed to convert A to B, minimized over all possible rotations of B. We show that, given the compressed representation of A and B, this distance may be computed in O(k²).

שפה מקורית	אנגלית אמריקאית
עמודים (מ-עד)	351-363
מספר עמודים	13
כתב עת	International Journal of Computational Methods
כרך	5
מספר גיליון	3
מזהי עצם דיגיטלי (DOIs)	https://doi.org/10.1142/S0219876208001583
סטטוס פרסום	פורסם - 2008

הערה ביבליוגרפית

Funding Information:
∗Partially supported by the Israel Science Foundation grant 35/05.

ASJC Scopus subject areas

???subjectarea.asjc.1700.1701???
???subjectarea.asjc.2600.2605???

גישה למסמך

10.1142/S0219876208001583

קבצים וקישורים אחרים

Link to publication in Scopus

פורמט ציטוט ביבליוגרפי

@article{d8f3a991b4a045f08178bd32f3de587b,

title = "Necklace swap problem for rhythmic similarity measures",

abstract = "Given two n-bit (cyclic) binary strings, A and B, represented on a circle (necklace instances), let each sequence have the same number (k) of 1's. We are interested in computing the cyclic swap distance between A and B, i.e. the minimum number of swaps needed to convert A to B, minimized over all possible rotations of B. We show that, given the compressed representation of A and B, this distance may be computed in O(k2).",

keywords = "Cyclic strings, Music retrieval, Repeated patterns, Rhythmic/melodic similarity, Swap distance",

author = "Ardila, {Yoan Jos{\'e} Pinz{\'o}} and Rapha{\"e}l Clifford and Iliopoulos, {Costas S.} and Landau, {Gad M.} and Manal Mohamed",

note = "Funding Information: ∗Partially supported by the Israel Science Foundation grant 35/05.",

year = "2008",

doi = "10.1142/S0219876208001583",

language = "English",

volume = "5",

pages = "351--363",

journal = "International Journal of Computational Methods",

issn = "0219-8762",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "3",

}

TY - JOUR

T1 - Necklace swap problem for rhythmic similarity measures

AU - Ardila, Yoan José Pinzó

AU - Clifford, Raphaël

AU - Iliopoulos, Costas S.

AU - Landau, Gad M.

AU - Mohamed, Manal

N1 - Funding Information: ∗Partially supported by the Israel Science Foundation grant 35/05.

PY - 2008

Y1 - 2008

N2 - Given two n-bit (cyclic) binary strings, A and B, represented on a circle (necklace instances), let each sequence have the same number (k) of 1's. We are interested in computing the cyclic swap distance between A and B, i.e. the minimum number of swaps needed to convert A to B, minimized over all possible rotations of B. We show that, given the compressed representation of A and B, this distance may be computed in O(k2).

AB - Given two n-bit (cyclic) binary strings, A and B, represented on a circle (necklace instances), let each sequence have the same number (k) of 1's. We are interested in computing the cyclic swap distance between A and B, i.e. the minimum number of swaps needed to convert A to B, minimized over all possible rotations of B. We show that, given the compressed representation of A and B, this distance may be computed in O(k2).

KW - Cyclic strings

KW - Music retrieval

KW - Repeated patterns

KW - Rhythmic/melodic similarity

KW - Swap distance

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

U2 - 10.1142/S0219876208001583

DO - 10.1142/S0219876208001583

M3 - Article

AN - SCOPUS:54949102846

VL - 5

SP - 351

EP - 363

JO - International Journal of Computational Methods

JF - International Journal of Computational Methods

SN - 0219-8762

IS - 3

ER -

Necklace swap problem for rhythmic similarity measures

תקציר

הערה ביבליוגרפית

ASJC Scopus subject areas

גישה למסמך

קבצים וקישורים אחרים

Fingerprint

פורמט ציטוט ביבליוגרפי