Using the Triangle Inequality to Accelerate k-Means

By Charles Peter Elkan. International Conference on Machine Learning, 2003

931 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/9b8d8f2fb88e03f8f3ad01efbfef52718b70d104

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

A Complexity-Invariant Distance Measure for Time Series (2011, background): “…this improvement does not compromise the efficiency of algorithms that make frequent calls to a distance measure (classification [5], clustering [6], motif discovery [17] and outlier detection [20][21]), since we can lower bound the measure and use a minor modification of triangular…”
Towards Scalable Dataset Construction: An Active Learning Approach (2008, methodology): “We run Fast K-means [23] to obtain 300 128-dimensional vectors, which form our codebook.”
Fast and robust Earth Mover's Distances (2009, background): “Practical considerations include speed of computation and the metric property that enables fast algorithms for nearest neighbor searches [41, 7], fast clustering [10] and large margin classifiers [15, 36].”
Learning to Count Leaves in Rosette Plants (2015, methodology): “We extract from the green color channel, dense SIFT [24] descriptors with bin size of 15, and use K-means to create a codebook of K = 800 to represent the data.”
Texture optimization for example-based synthesis (2005, methodology): “To accelerate this search, we use hierarchical clustering to organize the input neighborhoods into a tree structure [Johnson 1967; Elkan 2003; Dellaert et al. 2005].”
Scalable Semi-Supervised Learning by Efficient Anchor Graph Regularization (2016, methodology): “In fact, many fast clustering algorithms can be explored to improve the speed of this process [1], [10].”
SLIC Superpixels ? (2010, background): “Note that, like [21], SLIC implicitly sets bounds on distance calculations, but does not need to compute or carry forward these bounds for the subsequent iterations.”
Vlfeat: an open and portable library of computer vision algorithms (2010, methodology): “VLFeat implements the standard Lloyd [7] k-means algorithm and a variant from Elkan [2].”
Web-scale k-means clustering (2010, background): “Additional experiments (omitted for space) showed that mini-batch k-means is several times faster on large data sets than batch k-means exploiting triangle inequality [3].”
Towards parameter-free data mining (2004, methodology): “For some partitional algorithms [6], it is necessary to define the concept of cluster “center”.”
Multispectral pedestrian detection: Benchmark dataset and baseline (2015, methodology): “First, for each of the feature groups, we applied k-means clustering [12].”
Object retrieval with large vocabularies and fast spatial matching (2007, background): “If a scaling-up beyond reasonable memory requirements is needed, the top level branches of each tree can be distributed to different machines.”
Discovery and characterization of chromatin states for systematic annotation of the human genome (2010, background): “First, we found that the descriptive power of the model was appropriately spent, allocating more states to capture biologically-meaningful complexity in small regions, for example dedicating 11 states (1-11) to capture the subtleties of promoter-associated regions that only cover 1% of the genome, w”
Semantic texton forests for image categorization and segmentation (2008, background): “Unfortunately, this three stage process is extremely slow and often the most time consuming part of the whole system, even with optimizations such as kd-trees, the triangle inequality [5], or hierarchical clusters [21, 26].”
Evaluating state-space abstractions in extensive-form games (2013, methodology): “To make this large clustering problem tractable, we use a k -means implementation that uses the triangle inequality to reduce the number of distance function calls [3].”
The Concentration of Fractional Distances (2007, background): “Fractional norms have been studied and used [25], [26], [27], [28], [29], but many fundamental questions remain open about the concentration phenomenon.”
Improved Nyström low-rank approximation and error analysis (2008, methodology): “Recent advances in speeding up the k-means algorithms (Elkan, 2003; Kanungo et al., 2001) also make this k-means-based sampling strategy particularly suitable for large-scale problems.”
Pattern Recognition and Machine Learning (2006, unknown): “Other approaches make use of the triangle inequality for distances, thereby avoiding unnecessary distance calculations (Hodgson, 1998; Elkan, 2003).”
A Spectral Clustering Approach To Finding Communities in Graph (2005, background): “Elkan [5] proposed a much faster version of k-means.”