Recently, the increased competition in song recognition has led to the necessity to identify songs within very huge databases compared to previous years. Therefore, information retrieval technique requires a more efficient and scalable data storage framework. In this work, we propose an approach exploiting K-means clustering and describe strategies for improving accuracy and speed. In collaboration with an audio expert company providing us with 2.4 billion fingerprints data, we evaluated the performance of the proposed clustering and recognition algorithm.