Querying polyphonic music from a large data collection is an interesting and challenging topic. Recently, researchers attempt to provide efficient techniques for content-based retrieval in polyphonic music databases where queries can also be polyphonic. However, most of the techniques do not perform the approximate matching well. In this paper, we propose three polyphony representations with associated similarity measures and present a novel method to efficiently retrieve k music works that contain segments most similar to the user query based on the edit distance. A list-based index structure of the music database is first constructed for each representation of the polyphony. A set of expanded queries is also generated from the user query, which associates with a set of candidate answers. For each expanded query, the distance between it and the user query is computed, which indicates a lower bound of the distance of the set of candidate answers with the expanded query. From these lower bounds, we propose an efficient approach to retrieve the kNN answers from all candidate answers. A mechanism to eliminate the expanded queries from which no answers can be obtained is also proposed. The efficiency of the proposed method is evaluated by real data set and synthetic data set, reporting a significant improvement over existing approaches in the response time yielded. We also analyze the effectiveness of the approach based on the three representations for the musician and non-musician user groups. The experiment results are useful to the design of the polyphonic music database system.