  MeanShift is a popular mode-seeking clustering algorithm used in a wide range
of applications in machine learning. However, it is known to be prohibitively
slow, with quadratic runtime per iteration. We propose MeanShift++, an
extremely fast mode-seeking algorithm based on MeanShift that uses a grid-based
approach to speed up the mean shift step, replacing the computationally
expensive neighbors search with a density-weighted mean of adjacent grid cells.
In addition, we show that this grid-based technique for density estimation
comes with theoretical guarantees. The runtime is linear in the number of
points and exponential in dimension, which makes MeanShift++ ideal on
low-dimensional applications such as image segmentation and object tracking. We
provide extensive experimental analysis showing that MeanShift++ can be more
than 10,000x faster than MeanShift with competitive clustering results on
benchmark datasets and nearly identical image segmentations as MeanShift.
Finally, we show promising results for object tracking.
