WorksComputer Science
Small Is Not Dead: Distance-Aware Cluster Revival for e-means
Abstract
e-means (Bessa et al., 2026) is a recent mini-batch k-means algorithm, now part of the FAISS library, that reaches the error of Lloyd's algorithm about an order of magnitude faster on large embedding datasets. Every five mini-batches, it removes every cluster whose running point count falls below a tenth of the average and reuses its centre to split a large cluster. In the authors' ablation, removing this mechanism, called dead-cluster revival, raises the error more than removing any other component added to the moving-average update. The rule, however, considers only cluster size: it cannot distinguish a cluster that is small because it is redundant from one that covers a rare, isolated group of points, and on data with such groups it repeatedly removes centres whose removal is costly. We add a second condition, based on the distance between centres: a small cluster is removed only if its centre is close to another centre, relative to a running estimate of the mean squared error. When a centre equals the mean of its points, this squared distance is an upper bound on the average increase in squared error, per point of the cluster, caused by removing the centre. The condition costs one nearest-centre search for the small clusters every five mini-batches and adds no measurable running time. On the e-means paper's embedding benchmarks, it never prevents a removal, so the results are identical to those of FAISS. On datasets with small isolated groups not used during development, it reduces the test error after two epochs by roughly 10% to 80% relative to count-based revival, and it preserves the advantage of k-means++ initialization; on the other evaluation datasets, it stays within about 1% of the better of revival enabled and disabled. We also report two failure modes that the analysis predicts. This is a CPU proof of concept; GPU implementations are left to future work.
Introduction
The k-means problem asks for centres that minimize the mean squared distance from the points of a dataset to their nearest centre. It is a standard tool for vector quantization, data summarization and approximate nearest-neighbour search [10]. Lloyd’s algorithm [24], which alternates between assigning every point to its nearest centre and moving every centre to the mean of the points assigned to it, remains the default method for solving it.
e-means [6] is a recent replacement for Lloyd’s algorithm that reaches the same error about an order of magnitude faster. It was designed for, and evaluated on, large collections of embedding vectors: on these data it reaches the test error of 25 Lloyd iterations in fewer than three epochs, where an epoch is one complete pass over the training data, and the authors report a reduction in GPU running time of an order of magnitude or more compared with state-of-the-art k-means implementations (1.4–2.6 epochs and a 10–45-fold reduction [6 Table 4]). e-means processes the data in mini-batches and represents each centre as the ratio of two exponential moving averages (EMAs), of the number and of the sum of the points assigned to it; a decreasing step-size schedule and two scaling laws, empirical formulas that set the batch size and the step size from the size of the problem, remove the need for tuning (§ 2). Since version 1.16, e-means is distributed with the FAISS library [10]; we refer to its implementation there as the library.
In addition to the moving-average update, e-means relocates the centres of small clusters during training, a mechanism that the authors call dead-cluster revival. Every five mini-batches, every cluster whose moving-average count has fallen below a tenth of the average count is removed, and its centre is reused to split a large cluster into two. Without this mechanism, many centres stop receiving points: on the DEEP dataset ( points, ), about a quarter of the centres end with fewer than ten points when revival is disabled, against almost none with revival (26% and 0.3% [6 Table 14]). The authors’ ablation removes one component at a time while keeping the moving-average update, which is the core of the method. Among the components it removes, revival is the one whose removal costs most: on the same data, removing it raises the train and test errors by a few percent after three epochs, whereas removing the step-size schedule or the final averaging step changes them by only a fraction of a percent (3.0% and 2.2%, against at most 0.26% [6 Table 1]). On embedding data, where the clusters that become small are mostly redundant, moving their centres into large clusters reduces the error and makes the cluster sizes more uniform.
The revival rule decides by cluster size alone, but the size of a cluster does not determine the cost of removing its centre. A cluster can be small because it is redundant, or because it covers a small group of points far from all other points: a rare category in a tabular dataset, an unusual operating regime of a sensor, or a remote town in a geographic dataset. Removing the centre of a redundant cluster increases the error very little. Removing the centre of an isolated group moves its points to a distant centre, and each of these points then contributes its squared distance to that centre. We found that on such data e-means repeatedly removes exactly these centres. On the UCI Covertype dataset with standardized features, e-means with ends 58% above the test error of 25 Lloyd iterations after two epochs, and still 17% above it after ten epochs, whereas with revival disabled it ends 24% below Lloyd’s error after two epochs (§ 3).
The authors of e-means have also encountered this problem. A recent change to the library disables revival by default for data with at most two dimensions, after the authors found that disabling it lowered the median test error on two-dimensional geographic datasets by 7–10% [5]. This change is documented in the library’s source code and is not described in the e-means paper. It is a coarse mitigation: it decides by dimension, whereas the failure depends on whether small clusters are isolated, which also occurs in high dimension, for example on Covertype (54 dimensions) and KDD Cup 99 (122 dimensions after encoding).
Our Contribution
We propose a better-informed revival rule. It keeps the size test of e-means and adds a second condition that uses a second source of information, the distance from the centre of a small cluster to the nearest other centre: a small cluster is removed only if its centre is close to another centre. Clusters that are small because they are redundant are therefore still removed, and clusters that cover isolated groups of points are kept. In our timings, the added condition has no measurable computational cost.
Rule. A cluster selected by the size test, which we call a candidate, is removed only if , the squared distance from its centre to the nearest other centre, is at most , where is a running estimate of the mean squared error (MSE) and is a threshold; or if it has received no point for two epochs (§ 4). The distance test has a simple interpretation. When is the mean of the points nearest to it, is an upper bound on the average increase in squared error, per point of the cluster, caused by removing while the other centres are kept fixed (Proposition 1); summed over the points of the cluster, this increase is Fritzke’s utility [15, 16]. Under these conditions, the test removes a candidate only if removing it increases the squared error of its points, on average, by at most times the current MSE. We use , a margin above the largest values of that we observed among the candidates on embedding data, where removals are beneficial. The exact value matters little: on held-out data, values from 2 to 8 give nearly the same results (§ 5.5), so the threshold only needs to lie roughly in this range. The second condition, which we call the abandonment clause, releases a centre that has lost all its points while being far from all other centres. It is a safeguard motivated by an argument rather than by an observed failure: such a centre can be removed at no cost, but the distance test alone would keep it until the end of training. In our experiments, it rarely acts, and removing it changes the results negligibly (§ 5.5); the gains come from the distance test. Two epochs is the shortest waiting period, measured in whole epochs, after which this clause never removes a centre that receives at least one point in every epoch, whatever the batch size: when the data are shuffled before every epoch, a point visited at the start of one epoch may next be visited at the end of the following epoch, almost two epochs later (Proposition 2).
Cost. Count-based revival already keeps a moving-average count per cluster and checks it every five batches. Our rule adds one moving average per cluster, computed from the point-to-centre distances that the assignment step already returns, and a nearest-centre search for the candidates at each check. In the two configurations that we timed, the running time with our rule was the same as that of the library, within the variation between repeated runs (§ 5.6).
Evidence. We follow an experimental protocol that was written down before the runs, and we evaluate on held-out datasets that were not used during development (§ 5). On three embedding datasets of the e-means paper, in four of its configurations with up to ten million points and 65,536 centres, the distance test never prevents a removal, so all runs are identical to those of the library. On held-out datasets with small isolated groups, it reduces the test error after two epochs relative to count-based revival by roughly 25–80% on KDD Cup 99, 20–75% on Shuttle and 10–25% on GeoNames, depending on the number of centres. On the other evaluation datasets, its test error after two epochs is within about 1% of the better of revival enabled and revival disabled. With k-means++ initialization, it keeps the centres that k-means++ places on isolated groups, which count-based revival removes: on KDD Cup 99 (, two epochs), count-based revival ends at more than 25 times the test error of 25 Lloyd iterations started from the same centres, and our rule within 1% of it. Compared with an online estimate of the utility, the bound is as good or better in most configurations, and much better in training error on data with rare points far from all others; the estimate is better on YearPredictionMSD. The bound adds no measurable running time and uses only the centres, whereas the estimate requires a search for the two nearest centres of every point in every batch. Finally, we document two failure modes that the analysis predicts (§ 5.7).
We release the code.1 It is a subclass of the library’s NumPy implementation and can replace it without other changes.
Background: e-means and Count-Based Revival
Let be the training points and the centres. We write for the index of the centre nearest to a point , and say that is assigned to that centre. The -means objective is the mean squared error (MSE), ; the sum of squared errors (SSE) is times the MSE. Lloyd’s algorithm [24] alternates between assigning every point to its nearest centre and replacing every centre by the mean of the points assigned to it; each such iteration is one epoch. As in the e-means paper, our reference is FAISS’s implementation of Lloyd’s algorithm run for 25 iterations, which we denote Lloyd@25.
The e-means update. e-means [6 Sec. 3] processes the data in epochs. Each epoch visits every training point once, in a new random order, in batches of points, so that an epoch consists of batches. We denote by the number of epochs, by the total number of batches, and by the index of the current batch. For each cluster , e-means keeps two EMAs, a count and a sum of the points assigned to , and defines the centre as their ratio. With and the number and the sum of the points of batch with ,
where is the step size (the learning rate). Equivalently, moves towards the mean of its batch points by a fraction of the distance, where is the updated count; a cluster that receives no point does not move. With the whole dataset as one batch and , Equation (1) is one iteration of Lloyd’s algorithm. The step size decreases from to along a cosine curve, , a schedule known as cosine annealing [25]. The batch size and the initial step size are set by two scaling laws, that is, empirical power laws in , and , which the authors fitted on one embedding dataset [6 Sec. 3.3]; the library’s default (batch_law="auto") uses a smaller batch size for . The centres are initialized at training points drawn at random, with a negligible initial count. After the last epoch, each centre is replaced by the mean of the points assigned to it during that epoch, a step that the authors call the last-epoch mean. The EMA update itself comes from vector-quantized autoencoders [34]; e-means combines it with the step-size schedule, the scaling laws, the last-epoch mean and the revival rule described below.
Count-based revival. Every batches, the clusters whose count is below a fraction of the average count, with , form the candidate set . Each candidate is removed, and its centre is reused to split a donor cluster. Donors are drawn without replacement among the non-candidates, with probability proportional to their count. The donor’s centre is replaced by , and the candidate’s centre is set to , where denotes the elementwise product, and ; both clusters receive half of the donor’s count, with sums that match their new centres. FAISS’s implementation of Lloyd’s algorithm applies the same split only to clusters that have become empty, whereas e-means also removes clusters that still receive points, at any time during training. We call this rule count-based revival.
When Count-Based Revival Fails
Consider a cluster whose centre covers a group of points that lie at distance about from every other centre, with large compared with the spread of the group. The group contributes about points to a batch, while the average count is about ; so if , cluster is typically a candidate at every check. Removing it moves all points to a centre at squared distance about , which increases the SSE by about . This increase can exceed the SSE of many ordinary clusters combined, while the split that reuses the centre reduces the error much less. Two properties of e-means make this worse. First, is a moving average over a few batches, so a group whose points appear in only a few batches of each epoch (for example, a handful of rare points) has close to zero between these batches. Second, the rule is applied until the end of training, so a centre that moves back to the group is removed again.
Figure 1 shows the effect in two dimensions. Twenty Gaussian blobs of 2,000 points each are complemented by three far groups of 80 points each (4% of the size of a typical cluster), and . k-means++ initialization [1] places a centre on every far group in all 10 random seeds that we ran. After 5 epochs, count-based revival has removed all three of these centres in all 10 seeds, whereas with the distance test of § 4 all three are kept in all 10 seeds.
Figure 1. Two-dimensional example: 20 Gaussian blobs of 2,000 points and three far groups of 80 points (dotted circles), centres initialized by k-means++ (orange circles), and 5 epochs of e-means. Left: count-based revival removes the centres of the three far groups and reuses them inside the main mass of points. Right: with the distance test, all three are kept. Seed 0 is shown; the outcome (0 of 3 and 3 of 3 far groups kept) is the same in all 10 seeds. The size threshold is the e-means paper’s ; since version 1.16, the library disables revival by default for .
The same failure occurs on real data. On UCI Covertype with standardized features (each feature shifted and scaled to zero mean and unit variance), each of the 40 soil types is encoded as a binary (one-hot) feature. For the rarest soil types, standardization maps the value 1 to hundreds of standard deviations from the mean, so the few points with such a soil type form small, isolated groups. With , e-means with its default settings ends 58% above the test error of Lloyd@25 after 2 epochs, and disabling revival brings it to 24% below Lloyd@25 (§ 5). The gap is therefore caused by the removal rule, not by the moving-average optimization.
Algorithm 1 Revival in e-means with the distance test. The parts in colour are added by our rule; the rest is the library’s procedure, unchanged.
Initialization
and for every cluster
After each batch
update and as in e-means (Equation (1))
if then
Every batches
▷ size test
for each ▷ nearest-centre search
▷ library:
for each do
draw a new donor among the non-candidates, with probability proportional to
split the donor’s cluster, and set to one of the two halves
split like , and set
end for
Distance-Aware Revival
We keep the candidate set of count-based revival and add a condition that decides which candidates are removed: a candidate is removed only if its centre is close to another centre, or if it has received no point for a long time. Each cluster carries one more EMA, , of its batch distortion, that is, of the sum of the squared distances from the batch points assigned to to ; these distances are available from the assignment step, and is updated with the same step size as . Each cluster also records , the index of the last batch in which it received a point, or of the batch in which a split created it; the latter gives a newly created centre a full waiting period before it can be considered abandoned. At a revival check at batch ,
with batches per epoch. Here , the ratio of the two moving averages, is a running estimate of the MSE over all clusters, is the squared distance from to the nearest other centre, is a threshold, and is a waiting period measured in epochs. We call the second condition the abandonment clause. It handles a case that the distance test cannot: removing a centre that has lost all its points does not change the SSE, but if that centre is far from every other centre, the distance test keeps it until the end of training. The clause is motivated by this argument, not by a failure that we observed; in our experiments, it rarely acts and has no measurable effect on the error (§ 5.5). Removed candidates are reused exactly as in the library, with the same random procedure for choosing donors; the other candidates keep their centres and statistics. We use and throughout; both values were chosen on the development data and fixed before the evaluation on the held-out datasets (§ 5). Algorithm 1 gives the pseudo-code, with the parts that differ from the library in colour.
Proposition 1 (Removal cost). Let be the set of training points whose nearest centre is , assumed non-empty, let be their mean, and let be a centre nearest to among the others, so
that . With the other centres kept fixed, removing increases the sum of squared errors by
with equality in the first inequality if and only if is a nearest remaining centre of every point of . In particular, if (as at a fixed point of Lloyd’s algorithm), then .
Proof. We first replace the nearest remaining centre of each point by , then compute the resulting increase exactly, point by point, and sum over .
Step 1 (one replacement centre for all points). Let . Since is one of the remaining centres, , with equality if and only if is a nearest remaining centre of . Subtracting from both sides and summing over gives
with equality if and only if is a nearest remaining centre of every point of .
Step 2 (one point). Write and expand the square:
Since , the increase for the point is
Step 3 (sum over the cluster). Summing Equation (4) over the points of , and using the linearity of the inner product,
Since is the mean of , , so . Therefore
Combining Equations (3) and (5) gives the first inequality, with its equality condition.
Step 4 (Cauchy–Schwarz). By the Cauchy–Schwarz inequality, , which gives the second inequality.
Step 5 (centre at the mean). If , the inner product in Equation (5) is zero, and the first inequality becomes .
is Fritzke’s utility of centre [15, 16]: the increase in SSE caused by removing it while the other centres are kept fixed. When , also upper-bounds the increase in SSE caused by merging with the cluster of , , which is the merge cost of Ward’s agglomerative clustering and of the pairwise nearest neighbour (PNN) method [11, 36]. For a candidate () the two quantities are nearly equal. Proposition 1 motivates the test; it does not make the rule exact. Under its conditions, removing a candidate increases the squared error of its points, on average, by at most times the current MSE; dividing by MSE makes the test invariant to the scale of the data. Individual points can lose more, up to for a cluster of radius (the largest distance from to a point of ). The conditions are that one centre is removed while the others are kept fixed, and that the centre equals the mean of its points. Three aspects of the algorithm violate them. First, two nearby candidates can each pass the test because of the other, and both are then removed; breathing k-means avoids the analogous problem by excluding the nearest neighbour of a centre selected for removal from removal in the same step, which its author calls freezing [17], and we do not. Second, a centre can lag behind its points, as described next. Third, the abandonment clause removes a candidate regardless of distance.
Centre lag. In e-means, is a weighted mean, with exponentially decaying weights, of the points assigned to in past batches, together with its initial or split position; it is not the mean of the points currently nearest to it. For that weighted set of points, is the mean, so the weighted version of the inner product in Equation (5) is zero, as in Step 5 of the proof. The points currently nearest to can have a mean , and Proposition 1 then adds per point. This term is positive when lags behind a group of points that lies on the side away from ; then underestimates the cost, and the test errs towards removal, which is the library’s behaviour.
Bound versus utility estimate. The bound uses only the centres; it needs no distance from each point to its second-nearest centre. We compare it in § 5.4 with an online estimate of the utility per point: an EMA of over the batch points assigned to , divided by the matching EMA of their number, where is the distance from a point to its assigned centre and the distance to its nearest other centre. Because it averages over past batches, in which the centres were at different positions, it estimates rather than equals it, and it requires a search for the two nearest centres of every point in every batch.
Proposition 2 (Waiting period). Suppose that the run consists of whole epochs, each visiting every training point exactly once in batches (as e-means does when the number of epochs is an integer, as in all our runs). (a) If centre receives at least one point in every epoch, then at every revival check, so the abandonment clause with never applies to . (b) Suppose, in addition, that the order of each epoch is a uniformly random permutation of the training points, independent of the orders of the other epochs. If is the nearest centre of a single training point, the gap between two consecutive visits of that point exceeds epochs with probability in the limit .
Proof. (a) Epochs and consist of batches and . If receives a point in batch and next in batch , with , the gap is . Since is updated before the check, any check strictly between the two batches has . Before the first such batch, and .
(b) Since the point is visited once per epoch, two consecutive visits occur in consecutive epochs, say and . For , let be the position of the point in the order of epoch , and is the index, within that epoch, of the batch that contains it. As in (a), the gap between the two visits is batches, that is, epochs.
Distribution of the positions. A uniformly random permutation places a given point at each of the positions with probability , so is uniformly distributed on . Since the orders of the two epochs are independent, so are and , and hence and . Moreover, differs from by less than , because , and is uniform on . Therefore, as (which requires ), the pair converges in distribution to a pair of independent random variables, each uniformly distributed on , and the gap converges in distribution to epochs.
Probability of a long gap. The gap exceeds if and only if , where . The set is a right triangle whose two legs have length , and is uniformly distributed on the unit square, so . The distribution of has no atoms, so this is also the limit of the probability that the gap of the finite run exceeds epochs.
Hence, with , the abandonment clause never removes a centre that receives at least one point in every epoch, for any data, and no smaller has this property for every value of (the largest possible value of is ). With , the clause wrongly removes the centre of a single point between two given consecutive visits with probability approaching when an epoch has many batches, and at least once in a run of epochs with probability approaching ( for ). If the number of epochs is not an integer, e-means adds an incomplete epoch, which visits only a prefix of its random order, just before the last epoch, and the guarantee then requires the waiting period to be counted in complete epochs. The clause can only act in runs longer than epochs. Its purpose is to release a centre that has lost all its points while being far from every other centre, which the distance test alone would keep until the end of training; as noted above, our experiments show no measurable benefit from it (§ 5.5).
Cost and implementation. The rule needs two additional arrays of length ( and ); our implementation also keeps per-batch buffers, and two more arrays for the utility-estimate variant. is a per-cluster sum of the squared distances that the assignment step already returns, and requires the distances between the candidates and the centres every batches. Our implementation is a subclass of the library’s NumPy class (NumpyEmeans). With and no abandonment clause, it produces exactly the same centres as the library, which our unit tests verify. Porting it to the library’s PyTorch implementation for GPUs requires no new GPU kernel: only the same per-cluster sum, a search for the two nearest centres of each candidate in the revival step, and, in the multi-GPU version, summing across devices together with the counts and sums. The GPU implementation records each training step as a CUDA graph, a fixed sequence of GPU operations that is replayed for every batch, so the new state must be included in that recorded sequence. We leave this engineering to future work.
Experiments
Protocol. We wrote down the experimental protocol (datasets, configurations, metrics and statistical tests) and froze it before any of the runs reported here. Three dated amendments were each written before the runs they describe. The first added random seeds for Table 2, two more held-out datasets and two more embedding configurations. The second and third followed two rounds of independent review and corrected the utility-estimate variant (described below); all its runs were repeated after each correction, and after the third correction nearly all of them had exactly the same train and test MSE as before. The protocol and its amendments are distributed with the code. The values and come from development runs on Covertype, on the synthetic flat groups (Appendix § 9.§ 6) and on 200,000-point subsets of DEEP and SIFT; they were not changed afterwards. All runs use the NumPy implementation of e-means in FAISS 1.16 on CPU, with nearest-centre search in single precision, and with the library’s default settings (§ 2): the scaling laws, batch_law="auto" and the last-epoch mean. The methods differ only in the revival rule, and the size threshold is in every dimension; we do not apply the library’s default of disabling revival for , except in the method OFF.
| Dataset | Seeds | COUNT | OFF | DISTANCE | ESTIMATE | W/T/L | W/T/L | |||||
| Held-out datasets | ||||||||||||
| KDD Cup 99 | 256 | 30 | 1.121 | 0.550 | 0.526 | 0.524 | −51.8% | 30/0/0 | −3.1% | 22/0/8 | 1.000 | |
| KDD Cup 99 | 1024 | 30 | 2.837 | 0.629 | 0.561 | 0.562 | −81.2% | 30/0/0 | −8.7% | 27/0/3 | 0.007 | |
| KDD Cup 99 | 4096 | 30 | 1.174 | 0.982 | 0.916 | 0.960 | −23.6% | 26/0/4 | −5.6% | 23/0/7 | 0.108 | |
| Census 1990 | 256 | 30 | 0.991 | 0.992 | 0.991 | 0.991 | +0.0% | 3/19/8 | 1.000 | −0.0% | 16/2/12 | 1.000 |
| Census 1990 | 1024 | 30 | 0.990 | 0.988 | 0.989 | 0.990 | −0.1% | 22/4/4 | 0.006 | +0.0% | 12/0/18 | 1.000 |
| Census 1990 | 4096 | 30 | 0.992 | 0.990 | 0.991 | 0.992 | −0.1% | 24/1/5 | 0.004 | +0.0% | 12/1/17 | 1.000 |
| YearPredictionMSD | 256 | 30 | 1.020 | 1.025 | 1.021 | 1.011 | +0.1% | 10/0/20 | 1.000 | −0.5% | 29/0/1 | |
| YearPredictionMSD | 1024 | 30 | 1.012 | 1.023 | 1.012 | 1.008 | +0.0% | 14/0/16 | 1.000 | −1.1% | 30/0/0 | |
| YearPredictionMSD | 4096 | 30 | 1.003 | 1.029 | 1.005 | 1.003 | +0.2% | 1/0/29 | −2.3% | 30/0/0 | ||
| GeoNames (2-D) | 256 | 30 | 1.027 | 0.902 | 0.903 | 0.910 | −9.2% | 29/0/1 | +0.0% | 12/11/7 | 1.000 | |
| GeoNames (2-D) | 1024 | 30 | 1.237 | 0.924 | 0.928 | 0.938 | −25.4% | 30/0/0 | −0.2% | 20/0/10 | 1.000 | |
| GeoNames (2-D) | 4096 | 30 | 1.120 | 0.963 | 0.939 | 0.964 | −14.0% | 29/0/1 | −1.4% | 23/0/7 | 0.504 | |
| Household power | 256 | 10 | 1.003 | 0.945 | 0.949 | 0.953 | −5.1% | 10/0/0 | 0.504 | +0.5% | 4/0/6 | 1.000 |
| Household power | 1024 | 10 | 0.972 | 0.949 | 0.960 | 0.967 | −1.5% | 10/0/0 | 0.504 | +0.7% | 0/0/10 | 0.504 |
| Shuttle | 256 | 10 | 3.853 | 1.021 | 1.041 | 1.063 | −73.3% | 10/0/0 | 0.504 | +1.3% | 1/0/9 | 1.000 |
| Shuttle | 1024 | 10 | 1.350 | 1.038 | 1.039 | 1.037 | −20.2% | 10/0/0 | 0.504 | +0.9% | 2/0/8 | 1.000 |
| Development datasets | ||||||||||||
| Covertype (z-score) | 256 | 30 | 1.576 | 0.757 | 0.747 | 0.746 | −52.5% | 30/0/0 | −1.0% | 28/0/2 | ||
| Covertype (z-score) | 1024 | 30 | 1.002 | 1.005 | 0.996 | 0.997 | −0.3% | 23/1/6 | 0.109 | −0.7% | 30/0/0 | |
| Covertype (z-score) | 4096 | 30 | 1.008 | 1.008 | 1.008 | 1.007 | −0.1% | 21/1/8 | 0.819 | −0.1% | 19/0/11 | 1.000 |
| Covertype (min-max) | 256 | 30 | 0.980 | 0.973 | 0.973 | 0.975 | −0.6% | 24/0/6 | 0.605 | −0.0% | 18/2/10 | 1.000 |
| Covertype (min-max) | 1024 | 30 | 1.011 | 1.006 | 1.003 | 1.006 | −0.4% | 24/0/6 | 0.101 | −0.3% | 24/0/6 | 0.223 |
| Covertype (min-max) | 4096 | 30 | 1.003 | 1.007 | 1.003 | 1.003 | −0.1% | 20/2/8 | 1.000 | −0.2% | 25/0/5 | 0.018 |
Table 2. Test MSE after two epochs, random initialization. Columns 4–7: median test MSE divided by the median test MSE of Lloyd@25 over seeds 0–9 (a fixed reference, not a paired ratio). Seeds: number of paired seeds per comparison (30, or 10 for household power and Shuttle). : median over seeds of the relative change in the test MSE of DISTANCE with respect to the other method (negative values favour DISTANCE). W/T/L: numbers of seeds in which DISTANCE is better, tied () or worse. : two-sided Wilcoxon signed-rank test, Holm-adjusted over all comparisons on the held-out datasets (the development datasets form a separate family). Tables 4 to 7 in the appendix report the other numbers of epochs.
Methods. We compare the following revival rules; the names in parentheses are those used in the released code and records.
COUNT (count): count-based revival as in the library (the library’s default for ).
OFF (off): no revival (the library’s default for since version 1.16).
DISTANCE (near): our rule, Equation (2).
ESTIMATE (exact): the same rule with an online estimate of Fritzke’s utility per point, , in place of . Here is an EMA of over the batch points assigned to , and is the EMA of their number with the same step sizes; both restart when a split creates the centre. As in § 4, and are the distances from a point to its assigned centre and to its nearest other centre. They are computed by a separate search for the two nearest centres, so the library’s assignment is unchanged. A centre that has received no point since its creation has unknown utility and is not removed by the utility test; the abandonment clause still applies to it.
DISTANCE without abandonment: DISTANCE without the abandonment clause.
Lloyd@25: FAISS’s implementation of Lloyd’s algorithm, run for 25 iterations on all training points, the reference of the e-means paper.
For a given seed, all methods start from the same centres: either training points drawn at random (random initialization) or the centres chosen by greedy -means++ [1, 27], which selects each new centre as the best of several candidate points, each sampled with probability proportional to its squared distance to the nearest centre already selected.
Data. We use three groups of datasets.
Held-out datasets, never used during development:
KDD Cup 1999 [32]: the full data, with exact duplicates removed as in NSL-KDD [33]; 1.05M points with 122 dimensions after one-hot encoding of the categorical features.
US Census 1990 [26]: 2.0M unique points with 68 attributes.
YearPredictionMSD [4]: 495k points with 90 features.
GeoNames [19]: latitude and longitude of 1M places.
Individual household electric power consumption [20]: 1.89M points with 7 features.
Statlog Shuttle [31]: 38k points with 9 features.
SPACEV 1M [30], an embedding dataset from the e-means paper’s benchmarks, with .
Development datasets at larger scale: DEEP 1M [2] and SIFT 1M [23] with , and DEEP 10M with , all in the e-means paper’s configurations. During development we used only the first 200,000 points of the same 1M-point training sets.
Development datasets: Covertype [7] (561k points, 54 dimensions), standardized or rescaled to per feature (min-max scaling), and the synthetic far groups (Appendix § 9.§ 6).
In the tabular datasets we remove exact duplicates and standardize every feature (except in the min-max variant of Covertype); GeoNames is kept in degrees. As in the e-means paper, we hold out 20,000 points and use half of them as the test set. The numbers of epochs are ({1,2,5,10} for household power and Shuttle), and the numbers of centres are ({$256, 1024} for household power and Shuttle). We run 10 seeds per configuration, and 30 for the configuration of Table 2. The test MSE is the MSE of the test points; as in the e-means paper, the nearest centre is found in single precision and the squared distance to it is then computed in double precision. The train MSE is the MSE of all training points (of a fixed subset of 200,000 points for the embedding datasets). Appendix B gives further details of the data, the splits, the software and the hardware.
Statistics. Comparisons are paired by seed. We report the median over seeds of the relative change in test MSE (; negative values favour DISTANCE), the numbers of seeds in which DISTANCE wins, ties or loses (W/T/L; a tie is ), and two-sided Wilcoxon signed-rank tests [37]. As the protocol specifies, we apply Holm’s correction for multiple comparisons [21] within one family of tests per experiment: all comparisons of DISTANCE with COUNT and with OFF on the held-out datasets, over both initializations, all numbers of epochs and all values of (272 tests). The development datasets form a second family. Lloyd@25 is a fixed reference: we divide each method’s median test MSE by the median test MSE of Lloyd@25 over seeds 0–9 with the same type of initialization (seeds 0–2 for the embedding datasets). These are ratios of medians, not paired ratios. Appendix A reports every configuration (Table 4 to Table 18); the complete per-run records, including those of DISTANCE without abandonment, are released with the code.
| Dataset | Seeds | COUNT | OFF | DISTANCE | ESTIMATE | W/T/L | W/T/L | |||||
| Held-out datasets | ||||||||||||
| KDD Cup 99 | 256 | 10 | 1.194 | 0.812 | 0.840 | 0.853 | −30.4% | 10/0/0 | 0.504 | +3.4% | 3/0/7 | 1.000 |
| KDD Cup 99 | 1024 | 10 | 3.341 | 1.150 | 0.993 | 1.000 | −70.8% | 10/0/0 | 0.504 | −3.7% | 6/0/4 | 1.000 |
| KDD Cup 99 | 4096 | 10 | 2.061 | 1.434 | 1.338 | 1.501 | −27.9% | 10/0/0 | 0.504 | −2.0% | 6/0/4 | 1.000 |
| Census 1990 | 256 | 10 | 0.997 | 0.996 | 0.998 | 0.997 | +0.0% | 2/7/1 | 1.000 | −0.1% | 7/0/3 | 1.000 |
| Census 1990 | 1024 | 10 | 1.000 | 0.999 | 0.999 | 1.000 | −0.0% | 5/0/5 | 1.000 | −0.0% | 5/1/4 | 1.000 |
| Census 1990 | 4096 | 10 | 1.005 | 1.002 | 1.003 | 1.004 | −0.1% | 9/0/1 | 0.721 | +0.0% | 5/0/5 | 1.000 |
| YearPredictionMSD | 256 | 10 | 1.040 | 1.018 | 1.017 | 1.025 | −2.2% | 10/0/0 | 0.504 | −0.0% | 5/1/4 | 1.000 |
| YearPredictionMSD | 1024 | 10 | 1.028 | 1.025 | 1.016 | 1.021 | −1.0% | 10/0/0 | 0.504 | −0.8% | 10/0/0 | 0.504 |
| YearPredictionMSD | 4096 | 10 | 1.017 | 1.039 | 1.014 | 1.018 | −0.3% | 8/0/2 | 1.000 | −2.3% | 10/0/0 | 0.504 |
| GeoNames (2-D) | 256 | 10 | 1.112 | 1.007 | 1.005 | 1.038 | −8.5% | 10/0/0 | 0.504 | +0.0% | 4/2/4 | 1.000 |
| GeoNames (2-D) | 1024 | 10 | 1.370 | 1.063 | 1.071 | 1.088 | −22.7% | 10/0/0 | 0.504 | −0.3% | 7/0/3 | 1.000 |
| GeoNames (2-D) | 4096 | 10 | 1.205 | 1.083 | 1.063 | 1.085 | −12.1% | 10/0/0 | 0.504 | −1.5% | 7/0/3 | 1.000 |
| Household power | 256 | 10 | 1.040 | 0.983 | 0.989 | 0.990 | −5.1% | 10/0/0 | 0.504 | +0.5% | 2/1/7 | 1.000 |
| Household power | 1024 | 10 | 1.025 | 1.004 | 1.006 | 1.011 | −2.0% | 10/0/0 | 0.504 | +0.4% | 2/0/8 | 1.000 |
| Shuttle | 256 | 10 | 4.452 | 2.280 | 2.765 | 3.037 | −37.4% | 10/0/0 | 0.504 | +14.5% | 1/0/9 | 0.508 |
| Shuttle | 1024 | 10 | 3.001 | 1.543 | 1.544 | 1.554 | −43.7% | 10/0/0 | 0.504 | +1.1% | 2/0/8 | 1.000 |
| Development datasets | ||||||||||||
| Covertype (z-score) | 256 | 10 | 1.794 | 0.841 | 0.831 | 0.832 | −52.2% | 10/0/0 | 0.223 | −1.3% | 10/0/0 | 0.223 |
| Covertype (z-score) | 1024 | 10 | 1.043 | 1.024 | 1.023 | 1.020 | −0.5% | 8/0/2 | 0.793 | −0.3% | 9/0/1 | 1.000 |
| Covertype (z-score) | 4096 | 10 | 1.049 | 1.049 | 1.048 | 1.048 | −0.0% | 8/0/2 | 1.000 | +0.0% | 4/0/6 | 1.000 |
| Covertype (min-max) | 256 | 10 | 0.998 | 0.982 | 0.985 | 0.995 | −0.5% | 7/0/3 | 1.000 | +0.0% | 4/1/5 | 1.000 |
| Covertype (min-max) | 1024 | 10 | 1.019 | 1.017 | 1.007 | 1.009 | −0.8% | 9/0/1 | 0.393 | −0.4% | 9/0/1 | 0.285 |
| Covertype (min-max) | 4096 | 10 | 1.040 | 1.040 | 1.038 | 1.039 | −0.2% | 9/1/0 | 0.285 | −0.0% | 5/0/5 | 1.000 |
Table 4. Random initialization, 1 epoch. Columns as in Table 2.
| Initialization | Method | 50 | 100 | 150 | 250 | 400 | ||
| Random | Lloyd@25 | 2.3 | 2.7 | 2.8 | 3.3 | 4.7 | 0.822 | 180 |
| Random | COUNT | 0.0 | 0.0 | 0.0 | 0.7 | 5.0 | 0.562 | 152 |
| Random | OFF | 2.8 | 2.5 | 3.0 | 3.4 | 5.0 | 0.622 | 198 |
| Random | DISTANCE | 2.5 | 2.4 | 2.9 | 3.4 | 5.0 | 0.611 | 152 |
| Random | DISTANCE, no abandonment | 2.5 | 2.4 | 2.9 | 3.4 | 5.0 | 0.611 | 152 |
| Random | ESTIMATE | 2.4 | 2.4 | 2.9 | 3.4 | 5.0 | 0.571 | 158 |
| k-means++ | Lloyd@25 | 2.6 | 4.6 | 5.0 | 5.0 | 5.0 | 0.293 | 14.5 |
| k-means++ | COUNT | 0.0 | 0.0 | 0.0 | 0.6 | 4.9 | 0.333 | 14.5 |
| k-means++ | OFF | 2.8 | 4.7 | 5.0 | 5.0 | 5.0 | 0.29 | 14.5 |
| k-means++ | DISTANCE | 2.7 | 4.7 | 5.0 | 5.0 | 5.0 | 0.29 | 14.5 |
| k-means++ | DISTANCE, no abandonment | 2.7 | 4.7 | 5.0 | 5.0 | 5.0 | 0.29 | 14.5 |
| k-means++ | ESTIMATE | 2.6 | 4.7 | 5.0 | 5.0 | 5.0 | 0.288 | 14.5 |
Table 18. Synthetic data, 5 epochs, 10 seeds; errors are measured on the training points. Far groups: mean number of far groups kept over seeds. Heterogeneous scales: median MSE. Far groups kept (of 5), by group size . Heterogeneous, MSE.
No Change Where Revival Helps
On the embedding datasets of the e-means paper, count-based revival removes thousands of centres per run, and the distance test never prevents a removal (Table 1). Since the test keeps no candidate in any run, every removal, and hence every run, is the same as in the library: train and test MSE equal those of the library exactly in all 103 runs, and our unit tests verify that the centres are identical bit for bit when no candidate is kept. These runs include DEEP 10M with , which we ran for 2 epochs with 3 seeds only to check this identity. In the library’s runs on DEEP and SIFT, which have more than half a million candidates in total (a candidate is counted once at every revival check), every ratio is at most about 2.5, and very few exceed 2 (Figure 3), well below the threshold . Revival is beneficial on these datasets: disabling it raises the test MSE by a few percent, in every seed and for every number of epochs (Table 1), which is consistent with the ablation in the e-means paper. Our setup also reproduces the e-means paper’s results closely: after three epochs on DEEP 1M, e-means ends about 0.3% below the test MSE of Lloyd@25, both in our runs and in the e-means paper (ratios 0.9968 and 0.38788/0.38926 = 0.9965 [6 Table 5]).
| Dataset | Epochs | Identical runs | COUNT | OFF | DISTANCE | Splits per run |
| DEEP 1M | 1 | 10/10 | 1.0115 | 1.0420 | 1.0115 | 9010 |
| DEEP 1M | 2 | 10/10 | 0.9989 | 1.0315 | 0.9989 | 9726 |
| DEEP 1M | 3 | 10/10 | 0.9968 | 1.0180 | 0.9968 | 6892 |
| DEEP 1M | 5 | 10/10 | 0.9938 | 1.0161 | 0.9938 | 7454 |
| SIFT 1M | 1 | 10/10 | 1.0091 | 1.0330 | 1.0091 | 6902 |
| SIFT 1M | 2 | 10/10 | 0.9967 | 1.0216 | 0.9967 | 7290 |
| SIFT 1M | 3 | 10/10 | 0.9954 | 1.0108 | 0.9954 | 4622 |
| SIFT 1M | 5 | 10/10 | 0.9928 | 1.0073 | 0.9928 | 4826 |
| SPACEV 1M | 2 | 10/10 | 1.0009 | 1.0385 | 1.0009 | 14212 |
| SPACEV 1M | 5 | 10/10 | 0.9917 | 1.0179 | 0.9917 | 11208 |
| DEEP 10M | 2 | 3/3 | – | – | – | 16451 |
Table 1. Embedding datasets in the e-means paper’s configurations (random initialization, 10 seeds per row; DEEP 10M: 3). Ratios use the median test MSE of Lloyd@25 over seeds 0–2; DEEP 10M has no Lloyd@25 reference. Identical runs: runs whose train and test MSE equal those of the library exactly. Splits per run: median number of removals, each followed by a split.
Figure 3. Cumulative distribution of the ratio that the distance test computes for each candidate, recorded in runs of count-based revival, which remove every candidate whatever its ratio (2 epochs, random initialization; , or for DEEP 1M and SIFT 1M). Each curve pools all the runs of one dataset (30 seeds for the tabular datasets, 10 for DEEP 1M and SIFT 1M), and counts a candidate once at every revival check at which it is a candidate; the legend gives the number of pooled values. A curve is therefore the distribution of these pooled values, not an average over runs. The values are recorded in a histogram with ten bins per factor of ten, hence the steps. No value on DEEP 1M or SIFT 1M exceeds about 2.5. The fraction above is 23–24% on KDD Cup 99, 13–23% on Census, 33–43% on YearPredictionMSD, 38–45% on Covertype and 69–73% on GeoNames; each range reflects the width of the histogram bin that contains 4. On KDD Cup 99 and Covertype, part of the distribution lies several orders of magnitude above the threshold.
Large Gains on Data with Isolated Groups
Table 2 reports the test MSE after two epochs from random initialization, as ratios to Lloyd@25. Relative to COUNT, DISTANCE reduces the test error by large margins on the held-out datasets with isolated groups: by roughly 25–80% on KDD Cup 99, 20–75% on Shuttle and 10–25% on GeoNames, depending on . On Covertype, a development dataset, it reduces the error by up to about half. On household power, which, like Shuttle, was chosen before any result on it was seen, it reduces the error by a few percent. On Census 1990 and YearPredictionMSD, it changes the test error by at most a few tenths of a percent.
Relative to OFF, the median change in test error of DISTANCE is below 1.5% in every held-out configuration of Table 2. At two epochs, DISTANCE therefore performs about as well as the better of the library’s two settings. On KDD Cup 99 its median test error is lower than both for all three values of ; against OFF, the difference is significant after correction only for .
With more epochs, COUNT does not catch up (Figure 2). In 9 held-out configurations, COUNT does not reach the test error of Lloyd@25 at any tested number of epochs up to ten (Table 8). DISTANCE reaches it in 7 of these configurations, and within two epochs in 5 of them. Here, the number of epochs needed is the smallest tested number of epochs whose median test error is below that of Lloyd@25; each number of epochs is a separate run. The two remaining configurations are on YearPredictionMSD, where neither method reaches it. Outside the embedding setting, the distance test therefore restores, in most configurations, the main property of e-means: reaching the error of Lloyd@25 in a few epochs. On GeoNames, the test keeps almost every candidate, and DISTANCE performs like OFF, which is the library’s default for since version 1.16, without a rule based on dimension.
Figure 2. Median test MSE divided by the median test MSE of Lloyd@25 (dashed line), as a function of the number of epochs (, random initialization). Each number of epochs is a separately trained run. Where curves coincide, they are drawn on top of each other: on KDD Cup 99, the curve of DISTANCE (blue circles) lies under that of ESTIMATE (green crosses, dashed line), from which it differs by at most 2%; on Census 1990, the curve of COUNT (red squares) nearly coincides with that of ESTIMATE.
| Dataset | COUNT | OFF | DISTANCE | ESTIMATE | |
| KDD Cup 99 | 256 | 10 | 1 | 1 | 1 |
| KDD Cup 99 | 1024 | > 10 | 2 | 1 | 2 |
| KDD Cup 99 | 4096 | > 10 | 2 | 2 | 2 |
| Census 1990 | 256 | 1 | 1 | 1 | 1 |
| Census 1990 | 1024 | 2 | 1 | 1 | 2 |
| Census 1990 | 4096 | 2 | 2 | 2 | 2 |
| YearPredictionMSD | 256 | > 10 | > 10 | > 10 | > 10 |
| YearPredictionMSD | 1024 | > 10 | > 10 | > 10 | > 10 |
| YearPredictionMSD | 4096 | 5 | > 10 | > 10 | 5 |
| GeoNames (2-D) | 256 | > 10 | 2 | 2 | 2 |
| GeoNames (2-D) | 1024 | > 10 | 2 | 2 | 2 |
| GeoNames (2-D) | 4096 | > 10 | 2 | 2 | 2 |
| Household power | 256 | 5 | 1 | 1 | 1 |
| Household power | 1024 | 2 | 2 | 2 | 2 |
| Shuttle | 256 | > 10 | 5 | 5 | 5 |
| Shuttle | 1024 | > 10 | 10 | 10 | 10 |
| Covertype (z-score) | 256 | > 10 | 1 | 1 | 1 |
| Covertype (z-score) | 1024 | 3 | 3 | 2 | 2 |
| Covertype (z-score) | 4096 | 3 | 5 | 5 | 5 |
| Covertype (min-max) | 256 | 1 | 1 | 1 | 1 |
| Covertype (min-max) | 1024 | 3 | 3 | 3 | 3 |
| Covertype (min-max) | 4096 | 3 | 5 | 3 | 3 |
Table 8. Smallest tested number of epochs at which a method’s median test MSE is below the median test MSE of Lloyd@25, from random initialization. Each number of epochs is a separately trained run; “> 10”: not reached with any tested number of epochs up to 10.
k-means++ Initialization
With k-means++ initialization, the failure of count-based revival is larger: k-means++ places centres on rare groups, and count-based revival removes them. After two epochs with , COUNT ends far above the test error of Lloyd@25 started from the same centres: at more than 25 times that error on KDD Cup 99, and 76% above it on GeoNames. DISTANCE keeps those centres and ends within 1% of Lloyd@25 on both datasets, as does OFF (Table 10; Appendix § 9.§ 2 gives the other numbers of epochs).
| Dataset | Seeds | COUNT | OFF | DISTANCE | ESTIMATE | W/T/L | W/T/L | |||||
| Held-out datasets | ||||||||||||
| KDD Cup 99 | 256 | 10 | 13.073 | 1.016 | 1.016 | 1.014 | −92.2% | 10/0/0 | 0.504 | +0.0% | 1/9/0 | 1.000 |
| KDD Cup 99 | 1024 | 10 | 25.672 | 1.006 | 1.006 | 1.005 | −96.1% | 10/0/0 | 0.504 | −0.0% | 6/1/3 | 1.000 |
| KDD Cup 99 | 4096 | 10 | 4.466 | 1.008 | 1.007 | 1.007 | −77.6% | 10/0/0 | 0.504 | −0.0% | 6/1/3 | 1.000 |
| Census 1990 | 256 | 10 | 0.996 | 0.996 | 0.996 | 0.996 | +0.0% | 4/5/1 | 1.000 | +0.0% | 3/1/6 | 1.000 |
| Census 1990 | 1024 | 10 | 0.997 | 0.995 | 0.996 | 0.997 | −0.1% | 10/0/0 | 0.504 | +0.1% | 2/0/8 | 1.000 |
| Census 1990 | 4096 | 10 | 1.002 | 0.997 | 0.999 | 1.001 | −0.2% | 10/0/0 | 0.504 | +0.2% | 0/0/10 | 0.504 |
| YearPredictionMSD | 256 | 10 | 1.020 | 1.029 | 1.025 | 1.011 | +0.4% | 1/0/9 | 1.000 | −0.5% | 10/0/0 | 0.504 |
| YearPredictionMSD | 1024 | 10 | 1.008 | 1.025 | 1.017 | 1.007 | +1.0% | 0/0/10 | 0.504 | −0.8% | 10/0/0 | 0.504 |
| YearPredictionMSD | 4096 | 10 | 0.997 | 1.026 | 1.012 | 1.003 | +1.4% | 0/0/10 | 0.504 | −1.4% | 10/0/0 | 0.504 |
| GeoNames (2-D) | 256 | 10 | 1.304 | 1.003 | 1.003 | 1.003 | −23.2% | 10/0/0 | 0.504 | +0.0% | 0/10/0 | 1.000 |
| GeoNames (2-D) | 1024 | 10 | 1.755 | 0.994 | 0.996 | 1.001 | −43.5% | 10/0/0 | 0.504 | +0.0% | 2/6/2 | 1.000 |
| GeoNames (2-D) | 4096 | 10 | 1.603 | 1.007 | 1.008 | 1.017 | −37.9% | 10/0/0 | 0.504 | +0.1% | 3/0/7 | 1.000 |
| Development datasets | ||||||||||||
| Covertype (z-score) | 256 | 10 | 2.262 | 0.998 | 0.998 | 0.998 | −55.8% | 10/0/0 | 0.223 | +0.0% | 4/4/2 | 1.000 |
| Covertype (z-score) | 1024 | 10 | 1.006 | 0.998 | 0.999 | 0.998 | −0.7% | 10/0/0 | 0.223 | −0.0% | 6/1/3 | 1.000 |
| Covertype (z-score) | 4096 | 10 | 1.009 | 1.007 | 1.007 | 1.007 | −0.2% | 10/0/0 | 0.223 | +0.1% | 2/0/8 | 1.000 |
| Covertype (min-max) | 256 | 10 | 1.044 | 0.998 | 0.996 | 0.996 | −3.8% | 10/0/0 | 0.223 | −0.1% | 8/1/1 | 0.691 |
| Covertype (min-max) | 1024 | 10 | 1.018 | 1.000 | 1.001 | 1.000 | −1.7% | 10/0/0 | 0.223 | −0.0% | 5/1/4 | 1.000 |
| Covertype (min-max) | 4096 | 10 | 1.010 | 1.004 | 1.004 | 1.004 | −0.5% | 10/0/0 | 0.223 | +0.0% | 4/0/6 | 1.000 |
Table 10. k-means++ initialization, 2 epochs. Median test MSE / median test MSE of Lloyd@25 distance vs. count distance vs. off.
Bound versus Utility Estimate
In most configurations, the online utility estimate (ESTIMATE) is not better than the bound (DISTANCE); YearPredictionMSD is the exception (Table 15).
| Dataset | test () | test () | W/T/L () | Time ratio | |
| KDD Cup 99 | 256 | +0.1% | +0.1% | 13/0/17 | 0.72 |
| KDD Cup 99 | 1024 | −0.1% | −0.9% | 16/0/14 | 0.53 |
| KDD Cup 99 | 4096 | −1.6% | −2.8% | 20/0/10 | 0.48 |
| Census 1990 | 256 | +0.0% | +0.0% | 3/19/8 | 0.82 |
| Census 1990 | 1024 | −0.1% | +0.0% | 22/4/4 | 0.57 |
| Census 1990 | 4096 | −0.1% | −0.1% | 26/0/4 | 0.71 |
| YearPredictionMSD | 256 | +1.0% | +0.4% | 0/0/30 | 0.67 |
| YearPredictionMSD | 1024 | +0.4% | +1.7% | 0/0/30 | 0.55 |
| YearPredictionMSD | 4096 | +0.2% | +0.6% | 3/0/27 | 0.51 |
| GeoNames (2-D) | 256 | +0.0% | +0.0% | 10/17/3 | 0.60 |
| GeoNames (2-D) | 1024 | +0.0% | +0.0% | 14/3/13 | 0.55 |
| GeoNames (2-D) | 4096 | −1.3% | −0.2% | 24/0/6 | 0.50 |
| Household power | 256 | −0.2% | +0.4% | 6/1/3 | 0.61 |
| Household power | 1024 | −0.5% | +0.5% | 8/0/2 | 0.56 |
| Shuttle | 256 | −1.6% | −0.6% | 7/0/3 | 0.75 |
| Shuttle | 1024 | +0.4% | −0.0% | 4/0/6 | 0.62 |
| Covertype (z-score) | 256 | +0.1% | +0.0% | 11/1/18 | 0.72 |
| Covertype (z-score) | 1024 | +0.1% | +0.1% | 10/0/20 | 0.62 |
| Covertype (z-score) | 4096 | +0.0% | −0.0% | 14/1/15 | 0.61 |
| Covertype (min-max) | 256 | +0.0% | +0.0% | 9/16/5 | 0.74 |
| Covertype (min-max) | 1024 | +0.0% | −0.0% | 7/3/20 | 0.64 |
| Covertype (min-max) | 4096 | +0.0% | +0.1% | 10/1/19 | 0.67 |
| DEEP 1M | 16384 | −0.0% | −0.0% | 3/0/2 | 0.52 |
| SIFT 1M | 16384 | +0.0% | +0.0% | 2/0/3 | 0.80 |
Table 15. DISTANCE (bound) versus ESTIMATE (utility estimate), random initialization: median over seeds of the relative change in the test MSE of DISTANCE with respect to ESTIMATE after 2 and 5 epochs, W/T/L after 2 epochs, and the median ratio of the running time of DISTANCE to that of ESTIMATE. These runs shared their machine with other jobs, so the times are noisy; § 5.6 reports controlled timings.
Rare points far from all others. On such data, the bound is much better in training error. On KDD Cup 99 after 2 epochs (), the training error of DISTANCE is roughly 30–40% lower than that of ESTIMATE, and its test error is slightly lower (by less than 2%). Covertype shows the same pattern in training error.
Other datasets. On Census, GeoNames, Shuttle and the embedding datasets, the two are equal or the bound is slightly better. On household power, the bound is better after 2 epochs and the estimate after 5 epochs, by less than 1% in both cases. On YearPredictionMSD, the estimate is better: its test MSE is up to about 2% lower than that of DISTANCE (k-means++ initialization, , 5 epochs).
k-means++ initialization. Because centres of unknown utility are kept (Amendment 2 of the protocol), ESTIMATE also keeps the centres placed by k-means++, and ends at about the test error of Lloyd@25 on KDD Cup 99 and GeoNames with . Under the original convention, which treated the removal of a centre that had not yet received any point as free, it removed them.
Running time. The estimate requires an additional search for the two nearest centres of every point in every batch, which makes runs markedly slower (§ 5.6). On GPUs, the library’s assignment kernel, which returns only the nearest centre, would need a variant that also returns the second-nearest one.
We keep the bound as the default: in our timings it adds no measurable running time, and it requires only the centres, not the points of the cluster.
Sensitivity and the Abandonment Clause
Threshold (Table 16; 10 seeds). On KDD Cup 99 and GeoNames, values from 2 to 8 give nearly the same results (within about 1.5 percentage points of each other). Larger values keep fewer candidates and give up part of the gain, up to several percentage points for on KDD Cup 99 after 10 epochs. On Covertype with , every value stays within 1% of COUNT, since few candidates there are far from other centres. On DEEP 1M, keeps redundant candidates and raises the test MSE by about 2%; keeps several hundred candidates in total over ten runs, with a negligible change in test MSE; and with , the runs are identical to those of the library. In our experiments, the exact value of therefore matters little, as long as it lies roughly between 2 and 8.
| Dataset | 2 | 3 | 4 | 6 | 8 | 16 | 32 | No clause | off | ||||
| Covertype (z-score) | 2 | +0.0 | −0.2 | −0.2 | −0.3 | −0.3 | −0.3 | −0.3 | −0.1 | −0.3 | −0.3 | −0.3 | +0.6 |
| Covertype (z-score) | 5 | −0.2 | −0.3 | −0.2 | −0.1 | −0.2 | −0.4 | −0.3 | −0.1 | −0.2 | −0.1 | −0.1 | +0.6 |
| Covertype (z-score) | 10 | −0.4 | −0.5 | −0.6 | −0.6 | −0.6 | −0.5 | −0.5 | −0.2 | −0.5 | −0.4 | −0.3 | +0.5 |
| KDD Cup 99 | 2 | −80.7 | −82.5 | −81.3 | −82.3 | −82.3 | −82.2 | −82.0 | −81.6 | −82.1 | −82.3 | −82.3 | −79.0 |
| KDD Cup 99 | 5 | −79.3 | −79.6 | −78.9 | −78.5 | −78.3 | −78.3 | −78.3 | −78.3 | −76.8 | −78.5 | −78.5 | −72.6 |
| KDD Cup 99 | 10 | −62.7 | −58.9 | −58.9 | −59.6 | −58.5 | −58.8 | −57.3 | −52.3 | −57.2 | −59.6 | −59.6 | −47.7 |
| GeoNames (2-D) | 2 | −24.8 | −24.9 | −24.7 | −24.7 | −24.6 | −24.1 | −20.1 | −20.4 | −24.7 | −24.7 | −24.7 | −25.7 |
| GeoNames (2-D) | 5 | −27.4 | −27.4 | −27.4 | −26.8 | −27.4 | −27.2 | −25.1 | −22.6 | −26.8 | −26.8 | −26.8 | −27.8 |
| GeoNames (2-D) | 10 | −25.4 | −25.4 | −25.4 | −24.7 | −24.4 | −24.2 | −24.2 | −22.6 | −24.7 | −24.7 | −24.7 | −25.3 |
| DEEP 1M | 2 | +2.1 | +0.0 | − | +0.0 | − | +0.0 | − | − | +0.0 | − | − | +3.3 |
| DEEP 1M | 5 | +1.5 | +0.0 | − | +0.0 | − | +0.0 | − | − | +0.0 | − | − | +2.2 |
Table 16. Sensitivity: median over seeds of the relative change (%) in test MSE with respect to COUNT, random initialization, seeds 0–9, ( for DEEP 1M). Columns: values of , waiting periods (in epochs), no abandonment clause, and OFF.
Abandonment clause. The clause can act only in runs longer than two epochs. In those runs on the held-out datasets, it removes at least one candidate in about 9% of the runs, and it accounts for about 0.2% of all removals (75 of 800 runs; 253 of 136,890 removals). Removing it changes the median test MSE negligibly (by at most a few hundredths of a percent) in every held-out configuration. In our experiments, the abandonment clause therefore had no measurable benefit, and the gains come from the distance test. We keep it as the safeguard motivated in § 4, since it adds no measurable cost; a simpler rule could omit it.
Waiting period. Shortening it to epoch is harmful, as Proposition 2 predicts. On KDD Cup 99 () after 5 epochs, the reduction in training error relative to COUNT falls from about 80% to about 65%.
Running Time
We timed the library, DISTANCE and ESTIMATE on one server, with an AMD Ryzen Threadripper 3990X processor (64 cores), 188 GiB of memory and Ubuntu 24.04, using 16 threads and with no other jobs of ours running (Appendix § 10 gives the full specification and the software versions), for 2 epochs from the same random initialization, on DEEP 1M () and KDD Cup 99 (). We repeated each measurement 6 times and rotated the order of the three methods across repetitions (Table 3). In both configurations, the additional work of the distance test (one
| Dataset | Library (COUNT) | DISTANCE | ESTIMATE |
| DEEP 1M, | 32.9 | 32.9 | 90.3 |
| KDD Cup 99, | 11.9 | 12.0 | 27.6 |
Table 3. Running time in seconds, 2 epochs from random initialization, one server (AMD Ryzen Threadripper 3990X) with 16 threads; medians over 6 repetitions. Per repetition, the ratio of the running time of DISTANCE to that of the library is 0.98–1.04.
EMA, and a nearest-centre search for the candidates every five batches) is within the variation between repetitions: per repetition, the running time of DISTANCE is within a few percent of that of the library, in both directions. The search for the two nearest centres of every point in every batch makes ESTIMATE more than twice as slow with FAISS’s exact (brute-force) CPU search.
Mechanism and Downsides
Mechanism. Figure 3 shows why a single threshold separates the two settings. On the embedding datasets, every candidate is close to another centre. On the tabular datasets, a minority of candidates, whose removal is very costly, lie far from all other centres (up to five orders of magnitude above MSE on KDD Cup 99 and Covertype), and on GeoNames most candidates do. The gains come from the points with the largest errors: the mean of the largest 0.1% of the per-point training errors decreases more than fourfold on KDD Cup 99 () and by almost two orders of magnitude on Covertype () (Table 17). On the synthetic far groups, COUNT keeps no far group of up to 150 points (less than a tenth of the size of a typical cluster), whereas DISTANCE keeps about as many as OFF and Lloyd@25, and all five from k-means++ initialization once a group has at least 150 points (Table 18).
Table 17: Cluster-size imbalance (1 when all clusters have the same size) and mean of the largest 0.1% of the per-point training errors; random initialization, 2 epochs, medians over seeds.
| Dataset | Imbalance COUNT | Imbalance DISTANCE | Mean of the worst 0.1% errors COUNT | Mean of the worst 0.1% errors DISTANCE | |
| KDD Cup 99 | 256 | 2.08 | 2.09 | 2.4e+04 | 1.09e+04 |
| KDD Cup 99 | 1024 | 1.57 | 1.57 | 1.93e+04 | 4.16e+03 |
| KDD Cup 99 | 4096 | 1.75 | 1.76 | 1.42e+04 | 2.48e+03 |
| Census 1990 | 256 | 1.36 | 1.37 | 151 | 151 |
| Census 1990 | 1024 | 1.29 | 1.30 | 129 | 127 |
| Census 1990 | 4096 | 1.25 | 1.25 | 102 | 99.1 |
| YearPredictionMSD | 256 | 1.50 | 2.20 | 2.46e+03 | 1.58e+03 |
| YearPredictionMSD | 1024 | 1.43 | 1.78 | 2.02e+03 | 1.31e+03 |
| YearPredictionMSD | 4096 | 1.38 | 1.56 | 1.58e+03 | 1.06e+03 |
| GeoNames (2-D) | 256 | 1.24 | 1.27 | 2.04e+03 | 1.18e+03 |
| GeoNames (2-D) | 1024 | 1.21 | 1.22 | 825 | 393 |
| GeoNames (2-D) | 4096 | 1.17 | 1.17 | 235 | 167 |
| Household power | 256 | 1.40 | 1.44 | 26.3 | 20 |
| Household power | 1024 | 1.25 | 1.26 | 12.5 | 12.3 |
| Shuttle | 256 | 1.27 | 1.28 | 1.67e+03 | 215 |
| Shuttle | 1024 | 1.32 | 1.33 | 431 | 200 |
| Covertype (z-score) | 256 | 1.37 | 1.35 | 3.71e+03 | 41.8 |
| Covertype (z-score) | 1024 | 1.22 | 1.22 | 1.02e+03 | 27.7 |
| Covertype (z-score) | 4096 | 1.17 | 1.18 | 965 | 12.8 |
| Covertype (min-max) | 256 | 1.24 | 1.26 | 1.49 | 1.48 |
| Covertype (min-max) | 1024 | 1.21 | 1.21 | 0.872 | 0.758 |
| Covertype (min-max) | 4096 | 1.17 | 1.18 | 0.281 | 0.269 |
Table 17.
Downsides. We observed two, both anticipated by the analysis.
The first is that the test ignores the error reduction of the split, which shows on YearPredictionMSD. There, the largest increase in test error of DISTANCE relative to COUNT is below 3% (k-means++ initialization, , 10 epochs; higher in all ten seeds), and such increases appear for larger and more epochs. To understand it, we logged both quantities along one run of DISTANCE (, 10 epochs, seed 0). The test keeps most candidates (more than 90%, counted once per revival check). For about four-fifths of the kept candidates, the utility estimate also exceeds ; for these, the bound and the estimate nearly coincide (median ratio close to 1), and the median estimated utility per point is about ten times MSE. Most kept clusters are therefore costly per point by either measure. A plausible explanation is that splitting large clusters reduces the error more than keeping these few costly points saves, and the per-point test does not account for that reduction. We did not measure the error reduction of the splits directly. The kept candidates on which the two measures disagree may also contribute, through their effect on the rest of the run. Keeping candidates also makes the cluster sizes less uniform on this dataset: the imbalance , which equals 1 when all clusters have the same size, rises by almost half for (Table 17).
The second is the single, global error scale, which shows when cluster scales differ widely. On a two-dimensional mixture of 90 tight and 10 broad Gaussian blobs (Appendix § 9.§ 6), the test keeps redundant small clusters inside the broad blobs. The median change in MSE of DISTANCE relative to COUNT is then an increase of about 7% with random initialization, but a decrease of about 13% with k-means++ initialization, because COUNT then removes the centres that k-means++ placed in sparse regions. In 16 dimensions, the median change is negligible (Table 18).
Both downsides point to the same refinement: compare the cost of a removal with the error reduction of the split that would replace the removed cluster, and measure both relative to a local error scale.
Related Work
Removal cost and utility. The cost of removing a centre while the other centres are kept fixed, over its points, is Fritzke’s utility. Methods that use it differ in how they act on it. LBG-U and k-means-u* [15, 16] move the centre of lowest utility next to the centre with the largest error, run Lloyd’s algorithm on the full data, and keep the move only if the total error decreases. Breathing k-means [17] alternately adds centres near centres with large error and removes the centres of lowest utility, with Lloyd’s algorithm in between; it does not remove the nearest neighbour of a centre selected for removal in the same step (freezing), so that two adjacent centres are not removed together. GNG-U [14] is an online rule for growing neural gas [13], a network of units (centres) that is adapted one point at a time; it removes the unit of lowest utility when the ratio of the largest error to that utility exceeds a threshold, so removal is triggered by the utility itself, not by a count. Iterative shrinking and the pairwise nearest neighbour (PNN) method [11, 12, 36] reduce the number of clusters greedily, removing the cluster, or merging the pair of clusters, whose removal or merge costs least. Fritzke already notes that centres with close neighbours tend to have lower utility than isolated ones [16]. Our contribution is narrower: for mini-batch k-means, a bound on the removal cost that is computed from the centres alone and used as an additional condition on a count-based removal rule, so that the algorithm is unchanged wherever the count-based rule already works.
Revival in mini-batch k-means and vector-quantized neural networks. All the revival rules for mini-batch k-means and for vector-quantized neural networks that we found decide by count, or by the time since a centre was last used, alone. They include the reassignment step of scikit-learn’s MiniBatchKMeans [28, 29], e-means [6], and the resets of rarely used code vectors (the learned centres) in neural vector quantizers [9, 22, 35] [38, 39]; one of these, the vector-quantize-pytorch library, uses the same threshold as e-means (a tenth of the average count). Full-batch implementations relocate only empty clusters [10, 27]. ISODATA [3] discards small clusters and merges close ones, but through two separate rules. Online k-means with remove-birth updating [18] moves the unit that has been nearest to the fewest points, again a count-based criterion. We are not aware of a count-based revival rule that also checks whether the centre of a small cluster is far from the other centres.
Outliers. Outlier-aware variants of k-means, such as k-means− [8], decide which points to ignore. Our question is which centres to keep: a small isolated group is what an outlier-aware method may discard, and what the k-means objective rewards covering.
Limitations and Future Work
Scale and hardware. All results come from CPU runs of the library’s NumPy implementation. The tabular datasets have at most 2M points. The embedding evaluations cover the e-means paper’s configurations with points and one configuration with points (3 seeds, 2 epochs), in which we only verified that the results are identical to the library’s. We did not run the GPU or multi-GPU implementations, or datasets with more than points. The rule requires no new GPU kernel (§ 4), but its running time in the GPU implementation, with CUDA-graph replay, is unmeasured.
Hyperparameters. was chosen on the development data as a margin above the largest ratio observed on embedding data, and fixed before the evaluation on held-out datasets. On held-out data, values from 2 to 8 give nearly the same results, and larger values give up part of the gain (§ 5.5). A principled choice, for example one that compares the removal cost with the expected error reduction of the split that would replace the removed cluster, remains open.
Simultaneous removals. The bound concerns the removal of one centre at a time; two neighbouring candidates can be removed together (§ 4). Freezing, as in breathing k-means, would prevent this; we did not measure how often it occurs.
A single error scale. is an average over all clusters. When cluster scales differ widely, a redundant small cluster in a broad region can appear far from other centres relative to , and be kept. Our heterogeneous-scale experiment shows this effect in two dimensions (a median increase in MSE of about 7% relative to count-based revival, from random initialization) but not in sixteen (§ 5.7). A local scale, for example the per-point error of the neighbouring cluster, is a natural variant.
Downsides. Keeping small clusters spends centres on rare groups, which the k-means objective rewards, but makes cluster sizes less uniform where many candidates are kept (on YearPredictionMSD with , the imbalance rises by almost half); elsewhere the change is small (Table 17). The same dataset shows the cost of ignoring the error reduction of the split (§ 5.7). For an inverted-file index for nearest-neighbour search, which stores one list of points per cluster [10], balanced cluster sizes may matter more than squared error. On the embedding datasets we tested, the rule changes nothing.
Running time. Our running-time measurements cover two configurations on one CPU server.
Future work. GPU and multi-GPU implementations; comparing the removal cost with the error reduction of the split that would replace the removed cluster; using the same per-point quantity to choose donors (splitting where the error reduction is largest) and split directions; and applying the test to the count-based resets of code vectors in vector-quantized neural networks.
AI Use Statement
Claude Opus 5.5 (Anthropic), used through Claude Code, was used for coding, experiments and writing. GPT-6.1-sol (OpenAI), used through Codex, was used for paper and code reviews, and Claude Fable 5.2 (Anthropic) for reviewing the theoretical results. The authors reviewed all AI-assisted text, figures, and code. We take responsibility for the final content of this paper, including all claims.
Full Results
This appendix gives the full results behind § 5, in Table 4 to Table 18: the non-embedding datasets from random initialization (Appendix § 9.§ 1) and from k-means++ initialization (Appendix § 9.§ 2), the comparison of the bound with the utility estimate (Appendix § 9.§ 3), the sensitivity to the hyperparameters (Appendix § 9.§ 4), the cluster-size imbalance and the tail error (Appendix § 9.§ 5), and the synthetic data (Appendix § 9.§ 6). Appendix § 10 gives further details of the data and of the protocol. The following conventions apply to all these tables.
Seeds. Most configurations have 10 seeds (0–9). The configuration with random initialization and 2 epochs has 30 seeds (0–29) for the six original tabular datasets. The comparisons with ESTIMATE on the embedding datasets have 5 seeds, and the DEEP 10M check has 3. The column “Seeds” gives the number of paired seeds behind each comparison.
Notation. W/T/L counts the seeds in which the test MSE of DISTANCE is lower than, within a relative difference of of, or higher than that of the other method. is the median over seeds of the relative change in test MSE. is the -value of a two-sided Wilcoxon signed-rank test [37], Holm-adjusted [21] within one family of tests per experiment: all 272 comparisons on the held-out datasets, and separately the 120 comparisons on the development datasets.
Lloyd reference. The ratio columns divide each method’s median test MSE by the median test MSE of Lloyd@25 (FAISS’s implementation of Lloyd’s algorithm, 25 iterations on all training points) over seeds 0–9 with the same type of initialization (seeds 0–2 for the embedding datasets; DEEP 10M has no reference). For a given seed, Lloyd@25 and the e-means methods start from the same centres.
Released records. The runs of DISTANCE without the abandonment clause, all timings and all per-run metrics are in the released records (results/runs.jsonl.gz).
Non-Embedding Datasets, Random Initialization
Tables 4 to 7 complement Table 2, which reports 2 epochs, with 1, 3, 5 and 10 epochs; their columns are those of Table 2. Table 8 gives, for each configuration, the smallest tested number of epochs at which each method’s median test MSE is below that of Lloyd@25, which § 5.2 summarizes.
| Dataset | Seeds | COUNT | OFF | DISTANCE | ESTIMATE | W/T/L | W/T/L | |||||
| Held-out datasets | ||||||||||||
| KDD Cup 99 | 256 | 10 | 1.003 | 0.523 | 0.497 | 0.528 | −51.6% | 10/0/0 | 0.504 | −7.7% | 7/0/3 | 1.000 |
| KDD Cup 99 | 1024 | 10 | 2.489 | 0.552 | 0.419 | 0.420 | −82.2% | 10/0/0 | 0.504 | −20.3% | 9/0/1 | 1.000 |
| KDD Cup 99 | 4096 | 10 | 1.084 | 1.007 | 0.908 | 0.922 | −17.2% | 9/0/1 | 1.000 | −8.0% | 9/0/1 | 1.000 |
| Census 1990 | 256 | 10 | 0.993 | 0.997 | 0.992 | 0.993 | −0.0% | 1/9/0 | 1.000 | −0.4% | 9/0/1 | 0.508 |
| Census 1990 | 1024 | 10 | 0.990 | 0.991 | 0.990 | 0.990 | −0.1% | 9/0/1 | 0.508 | −0.0% | 5/1/4 | 1.000 |
| Census 1990 | 4096 | 10 | 0.990 | 0.987 | 0.989 | 0.990 | −0.1% | 8/0/2 | 1.000 | +0.1% | 3/0/7 | 1.000 |
| YearPredictionMSD | 256 | 10 | 1.016 | 1.031 | 1.026 | 1.009 | +0.8% | 0/0/10 | 0.504 | −0.5% | 10/0/0 | 0.504 |
| YearPredictionMSD | 1024 | 10 | 1.009 | 1.027 | 1.012 | 1.004 | +0.4% | 2/0/8 | 1.000 | −1.5% | 10/0/0 | 0.504 |
| YearPredictionMSD | 4096 | 10 | 1.000 | 1.021 | 1.004 | 1.001 | +0.5% | 0/1/9 | 0.504 | −1.8% | 10/0/0 | 0.504 |
| GeoNames (2-D) | 256 | 10 | 1.024 | 0.886 | 0.882 | 0.903 | −9.7% | 10/0/0 | 0.504 | +0.0% | 3/3/4 | 1.000 |
| GeoNames (2-D) | 1024 | 10 | 1.216 | 0.895 | 0.905 | 0.913 | −27.9% | 9/0/1 | 0.508 | +0.1% | 4/1/5 | 1.000 |
| GeoNames (2-D) | 4096 | 10 | 1.064 | 0.942 | 0.942 | 0.950 | −11.8% | 10/0/0 | 0.504 | −0.6% | 7/0/3 | 1.000 |
| Development datasets | ||||||||||||
| Covertype (z-score) | 256 | 10 | 1.445 | 0.752 | 0.743 | 0.743 | −48.7% | 10/0/0 | 0.223 | −1.4% | 10/0/0 | 0.223 |
| Covertype (z-score) | 1024 | 10 | 0.985 | 0.992 | 0.983 | 0.982 | −0.3% | 9/0/1 | 0.793 | −0.9% | 10/0/0 | 0.223 |
| Covertype (z-score) | 4096 | 10 | 1.000 | 1.002 | 1.000 | 1.000 | −0.0% | 7/0/3 | 1.000 | −0.1% | 10/0/0 | 0.223 |
| Covertype (min-max) | 256 | 10 | 0.975 | 0.971 | 0.972 | 0.972 | −0.3% | 7/0/3 | 1.000 | −0.0% | 4/2/4 | 1.000 |
| Covertype (min-max) | 1024 | 10 | 0.999 | 0.998 | 0.989 | 0.992 | −0.6% | 9/0/1 | 0.285 | −0.2% | 9/0/1 | 0.977 |
| Covertype (min-max) | 4096 | 10 | 0.997 | 1.002 | 0.998 | 0.999 | +0.0% | 5/0/5 | 1.000 | −0.3% | 9/1/0 | 0.285 |
Table 5. Random initialization, 3 epochs.
| Dataset | Seeds | COUNT | OFF | DISTANCE | ESTIMATE | DISTANCE VS. COUNT | W/T/L | DISTANCE VS. OFF | W/T/L | |||
| Held-out datasets | ||||||||||||
| KDD Cup 99 | 256 | 10 | 1.027 | 0.616 | 0.583 | 0.579 | −41.2% | 10/0/0 | 0.504 | −2.9% | 7/0/3 | 1.000 |
| KDD Cup 99 | 1024 | 10 | 2.068 | 0.580 | 0.419 | 0.421 | −78.5% | 10/0/0 | 0.504 | −17.0% | 10/0/0 | 0.504 |
| KDD Cup 99 | 4096 | 10 | 1.092 | 0.779 | 0.690 | 0.713 | −36.1% | 10/0/0 | 0.504 | −9.6% | 9/0/1 | 0.508 |
| Census 1990 | 256 | 10 | 0.992 | 0.994 | 0.991 | 0.992 | +0.0% | 1/9/0 | 1.000 | −0.3% | 9/1/0 | 0.504 |
| Census 1990 | 1024 | 10 | 0.994 | 0.995 | 0.994 | 0.994 | +0.0% | 3/3/4 | 1.000 | −0.0% | 6/1/3 | 1.000 |
| Census 1990 | 4096 | 10 | 0.988 | 0.987 | 0.987 | 0.988 | −0.2% | 7/2/1 | 1.000 | +0.0% | 4/0/6 | 1.000 |
| YearPredictionMSD | 256 | 10 | 1.011 | 1.013 | 1.009 | 1.006 | −0.2% | 6/1/3 | 1.000 | −0.3% | 9/1/0 | 0.508 |
| YearPredictionMSD | 1024 | 10 | 1.006 | 1.032 | 1.021 | 1.004 | +1.7% | 0/0/10 | 0.504 | −1.1% | 10/0/0 | 0.504 |
| YearPredictionMSD | 4096 | 10 | 0.998 | 1.025 | 1.004 | 0.998 | +0.6% | 0/0/10 | 0.504 | −2.2% | 10/0/0 | 0.504 |
| GeoNames (2-D) | 256 | 10 | 1.008 | 0.906 | 0.890 | 0.916 | −10.1% | 10/0/0 | 0.504 | +0.0% | 4/4/2 | 1.000 |
| GeoNames (2-D) | 1024 | 10 | 1.185 | 0.856 | 0.868 | 0.866 | −26.8% | 10/0/0 | 0.504 | −0.0% | 6/0/4 | 1.000 |
| GeoNames (2-D) | 4096 | 10 | 1.047 | 0.906 | 0.909 | 0.893 | −13.6% | 10/0/0 | 0.504 | −0.2% | 6/0/4 | 1.000 |
| Household power | 256 | 10 | 1.000 | 0.933 | 0.936 | 0.931 | −6.5% | 10/0/0 | 0.504 | +0.2% | 4/1/5 | 1.000 |
| Household power | 1024 | 10 | 0.935 | 0.923 | 0.922 | 0.921 | −0.6% | 6/0/4 | 1.000 | +0.4% | 4/0/6 | 1.000 |
| Shuttle | 256 | 10 | 3.205 | 0.930 | 0.969 | 0.970 | −69.1% | 10/0/0 | 0.504 | +2.7% | 1/0/9 | 1.000 |
| Shuttle | 1024 | 10 | 1.584 | 1.005 | 1.019 | 1.021 | −36.3% | 10/0/0 | 0.504 | +0.7% | 3/0/7 | 1.000 |
| Development datasets | ||||||||||||
| Covertype (z-score) | 256 | 10 | 1.267 | 0.763 | 0.746 | 0.745 | −39.1% | 10/0/0 | 0.223 | −0.9% | 10/0/0 | 0.223 |
| Covertype (z-score) | 1024 | 10 | 0.981 | 0.988 | 0.976 | 0.977 | −0.1% | 8/0/2 | 1.000 | −0.8% | 10/0/0 | 0.223 |
| Covertype (z-score) | 4096 | 10 | 0.994 | 0.994 | 0.993 | 0.993 | −0.1% | 8/1/1 | 0.977 | −0.1% | 5/2/3 | 1.000 |
| Covertype (min-max) | 256 | 10 | 0.989 | 0.982 | 0.978 | 0.978 | −0.8% | 9/0/1 | 0.977 | −0.2% | 8/1/1 | 1.000 |
| Covertype (min-max) | 1024 | 10 | 0.995 | 0.995 | 0.986 | 0.990 | −0.8% | 8/0/2 | 0.625 | −0.3% | 9/0/1 | 0.793 |
| Covertype (min-max) | 4096 | 10 | 0.989 | 0.993 | 0.990 | 0.989 | +0.0% | 4/1/5 | 1.000 | −0.3% | 10/0/0 | 0.223 |
Table 6. Random initialization, 5 epochs. Median test MSE / median test MSE of Lloyd@25 distance vs. count distance vs. off.
| Dataset | Seeds | COUNT | OFF | DISTANCE | ESTIMATE | DISTANCE VS. COUNT | W/T/L | DISTANCE VS. OFF | W/T/L | |||
| Held-out datasets | ||||||||||||
| KDD Cup 99 | 256 | 10 | 0.938 | 0.578 | 0.521 | 0.547 | −41.9% | 10/0/0 | 0.504 | −4.3% | 7/0/3 | 1.000 |
| KDD Cup 99 | 1024 | 10 | 1.428 | 0.585 | 0.435 | 0.443 | −59.6% | 10/0/0 | 0.504 | −15.4% | 10/0/0 | 0.504 |
| KDD Cup 99 | 4096 | 10 | 1.145 | 0.755 | 0.670 | 0.681 | −38.9% | 10/0/0 | 0.504 | −9.9% | 10/0/0 | 0.504 |
| Census 1990 | 256 | 10 | 0.994 | 0.996 | 0.994 | 0.994 | −0.0% | 8/1/1 | 1.000 | −0.2% | 8/1/1 | 1.000 |
| Census 1990 | 1024 | 10 | 0.997 | 0.998 | 0.997 | 0.997 | +0.0% | 3/5/2 | 1.000 | −0.0% | 4/2/4 | 1.000 |
| Census 1990 | 4096 | 10 | 0.991 | 0.991 | 0.991 | 0.991 | −0.0% | 5/0/5 | 1.000 | +0.0% | 2/2/6 | 1.000 |
| YearPredictionMSD | 256 | 10 | 1.013 | 1.003 | 1.004 | 1.003 | −0.9% | 10/0/0 | 0.504 | +0.1% | 4/0/6 | 1.000 |
| YearPredictionMSD | 1024 | 10 | 1.002 | 1.018 | 1.013 | 1.002 | +1.1% | 0/0/10 | 0.504 | −0.4% | 10/0/0 | 0.504 |
| YearPredictionMSD | 4096 | 10 | 0.997 | 1.028 | 1.010 | 0.998 | +1.5% | 0/0/10 | 0.504 | −1.7% | 10/0/0 | 0.504 |
| GeoNames (2-D) | 256 | 10 | 1.007 | 0.896 | 0.887 | 0.918 | −11.3% | 10/0/0 | 0.504 | −0.4% | 6/3/1 | 1.000 |
| GeoNames (2-D) | 1024 | 10 | 1.170 | 0.846 | 0.856 | 0.859 | −24.7% | 10/0/0 | 0.504 | −0.2% | 5/0/5 | 1.000 |
| GeoNames (2-D) | 4096 | 10 | 1.020 | 0.896 | 0.886 | 0.891 | −15.4% | 10/0/0 | 0.504 | −0.6% | 7/0/3 | 1.000 |
| Household power | 256 | 10 | 0.996 | 0.929 | 0.935 | 0.929 | −4.5% | 10/0/0 | 0.504 | +0.2% | 1/1/8 | 1.000 |
| Household power | 1024 | 10 | 0.916 | 0.891 | 0.902 | 0.902 | −1.3% | 8/1/1 | 1.000 | +0.2% | 5/0/5 | 1.000 |
| Shuttle | 256 | 10 | 3.587 | 0.917 | 0.926 | 0.937 | −74.0% | 10/0/0 | 0.504 | +1.0% | 1/0/9 | 0.508 |
| Shuttle | 1024 | 10 | 1.253 | 0.948 | 0.952 | 0.949 | −24.0% | 10/0/0 | 0.504 | +0.2% | 1/1/8 | 0.721 |
| Development datasets | ||||||||||||
| Covertype (z-score) | 256 | 10 | 1.166 | 1.009 | 0.998 | 0.998 | −20.3% | 8/0/2 | 0.793 | −0.7% | 10/0/0 | 0.223 |
| Covertype (z-score) | 1024 | 10 | 0.982 | 0.988 | 0.977 | 0.976 | −0.6% | 10/0/0 | 0.223 | −0.9% | 10/0/0 | 0.223 |
| Covertype (z-score) | 4096 | 10 | 0.987 | 0.991 | 0.987 | 0.986 | −0.0% | 5/1/4 | 1.000 | −0.2% | 8/0/2 | 0.625 |
| Covertype (min-max) | 256 | 10 | 1.031 | 1.021 | 1.020 | 1.023 | −0.6% | 9/0/1 | 0.285 | −0.1% | 6/4/0 | 0.819 |
| Covertype (min-max) | 1024 | 10 | 0.990 | 0.984 | 0.981 | 0.983 | −0.6% | 8/0/2 | 0.625 | −0.2% | 9/0/1 | 1.000 |
| Covertype (min-max) | 4096 | 10 | 0.986 | 0.988 | 0.983 | 0.984 | −0.0% | 5/0/5 | 1.000 | −0.3% | 10/0/0 | 0.223 |
Table 7. Random initialization, 10 epochs. Median test MSE / median test MSE of Lloyd@25 distance vs. count distance vs. off.
Non-Embedding Datasets, k-means++ Initialization
Tables 9 to 13 repeat the comparison from k-means++ initialization, with 1, 2, 3, 5 and 10 epochs (§ 5.3); Lloyd@25 starts from the same k-means++ centres as the e-means methods. Table 14 is the counterpart of Table 8.
| Dataset | COUNT | OFF | DISTANCE | ESTIMATE | |
| KDD Cup 99 | 256 | > 10 | > 10 | > 10 | > 10 |
| KDD Cup 99 | 1024 | > 10 | 10 | 10 | 10 |
| KDD Cup 99 | 4096 | > 10 | > 10 | 5 | > 10 |
| Census 1990 | 256 | 2 | 2 | 2 | 2 |
| Census 1990 | 1024 | 2 | 2 | 2 | 2 |
| Census 1990 | 4096 | 5 | 2 | 2 | 3 |
| YearPredictionMSD | 256 | > 10 | > 10 | > 10 | > 10 |
| YearPredictionMSD | 1024 | > 10 | > 10 | > 10 | > 10 |
| YearPredictionMSD | 4096 | 2 | > 10 | > 10 | 5 |
| GeoNames (2-D) | 256 | > 10 | 1 | 1 | 3 |
| GeoNames (2-D) | 1024 | > 10 | 2 | 2 | 3 |
| GeoNames (2-D) | 4096 | > 10 | 5 | 10 | 10 |
| Covertype (z-score) | 256 | > 10 | 2 | 2 | 2 |
| Covertype (z-score) | 1024 | > 10 | 2 | 2 | 2 |
| Covertype (z-score) | 4096 | 5 | 3 | 3 | 3 |
| Covertype (min-max) | 256 | > 10 | 2 | 2 | 2 |
| Covertype (min-max) | 1024 | > 10 | 2 | 3 | 2 |
| Covertype (min-max) | 4096 | 10 | 5 | 3 | 5 |
Table 14. Smallest tested number of epochs at which a method’s median test MSE is below the median test MSE of Lloyd@25, from k-means++ initialization (as in Table 8).
| Dataset | Seeds | COUNT | OFF | DISTANCE | ESTIMATE | W/T/L | W/T/L | |||||
| Held-out datasets | ||||||||||||
| KDD Cup 99 | 256 | 10 | 14.582 | 1.026 | 1.027 | 1.027 | −93.0% | 10/0/0 | 0.504 | +0.0% | 0/9/1 | 1.000 |
| KDD Cup 99 | 1024 | 10 | 30.804 | 1.007 | 1.007 | 1.005 | −96.7% | 10/0/0 | 0.504 | +0.0% | 3/2/5 | 1.000 |
| KDD Cup 99 | 4096 | 10 | 9.445 | 1.013 | 1.013 | 1.020 | −88.5% | 10/0/0 | 0.504 | +0.0% | 3/1/6 | 1.000 |
| Census 1990 | 256 | 10 | 1.001 | 1.001 | 1.001 | 1.001 | +0.0% | 3/5/2 | 1.000 | +0.1% | 3/0/7 | 1.000 |
| Census 1990 | 1024 | 10 | 1.004 | 1.000 | 1.002 | 1.003 | −0.2% | 10/0/0 | 0.504 | +0.3% | 1/0/9 | 1.000 |
| Census 1990 | 4096 | 10 | 1.013 | 1.006 | 1.011 | 1.012 | −0.2% | 10/0/0 | 0.504 | +0.3% | 0/0/10 | 0.504 |
| YearPredictionMSD | 256 | 10 | 1.039 | 1.017 | 1.017 | 1.023 | −2.0% | 10/0/0 | 0.504 | +0.1% | 2/0/8 | 1.000 |
| YearPredictionMSD | 1024 | 10 | 1.024 | 1.022 | 1.018 | 1.019 | −0.6% | 10/0/0 | 0.504 | −0.4% | 10/0/0 | 0.504 |
| YearPredictionMSD | 4096 | 10 | 1.010 | 1.032 | 1.017 | 1.017 | +0.8% | 0/0/10 | 0.504 | −1.4% | 10/0/0 | 0.504 |
| GeoNames (2-D) | 256 | 10 | 1.389 | 0.999 | 0.999 | 1.003 | −27.8% | 10/0/0 | 0.504 | +0.0% | 1/8/1 | 1.000 |
| GeoNames (2-D) | 1024 | 10 | 1.761 | 1.007 | 1.011 | 1.020 | −42.6% | 10/0/0 | 0.504 | +0.2% | 4/0/6 | 1.000 |
| GeoNames (2-D) | 4096 | 10 | 1.918 | 1.024 | 1.040 | 1.054 | −45.8% | 10/0/0 | 0.504 | +1.3% | 0/0/10 | 0.504 |
| Development datasets | ||||||||||||
| Covertype (z-score) | 256 | 10 | 2.589 | 1.003 | 1.003 | 1.003 | −61.3% | 10/0/0 | 0.223 | +0.0% | 3/4/3 | 1.000 |
| Covertype (z-score) | 1024 | 10 | 1.069 | 1.011 | 1.011 | 1.011 | −5.2% | 10/0/0 | 0.223 | +0.0% | 4/0/6 | 1.000 |
| Covertype (z-score) | 4096 | 10 | 1.033 | 1.025 | 1.027 | 1.028 | −0.6% | 10/0/0 | 0.223 | +0.2% | 1/1/8 | 0.625 |
| Covertype (min-max) | 256 | 10 | 1.050 | 1.004 | 1.004 | 1.004 | −4.5% | 10/0/0 | 0.223 | +0.0% | 4/3/3 | 1.000 |
| Covertype (min-max) | 1024 | 10 | 1.034 | 1.011 | 1.011 | 1.010 | −2.5% | 10/0/0 | 0.223 | −0.0% | 5/2/3 | 1.000 |
| Covertype (min-max) | 4096 | 10 | 1.030 | 1.021 | 1.022 | 1.024 | −0.9% | 10/0/0 | 0.223 | +0.2% | 2/1/7 | 1.000 |
Table 9. k-means++ initialization, 1 epoch. Lloyd@25 starts from the same k-means++ centres. Median test MSE / median test MSE of Lloyd@25 distance vs. count distance vs. off.
| Dataset | Seeds | COUNT | OFF | DISTANCE | ESTIMATE | W/T/L | W/T/L | |||||
| Held-out datasets | ||||||||||||
| KDD Cup 99 | 256 | 10 | 12.796 | 1.009 | 1.009 | 1.013 | −92.1% | 10/0/0 | 0.504 | +0.0% | 1/9/0 | 1.000 |
| KDD Cup 99 | 1024 | 10 | 23.796 | 1.004 | 1.003 | 1.002 | −95.8% | 10/0/0 | 0.504 | −0.1% | 8/0/2 | 1.000 |
| KDD Cup 99 | 4096 | 10 | 3.884 | 1.006 | 1.006 | 1.009 | −74.1% | 10/0/0 | 0.504 | −0.0% | 6/0/4 | 1.000 |
| Census 1990 | 256 | 10 | 0.998 | 0.998 | 0.998 | 0.998 | +0.0% | 0/9/1 | 1.000 | +0.0% | 4/3/3 | 1.000 |
| Census 1990 | 1024 | 10 | 0.997 | 0.994 | 0.995 | 0.996 | −0.2% | 10/0/0 | 0.504 | +0.1% | 1/0/9 | 1.000 |
| Census 1990 | 4096 | 10 | 1.000 | 0.996 | 0.997 | 1.000 | −0.3% | 10/0/0 | 0.504 | +0.2% | 1/1/8 | 0.721 |
| YearPredictionMSD | 256 | 10 | 1.016 | 1.035 | 1.028 | 1.009 | +1.0% | 0/0/10 | 0.504 | −0.7% | 10/0/0 | 0.504 |
| YearPredictionMSD | 1024 | 10 | 1.006 | 1.029 | 1.018 | 1.005 | +1.2% | 0/0/10 | 0.504 | −1.1% | 10/0/0 | 0.504 |
| YearPredictionMSD | 4096 | 10 | 0.995 | 1.022 | 1.011 | 1.001 | +1.7% | 0/0/10 | 0.504 | −1.1% | 10/0/0 | 0.504 |
| GeoNames (2-D) | 256 | 10 | 1.301 | 0.995 | 0.995 | 0.996 | −23.9% | 10/0/0 | 0.504 | +0.0% | 0/10/0 | 1.000 |
| GeoNames (2-D) | 1024 | 10 | 1.694 | 0.993 | 0.993 | 0.995 | −41.1% | 10/0/0 | 0.504 | −0.0% | 4/3/3 | 1.000 |
| GeoNames (2-D) | 4096 | 10 | 1.565 | 1.005 | 1.005 | 1.014 | −35.9% | 10/0/0 | 0.504 | +0.1% | 4/0/6 | 1.000 |
| Development datasets | ||||||||||||
| Covertype (z-score) | 256 | 10 | 2.212 | 0.998 | 0.997 | 0.997 | −54.6% | 10/0/0 | 0.223 | −0.0% | 6/3/1 | 1.000 |
| Covertype (z-score) | 1024 | 10 | 1.006 | 0.997 | 0.997 | 0.997 | −1.0% | 10/0/0 | 0.223 | −0.0% | 5/0/5 | 1.000 |
| Covertype (z-score) | 4096 | 10 | 1.001 | 1.000 | 0.999 | 0.999 | −0.2% | 8/0/2 | 0.793 | −0.0% | 5/0/5 | 1.000 |
| Covertype (min-max) | 256 | 10 | 1.043 | 0.996 | 0.994 | 0.994 | −3.9% | 10/0/0 | 0.223 | −0.1% | 8/1/1 | 1.000 |
| Covertype (min-max) | 1024 | 10 | 1.016 | 0.999 | 0.998 | 0.998 | −1.8% | 10/0/0 | 0.223 | −0.0% | 6/2/2 | 1.000 |
| Covertype (min-max) | 4096 | 10 | 1.004 | 1.001 | 0.999 | 1.000 | −0.5% | 10/0/0 | 0.223 | −0.1% | 8/0/2 | 1.000 |
Table 11. k-means++ initialization, 3 epochs. Median test MSE / median test MSE of Lloyd@25. DISTANCE VS. COUNT and DISTANCE VS. OFF.
| Dataset | Seeds | COUNT | OFF | DISTANCE | ESTIMATE | W/T/L | W/T/L | |||||
| Held-out datasets | ||||||||||||
| KDD Cup 99 | 256 | 10 | 11.748 | 1.014 | 1.014 | 1.014 | −91.2% | 10/0/0 | 0.504 | +0.0% | 0/10/0 | 1.000 |
| KDD Cup 99 | 1024 | 10 | 19.774 | 1.004 | 1.003 | 1.003 | −94.9% | 10/0/0 | 0.504 | −0.1% | 6/3/1 | 1.000 |
| KDD Cup 99 | 4096 | 10 | 4.204 | 1.000 | 1.000 | 1.005 | −76.4% | 10/0/0 | 0.504 | −0.0% | 7/1/2 | 1.000 |
| Census 1990 | 256 | 10 | 0.998 | 0.998 | 0.998 | 0.998 | +0.0% | 0/9/1 | 1.000 | +0.0% | 4/1/5 | 1.000 |
| Census 1990 | 1024 | 10 | 0.996 | 0.996 | 0.996 | 0.996 | −0.1% | 8/0/2 | 1.000 | −0.0% | 6/0/4 | 1.000 |
| Census 1990 | 4096 | 10 | 0.999 | 0.995 | 0.995 | 0.998 | −0.3% | 10/0/0 | 0.504 | +0.1% | 2/1/7 | 1.000 |
| YearPredictionMSD | 256 | 10 | 1.013 | 1.016 | 1.013 | 1.005 | −0.0% | 6/0/4 | 1.000 | −0.3% | 10/0/0 | 0.504 |
| YearPredictionMSD | 1024 | 10 | 1.005 | 1.036 | 1.027 | 1.004 | +2.1% | 0/0/10 | 0.504 | −1.1% | 10/0/0 | 0.504 |
| YearPredictionMSD | 4096 | 10 | 0.994 | 1.025 | 1.012 | 0.999 | +1.8% | 0/0/10 | 0.504 | −1.4% | 10/0/0 | 0.504 |
| GeoNames (2-D) | 256 | 10 | 1.310 | 0.998 | 0.998 | 0.998 | −24.2% | 10/0/0 | 0.504 | +0.0% | 0/10/0 | 1.000 |
| GeoNames (2-D) | 1024 | 10 | 1.575 | 0.991 | 0.992 | 0.992 | −37.2% | 10/0/0 | 0.504 | +0.0% | 2/4/4 | 1.000 |
| GeoNames (2-D) | 4096 | 10 | 1.625 | 0.999 | 1.000 | 1.007 | −38.2% | 10/0/0 | 0.504 | +0.2% | 0/0/10 | 0.504 |
| Development datasets | ||||||||||||
| Covertype (z-score) | 256 | 10 | 1.697 | 0.998 | 0.998 | 0.998 | −41.2% | 10/0/0 | 0.223 | +0.0% | 3/6/1 | 1.000 |
| Covertype (z-score) | 1024 | 10 | 1.002 | 0.993 | 0.992 | 0.992 | −1.0% | 10/0/0 | 0.223 | −0.1% | 6/0/4 | 1.000 |
| Covertype (z-score) | 4096 | 10 | 0.997 | 0.994 | 0.994 | 0.995 | −0.2% | 10/0/0 | 1.000 | +0.0% | 2/1/7 | 1.000 |
| Covertype (min-max) | 256 | 10 | 1.033 | 0.997 | 0.995 | 0.995 | −3.7% | 10/0/0 | 0.223 | −0.1% | 7/3/0 | 0.819 |
| Covertype (min-max) | 1024 | 10 | 1.015 | 0.995 | 0.995 | 0.994 | −1.9% | 10/0/0 | 0.223 | −0.0% | 6/3/1 | 1.000 |
| Covertype (min-max) | 4096 | 10 | 1.000 | 0.995 | 0.994 | 0.995 | −0.5% | 10/0/0 | 0.223 | −0.1% | 8/0/2 | 1.000 |
Table 12. k-means++ initialization, 5 epochs. Median test MSE / median test MSE of Lloyd@25. DISTANCE VS. COUNT and DISTANCE VS. OFF.
| Dataset | Seeds | COUNT | OFF | DISTANCE | ESTIMATE | DISTANCE VS. COUNT | DISTANCE VS. COUNT W/T/L | DISTANCE VS. COUNT | DISTANCE VS. OFF | DISTANCE VS. OFF W/T/L | DISTANCE VS. OFF | |
| KDD Cup 99 | 256 | 10 | 11.516 | 1.019 | 1.019 | 1.017 | −91.2% | 10/0/0 | 0.504 | +0.0% | 0/10/0 | 1.000 |
| KDD Cup 99 | 1024 | 10 | 6.495 | 0.997 | 0.996 | 0.996 | −84.0% | 10/0/0 | 0.504 | −0.1% | 7/2/1 | 1.000 |
| KDD Cup 99 | 4096 | 10 | 4.605 | 1.002 | 1.004 | 1.010 | −78.4% | 10/0/0 | 0.504 | +0.1% | 3/1/6 | 1.000 |
| Census 1990 | 256 | 10 | 0.998 | 0.998 | 0.998 | 0.998 | +0.0% | 0/8/2 | 1.000 | +0.0% | 4/1/5 | 1.000 |
| Census 1990 | 1024 | 10 | 0.997 | 0.997 | 0.997 | 0.997 | −0.1% | 7/1/2 | 1.000 | −0.1% | 7/1/2 | 1.000 |
| Census 1990 | 4096 | 10 | 0.998 | 0.995 | 0.996 | 0.997 | −0.2% | 10/0/0 | 0.504 | +0.1% | 3/0/7 | 1.000 |
| YearPredictionMSD | 256 | 10 | 1.011 | 1.006 | 1.005 | 1.005 | −0.5% | 10/0/0 | 0.504 | −0.1% | 6/0/4 | 1.000 |
| YearPredictionMSD | 1024 | 10 | 1.001 | 1.021 | 1.016 | 1.001 | +1.6% | 0/0/10 | 0.504 | −0.5% | 10/0/0 | 0.504 |
| YearPredictionMSD | 4096 | 10 | 0.992 | 1.030 | 1.020 | 0.998 | +2.7% | 0/0/10 | 0.504 | −1.1% | 10/0/0 | 0.504 |
| GeoNames (2-D) | 256 | 10 | 1.315 | 0.994 | 0.994 | 0.992 | −24.3% | 10/0/0 | 0.504 | +0.0% | 0/10/0 | 1.000 |
| GeoNames (2-D) | 1024 | 10 | 1.743 | 0.985 | 0.985 | 0.984 | −43.2% | 10/0/0 | 0.504 | +0.0% | 1/8/1 | 1.000 |
| GeoNames (2-D) | 4096 | 10 | 1.600 | 0.998 | 0.997 | 1.000 | −37.8% | 10/0/0 | 0.504 | +0.0% | 5/0/5 | 1.000 |
| Covertype (z-score) | 256 | 10 | 1.833 | 0.998 | 0.998 | 0.998 | −45.7% | 10/0/0 | 0.223 | +0.0% | 2/7/1 | 1.000 |
| Covertype (z-score) | 1024 | 10 | 1.004 | 0.994 | 0.993 | 0.993 | −1.2% | 10/0/0 | 0.223 | −0.1% | 8/1/1 | 0.393 |
| Covertype (z-score) | 4096 | 10 | 0.994 | 0.991 | 0.992 | 0.992 | −0.3% | 8/0/2 | 0.625 | +0.1% | 3/0/7 | 1.000 |
| Covertype (min-max) | 256 | 10 | 1.035 | 1.002 | 1.001 | 1.001 | −3.6% | 10/0/0 | 0.223 | −0.1% | 5/4/1 | 1.000 |
| Covertype (min-max) | 1024 | 10 | 1.011 | 0.995 | 0.994 | 0.993 | −1.6% | 10/0/0 | 0.223 | −0.1% | 7/0/3 | 1.000 |
| Covertype (min-max) | 4096 | 10 | 0.997 | 0.991 | 0.991 | 0.991 | −0.6% | 9/0/1 | 0.285 | −0.1% | 6/1/3 | 1.000 |
Table 13. k-means++ initialization, 10 epochs. Median test MSE / median test MSE of Lloyd@25. DISTANCE VS. COUNT and DISTANCE VS. OFF comparisons.
Bound versus Utility Estimate
Table 15 compares DISTANCE (the bound) with ESTIMATE (the online utility estimate) on the tabular datasets and on DEEP 1M and SIFT 1M (§ 5.4).
Sensitivity
Table 16 gives the effect of the threshold , of the waiting period and of removing the abandonment clause (§ 5.5).
Cluster-Size Imbalance and Tail Error
Table 17 gives two quantities other than the MSE that § 5.7 discusses: how unequal the cluster sizes are, and the mean error of the points with the largest errors.
Synthetic Data
We use two synthetic datasets, which § 5.7 discusses. Table 18 gives the results after 5 epochs, over 10 seeds; errors are measured on the training points.
Far groups. 100 Gaussian blobs of 2,000 points in dimensions and 5 far groups of points each, centred at distance 20 from the origin in random directions, with . A far group counts as kept if a centre ends within distance 5 (a quarter of 20) of the group’s centre.
Heterogeneous scales. 90 tight blobs (standard deviation 0.1) and 10 broad blobs (standard deviation 3), with , in and dimensions.
Data and Protocol Details
KDD Cup 1999. The full kddcup.data file (4,898,431 records). The three categorical features (protocol, service and flag) are one-hot encoded, which gives 122 dimensions. Removing exact duplicates leaves 1,074,974 points.
US Census 1990. 68 coded attributes (the record identifier caseid is dropped); 2,458,285 records, of which 1,998,492 are unique.
YearPredictionMSD. 90 timbre features (the target year is dropped); 515,345 records, of which 515,129 are unique.
GeoNames. Latitude and longitude from the allCountries file (13,199,186 unique coordinate pairs). We draw a random subsample of 1,020,000 points.
Covertype. The 54 attributes from scikit-learn’s fetch_covtype: 581,012 records, with no duplicates.
Household power. The 7 numeric columns of the UCI file (date and time are dropped). Rows with missing values are dropped, which leaves 2,049,280 records, of which 1,906,698 are unique.
Statlog Shuttle. The training and test files combined, with the class column dropped: 9 numeric attributes and 58,000 records, all unique.
Splits and scaling. After duplicates are removed, 20,000 points are held out (random permutation with seed 1234), and the test set is one half of them (seed 1234). Scaling uses statistics of the training points only.
Embedding datasets. DEEP 1M uses the e-means paper’s split, verified against the SHA-256 checksums distributed with the library’s e-means benchmarks. SIFT 1M uses the first BIGANN base vectors for training, and its test set is half of the next .
Software and hardware. FAISS 1.16.0 (faiss-cpu from PyPI), NumPy 2.5.4 and scikit-learn 1.9.1. Two AMD Threadripper servers (3990X and 7980X), each running 8 runs at a time with 4 threads per run.
Timing machine. The running times of § 5.6 were measured on the 3990X server: an AMD Ryzen Threadripper 3990X processor (64 cores, 128 hardware threads, 256 MiB of L3 cache), 188 GiB of memory, Ubuntu 24.04.5 LTS with Linux kernel 7.0, Python 3.12.16, NumPy 2.5.4 with OpenBLAS 0.3.34, and FAISS 1.16.0 (faiss-cpu from PyPI). Each timed run used 16 threads at reduced scheduling priority (nice 10). The server is shared with other users, whose jobs we did not control; rotating the order of the three methods across repetitions spreads the effect of their load over the three methods.
e-means settings. The library’s defaults: the scaling laws, batch_law="auto" (the smaller batch size for ) and the last-epoch mean. Every method uses the same settings; only the revival rule differs.
References
- [1]David Arthur and Sergei Vassilvitskii. k-means++: The advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1027–1035, 2007.DOI
- [2]Artem Babenko and Victor Lempitsky. Efficient indexing of billion-scale datasets of deep descriptors. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2055–2063, 2016.
- [3]Geoffrey H. Ball and David J. Hall. ISODATA, a novel method of data analysis and pattern classification. Technical Report AD 699616, Stanford Research Institute, Menlo Park, CA, 1965.
- [4]Thierry Bertin-Mahieux, Daniel P. W. Ellis, Brian Whitman, and Paul Lamere. The million song dataset. In Proceedings of the 12th International Society for Music Information Retrieval Conference (ISMIR), 2011.
- [5]Swann Bessa. E-means: quality batch at d ≤ 16 and no revival at d ≤ 2 by default. FAISS pull request #5854, commit 741138a, 2026. URL https://github.com/facebookresearch/faiss/pull/5854. Landed 2026-11-09; released in FAISS v1.16.0.
- [6]Swann Bessa, Pierre-Emmanuel Mazaré, Gergely Szilvasy, Hugo Touvron, David Picard, Matthijs Douze, and Hervé Jégou. e-means: outperforming k-means (in one-tenth the epochs), 2026. URL https://arxiv.org/abs/2611.09501.
- [7]Jock A. Blackard and Denis J. Dean. Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables. Computers and Electronics in Agriculture, 24(3):131–151, 1999.DOI
- [8]Sanjay Chawla and Aristides Gionis. k-means-: A unified approach to clustering and outlier detection. In Proceedings of the 2013 SIAM International Conference on Data Mining, pages 189–197, 2013. doi: 10.1137/1.9781611972832.21.DOI
- [9]Prafulla Dhariwal, Heewoo Jun, Christine Payne, Jong Wook Kim, Alec Radford, and Ilya Sutskever. Jukebox: A generative model for music, 2020.arxiv.org/abs/2005.00341
- [10]Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. The Faiss library, 2024.
- [11]William H. Equitz. A new vector quantization clustering algorithm. IEEE Transactions on Acoustics, Speech, and Signal Processing, 37(10):1568–1575, 1989. doi: 10.1109/29.35395.DOI
- [12]Pasi Fränti and Olli Virmajoki. Iterative shrinking method for clustering problems. Pattern Recognition, 39(5):761–775, 2006. doi: 10.1016/j.patcog.2005.09.012.DOI
- [13]Bernd Fritzke. A growing neural gas network learns topologies. In Advances in Neural Information Processing Systems 7, pages 625–632, 1995.
- [14]Bernd Fritzke. A self-organizing network that can follow non-stationary distributions. In Artificial Neural Networks – ICANN’97, volume 1327 of Lecture Notes in Computer Science, pages 613–618. Springer, 1997. doi: 10.1007/BFb0020222.DOI
- [15]Bernd Fritzke. The LBG-U method for vector quantization – an improvement over LBG inspired from neural networks. Neural Processing Letters, 5(1):35–45, 1997. doi: 10.1023/A:1009653226428.DOI
- [16]Bernd Fritzke. The k-means-u* algorithm: non-local jumps and greedy retries improve k-means++ clustering, 2017.arxiv.org/abs/1706.09059
- [17]Bernd Fritzke. Breathing k-means: Superior k-means solutions through dynamic k-values, 2020. Version 5, 2024.arxiv.org/abs/2006.15666
- [18]Kazuhisa Fujita. An efficient and straightforward online quantization method for a data stream through remove-birth updating, 2023.
- [19]GeoNames. GeoNames geographical database, allCountries dump. https://www.geonames.org, CC BY 4.0, 2026. Accessed 2026-11-11.
- [20]Georges Hebrail and Alice Berard. Individual household electric power consumption. UCI Machine Learning Repository, 2006.DOI
- [21]Sture Holm. A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 6(2):65–70, 1979.DOI
- [22]Minyoung Huh, Brian Cheung, Pulkit Agrawal, and Phillip Isola. Straightening out the straight-through estimator: Overcoming optimization challenges in vector quantized networks. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of PMLR, 2023.arxiv.org/abs/2305.08842
- [23]Hervé Jégou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg. Searching in one billion vectors: re-rank with source coding. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 861–864, 2011. doi: 10.1109/ICASSP.2011.5946540.DOI
- [24]Stuart P. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2):129–137, 1982. doi: 10.1109/TIT.1982.1056489.DOI
- [25]Ilya Loshchilov and Frank Hutter. SGDR: Stochastic gradient descent with warm restarts. In International Conference on Learning Representations (ICLR), 2017.arxiv.org/abs/1608.03983
- [26]Christopher Meek, Bo Thiesson, and David Heckerman. US census data (1990). UCI Machine Learning Repository, https://archive.ics.uci.edu/dataset/116/us+census+data+1990, 1990.
- [27]Fabian Pedregosa et al. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825–2830, 2011.arxiv.org/abs/1201.0490
- [28]scikit-learn developers. scikit-learn MiniBatchKMeans source, sklearn/cluster/_kmeans.py. https://github.com/scikit-learn/scikit-learn/blob/main/sklearn/cluster/_kmeans.py, 2026. Accessed 2026-11-11 (last change 2026-10-28; latest release 1.9.1).
- [29]D. Sculley. Web-scale k-means clustering. In Proceedings of the 19th International Conference on World Wide Web, pages 1177–1178, 2010. doi: 10.1145/1772690.1772862.DOI
- [30]Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Krishnaswamy, Gopal Srinivasa, Suhas Jayaram Subramanya, and Jingdong Wang. Results of the NeurIPS’21 challenge on billion-scale approximate nearest neighbor search. In Proceedings of the NeurIPS 2021 Competitions and Demonstrations Track, volume 176 of Proceedings of Machine Learning Research, pages 177–189, 2022.arxiv.org/abs/2205.03763
- [31]Statlog. Statlog (Shuttle). UCI Machine Learning Repository.DOI
- [32]Salvatore Stolfo, Wei Fan, Wenke Lee, Andreas Prodromidis, and Philip Chan. KDD cup 1999 data. UCI Machine Learning Repository, https://archive.ics.uci.edu/dataset/130/kdd+cup+1999+data, 1999.
- [33]Mahbod Tavallaee, Ebrahim Bagheri, Wei Lu, and Ali A. Ghorbani. A detailed analysis of the KDD CUP 99 data set. In IEEE Symposium on Computational Intelligence for Security and Defense Applications, pages 1–6, 2009. doi: 10.1109/CISDA.2009.5356528.DOI
- [34]Aaron van den Oord, Oriol Vinyals, and Koray Kavukcuoglu. Neural discrete representation learning. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, 2017.arxiv.org/abs/1711.00937
- [35]Phil Wang. vector-quantize-pytorch. https://github.com/lucidrains/vector-quantize-pytorch, 2026. Accessed 2026-11-11.
- [36]Joe H. Ward. Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, 58(301):236–244, 1963. doi: 10.1080/01621459.1963.10500845.DOI
- [37]Frank Wilcoxon. Individual comparisons by ranking methods. Biometrics Bulletin, 1(6):80–83, 1945. doi: 10.2307/3001968.DOI


