Abstract
This paper introduces the problem of discovering maximum-length repeating patterns in music objects. A novel algorithm is presented for the extraction of this kind of patterns from a melody music object. The proposed algorithm discovers all maximum-length repeating patterns using an “aggressive” accession during searching, by avoiding costly repetition frequency calculation and by examining as few as possible repeating patterns in order to reach the maximum-length repeating pattern(s). Detailed experimental results illustrate the significant performance gains due to the proposed algorithm, compared to an existing baseline algorithm.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Agrawal R, Srikant R (1995) Mining sequential patterns. In: Proceedings of the 11th IEEE international conference on data engineering (ICDE), Taipei, Taiwan, pp 3–14
Alghoniemy M, Tewfik AH (2000) User-defined music sequence retrieval. In: Proceedings of the 8th ACM international conference on multimedia, Los Angeles, CA, pp 356–358
Aucouturier J-J, Sandler M (2002) Finding repeating patterns in acoustic musical signals: applications for audio thumbnailing. In: Proceedings 22nd AES international conference on virtual, synthetic and entertainment audio, Espoo, Finland, pp 412–421
Bainbridge D, Bernbom G, Davidson MW, Dillon AP, Dovey M, Dunn JW, Fingerhut M, Fujinaga I, Isaacson EJ (2001) Digital music libraries—research and development. In: Proceedings of the 1st ACM/IEEE joint conference on digital libraries (JCDL), Roanoke, VA, pp 446–448
Barlow H, Morgenstern S (1975) A dictionary of musical themes. Crown, New York
Bartsch M, Birmingham WP, Bykowski D, Dannenberg RB, Mazzoni D, Meek C, Mellody M, Rand W, Wakefield GH, (2001) MUSART: music retrieval via aural queries. In: Proceedings of the 2nd annual international symposium on music information retrieval (ISMIR), Bloomington, IN, pp 73–81
Bayardo R (1998) Efficiently mining long patterns from databases. In: Proceedings of the ACM international conference on management of data (SIGMOD), Seattle, WA, pp 85–93
Byrd D, Crawford T (2002) Problems of music information retrieval in the real world. Inf Process Manag 38(2):249–272
Chavez E, Navarro G (2002) A metric index for approximate string matching. In: Proceedings of the 5th Latin American symposium on theoretical informatics (LATIN), New York, NY, pp 181–195
Chen ALP, Chang M, Chen J, Hsu J, Hsu C, Hua YS (2000) Query by music segments: an efficient approach for song retrieval. In: Proceedings of the IEEE international conference on multimedia and expo, New York, NY pp 873–876
Chen JCC, Chen ALP (1998) Query by rhythm: an approach for song retrieval in music databases. In: Proceedings of the workshop on research issues in data engineering (RIDE), Tucson, AZ, pp 139–146
Chen H, Chen ALP (2001) A music recommendation system based on music data grouping and user interests. In: Proceedings of the conference in information and knowledge management (CIKM), Hilton, Singapore, pp 231–238
Chuo T-C, Chen ALP, Liu C-C, (1996) Music DataBases: indexing techniques and implementation. In: Proceedings of the international workshop on multimedia databases management systems, Blue Mountain Lake, NY, pp 46–53
Crawford T, Iliopoulos CS, Raman R (1998) String matching techniques for music similarity and melodic recognition. Comput Musicol 11:73–100
Dovey MJ (2001) Adding content-based searching to a traditional music library catalogue server. In: Proceedings of the 1st ACM/IEEE joint conference on digital libraries (JCDL), Roanoke, VA, pp 249–250
Durey AS, Clements MA (2001) Melody spotting using hidden Markov models. In: Proceedings of the 2nd annual international symposium on music information retrieval (ISMIR), Berkeley, CA, pp 109–117
Francu C, Nevill-Manning CG (2000) Distance metrics and indexing strategies for a digital library of popular music. In: Proceedings of the IEEE international conference on multimedia and expo, New York, NY, pp 889–894
Hamilton JD (1994) Time series analysis. Princeton University Press, Princeton, NJ
Hsu J, Liu C, Chen ALP (1998) Efficient repeating pattern finding in music databases. In: Proceedings of the ACM international conference on information and knowledge management (CIKM), Bethesda, MD
Hsu JL, Liu CC, Chen ALP (2001) Discovering non-trivial repeating patterns in music data. IEEE Trans Multimedia 3(3):311–325
Iliopoulos CS, Kurokawa M (2002) Exact & approximate distributed matching for musical melodic recognition. In: Proceedings of the convention on artificial intelligence and the simulation of behaviour (AISB). Imperial College, London, UK, pp 49–56
Iliopoulos CS, Niyad M, Lenstrom K, Pinzon YJ (2002) Evolution of musical motifs in polyphonic passages. In: Proceedings of the convention on artificial intelligence and the simulation of behaviour (AISB). Imperial College, London, pp 67–75
Kang YK, Kim YS, Ku KI (2001) Extracting theme melodies by using a graphical clustering algorithm for content-based MIR. In: Proceedings of the 5th East-European conference on advances in databases and information systems (ADBIS), Springer-Verlag, London, pp 84–97
Kassler M (1966) Toward musical information retrieval. Perspect New Music 4(2):59–67
Koh JL, Yu WDC (2001) Efficient feature mining in music objects. In: Proceedings of the 12th conference in database and expert system applications (DEXA), London, UK, pp 221–231
Kornstadt A (1998) Themefinder: a web-based melodic search tool. Comput Musicol 11:231–236
Lin D-I, Kedem Z (2002) Pincer-search: an efficient algorithm for discovering the maximum frequent set. IEEE Trans Knowl Data Eng 14(3):553–566
Liu CC, Hsu JL, Chen ALP (1999) Efficient theme and non-trivial repeating pattern discovering in music databases. In: Proceedings of the 15th IEEE international conference on data engineering (ICDE), Sydney, Australia, pp 14–21
Meek C, Birmingham WP (2001) Thematic extractor. In: Proceedings of the 2nd annual international symposium on music information retrieval (ISMIR), Bloomington, IN, pp 119–128
Mongeau M, Sankoff D (1990) Comparison of musical sequences. Comput Humanit 24:161–175
Nishimura T, Hashiguchi H, Takita J, Zhang JX, Goto M, Oka R (2001) Music signal spotting retrieval by a humming query suing start frame feature dependent continuous dynamic programming. In: Proceedings of the 2nd annual international symposium on music information retrieval (ISMIR), Bloomington, IN, pp 211–218
O’Maidin DS, Cahill M (2001) Score processing for MIR. In: Proceedings of the 2nd annual international symposium on music information retrieval (ISMIR), Bloomington, IN, pp 59–64
Park J, Chen M-S, Yu P (1997) Using a hash-based method with transaction trimming for mining association rules. IEEE Trans Knowl Data Eng 9(5):813–825
Pienimaki A (2002) Indexing music databases using automatic extraction of frequent phrases. In: Proceedings of the 3nd annual international symposium on music information retrieval (ISMIR), Paris, France, pp 25–30
Pikrakis A, Theodoridis S, Kamarotos D (2002) Recognition of isolated musical patterns using hidden markov models. In: Proceedings of the II international conference on music and artificial intelligence (ICMAI), Edinburg, Scotland, pp 133–143
Raphael C (2001) Automated rhythm transcription. In: Proceedings of the 2nd annual international symposium on music information retrieval (ISMIR), Bloomington, IN, pp 99–107
Rolland P-Y, Ganascia J-G (2002) Pattern detection and discovery: the case of music data mining. In: Proceedings of the conference on pattern detection and discovery, London, UK, pp 190–198
Shifrin J, Pardo B, Meek C, Birmingham W (2002) HMM-based musical query retrieval. In: Proceedings of the 2nd ACM/IEEE-CS conference on digital libraries, Portland, OR, pp 295–300
Smith L, Medina R (2001) Discovering themes by exact pattern matching. In: Proceedings of the 2nd annual international symposium on music information retrieval (ISMIR), Bloomington, IN, pp 31–32
Takasu A, Yanase T, Kanazawa T, Adachi J (1999) Music structure analusis and its application to theme phrase extraction. In: Third European conference on research and advanced technology for digital libraries, Paris, France, pp 92–105
Uitdenbogerd A, Zobel J (1999) Melodic matching techniques for large music databases. In: Proceedings of the ACM international multimedia conference, Orlando, FL, pp 57–66
Velivelli A, Zhai C, Huang TS (2003) Audio segment retrieval using a synthesized HMM. In: Proceedings of the ACM SIGIR workshop on multimedia information retrieval, Toronto, Canada
Zaki M, Parthasarathy S, Ogihara M, Li W (1997) New algorithms for fast discovery of association rules. In: Proceedings of the international conference on knowledge discovery and data mining (KDD), Menlo Park, CA, pp 283–286
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Karydis, I., Nanopoulos, A. & Manolopoulos, Y. Finding maximum-length repeating patterns in music databases. Multimed Tools Appl 32, 49–71 (2007). https://doi.org/10.1007/s11042-006-0068-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11042-006-0068-5