Cover Tree-Optimized Spectral Clustering: Efficient Nearest Neighbor Search for Large-Scale Data Partitioning
Abderrafik Laakel Hemdanou, Youssef Achtoun, Sara Mouali, Mohammed Lamartı Sefian, Vesna Šešum-Čavić, Stojan Radenović · Machine Learning and Knowledge Extraction · 2025
Spectral clustering has established itself as a powerful technique for data partitioning across various domains due to its ability to handle complex cluster structures. However, its computational efficiency remains a challenge, especially with large datasets. In this paper, we propose an enhancement of spectral clustering by integrating Cover tree data structure to optimize the nearest neighbor search, a crucial step in the construction of similarity graphs. Cover trees are a type of spatial tree that allow for efficient exact nearest neighbor queries in high-dimensional spaces. By embedding this technique into the spectral clustering framework, we achieve significant reductions in computational cost while maintaining clustering accuracy. Through extensive experiments on random, synthetic, and real-world datasets, we demonstrate that our approach outperforms traditional spectral clustering methods in terms of scalability and execution speed, without compromising the quality of the resultant clusters. This work provides a more efficient utilization of spectral clustering in big data applications.