A bit-parallel suffix automaton approach for (delta, gamma)-matching in music retrieval

M A Nascimento, E S DeMoura, A L Oliveira (Editor), Y J Pinzon

Research output: Chapter in Book/Report/Conference proceedingConference paper

Abstract

(delta, gamma)-Matching is a string matching problem with applications to music retrieval. The goal is, given a pattern P-1...m and a text T-1...n on an alphabet of integers, find the occurrences P' of the pattern in the text such that (i) For All1 less than or equal to i less than or equal to m, \P-i - P-i'\ less than or equal to delta, and (ii) Sigma(1less than or equal toiless than or equal tom) \P-i - P-i'\ less than or equal to gamma. Several techniques for (delta, gamma)-matching have been proposed. In this paper we show that a classical string matching technique that combines bit-parallelism and suffix automata can be successfully adapted to this problem. This is the first character-skipping algorithm that skips characters using both delta and gamma. We implemented our algorithm and drew experimental results on real music showing that our algorithm is superior to current alternatives.
Original languageEnglish
Title of host publicationLECT NOTE COMPUT SCI
Place of PublicationBERLIN
PublisherSpringer
Pages211 - 223
Number of pages13
ISBN (Print)3-540-20177-7
Publication statusPublished - 2003
Event10th International Symposium on String Processing and Information Retrieval - MANAUS, Brazil
Duration: 1 Jan 2003 → …

Publication series

NameLECTURE NOTES IN COMPUTER SCIENCE

Conference

Conference10th International Symposium on String Processing and Information Retrieval
Country/TerritoryBrazil
CityMANAUS
Period1/01/2003 → …

Fingerprint

Dive into the research topics of 'A bit-parallel suffix automaton approach for (delta, gamma)-matching in music retrieval'. Together they form a unique fingerprint.

Cite this