A tone data processing apparatus comprising: a storage section storing therein tone data sets, each representative of a plurality of sounds in a predetermined time period, and tone rhythm patterns, each representative of a series of sound generation times of the plurality of sounds, in association with each other, said storage section further storing therein categories of rhythms, determined on the basis of the sound generation time intervals represented by the tone rhythm patterns, in association with the tone rhythm patterns; an acquisition section which, on the basis of operation input by a user, acquires an input rhythm pattern representative of a series of designated time points corresponding to a pattern of the operation input by the user; a determination section which, on the basis of intervals between the designated time points represented by the input rhythm pattern, determines a category of rhythm the inputs rhythm pattern belongs to; a calculation section which calculates a distance between the input rhythm pattern and each of the tone rhythm patterns, and a search section which calculates a degree of similarity between the input rhythm pattern and each of the tone rhythm patterns on the basis of the distance calculated by said calculation section and relationship between the category of rhythm the input rhythm pattern belongs to and a category of rhythm the tone rhythm pattern belongs to, and searches the tone data sets stored in said storage section for a tone data set associated with a tone rhythm pattern of which the calculated degree of similarity to the input rhythm pattern satisfies a predetermined condition. a storage section storing therein tone data sets, each representative of a plurality of sounds in a predetermined time period, and tone rhythm patterns, each representative of a series of sound generation times of the plurality of sounds, in association with each other, said storage section further storing therein categories of rhythms, determined on the basis of the sound generation time intervals represented by the tone rhythm patterns, in association with the tone rhythm patterns; an acquisition section which, on the basis of operation input by a user, acquires an input rhythm pattern representative of a series of designated time points corresponding to a pattern of the operation input by the user; a determination section which, on the basis of intervals between the designated time points represented by the input rhythm pattern, determines a category of rhythm the inputs rhythm pattern belongs to; a calculation section which calculates a distance between the input rhythm pattern and each of the tone rhythm patterns, and a search section which calculates a degree of similarity between the input rhythm pattern and each of the tone rhythm patterns on the basis of the distance calculated by said calculation section and relationship between the category of rhythm the input rhythm pattern belongs to and a category of rhythm the tone rhythm pattern belongs to, and searches the tone data sets stored in said storage section for a tone data set associated with a tone rhythm pattern of which the calculated degree of similarity to the input rhythm pattern satisfies a predetermined condition.