Clustering, that is the partitioning of a set of patterns into disjoint and homogeneous meaningful groups (clusters), is a fundamental process in the practice of science. k -windows is an efficient clustering algorithm that reduces the number of patterns that need to be examined for similarity, using a windowing technique. It exploits well known spatial data structures, namely the range tree, that allows fast range searches. From a theoretical standpoint, the k -windows algorithm is characterized by lower time complexity compared to other well-known clustering algorithms. Moreover, it achieves high quality clustering results. However, it appears that it cannot be directly applicable in high-dimensional settings due to the superlinear space requirements for the range tree. In this paper, an improvement of the k -windows algorithm, aiming at resolving this defficiency, is presented. The improvement is based on an alternative solution to the orthogonal range search problem.