Abstract
In this paper, we present the techniques for retrieving songs by segment. The melody contour is categorized into four types. A segment consists of melody contour of one type and the associated beat (note duration) and pitch (note difference) information. The definitions of similarity for the note duration and the note difference capture the similarity among songs. Moreover, the two-dimensional augmented suffix tree is proposed to speed up the search processing. The minimal and maximal values of data recorded in internal node aid the searching process. Moreover, the threshold propagation function is developed for approximate searching.