Clustering is an important data analysis tool for discovering structure in data sets. Although research on conceptual clustering has produced algorithms showing significant advantages over earlier numerical ones, existing methods still present some limitations regarding applicability to biomedical domains. In this paper we describe ADAGIO, a conceptual clustering algorithm combining a low-cost preordering process with a breadth-first incremental control strategy that incorporates merging and splitting operators. Experimental evaluation indicated that the algorithm achieves a good balance between structure discovery performance and computational efficiency, and demonstrated the comparative effectiveness of its missing information handling process. ADAGIO is able to handle qualitative, quantitative and mixed-type data. An application example to a cancer domain is given, where the algorithm was able to suggest interesting epidemiological interpretations.