Wikipedia
X-shift is a density-based clustering method that combines K-nearest neighbor density estimation with a discrete gradient ascent in a K-nearest neighbor graph to find clusters in large datasets. The software implementation of X-shift is based on a fast exact K-nearest neighbor search algorithm that splits the data into convex buckets and then uses the distances to bucket centroids and triangle inequality to guide K-nearest neighbor search. This algorithm shows average complexity of O(n), which leads to a several fold speedup on large datasets. Its primary application is clustering of single-cell phenotypic measurements, especially those derived from flow cytometers and mass cytometers. The algorithm output is controlled by a single free parameter K, which defines the number of nearest neighbors for density estimation, but the algorithm can automatically infer the optimal K value by fitting the elbow point into the plot of number of clusters over K.