A mode-seeking clustering mechanism identifies clusters within a data set based on the location of individual data point according to modes in a kernel density estimate. For large-scale applications the clustering mechanism may utilize rough hierarchical kernel and data partitions in a computationally efficient manner. A variational approach to the clustering mechanism may take into account variational probabilities, which are restricted in certain ways according to hierarchical kernel and data partition trees, and the mechanism may store certain statistics within these trees in order to compute the variational probabilities in a computational efficient way. The clustering mechanism may use a two-step variational expectation and maximization algorithm and generalizations hereof, where the maximization step may be performed in different ways in order to accommodate different mode-seeking algorithms, such as the mean shift, mediod shift, and quick shift algorithms.