Algorithm Comparison

This guide helps you choose the right algorithm for your use case.

Quick Recommendation

from kmeans_seeding import rskmeans

# Default: Works great for most cases
centers = rskmeans(X, n_clusters=k, index_type='FastLSH')

Use this unless you have specific requirements (see decision tree below).

Decision Tree

Start
  │
  ├─ n < 10,000?
  │    └─ Yes → Use kmeanspp (simple, fast enough)
  │    └─ No  → Continue
  │
  ├─ Have FAISS installed?
  │    ├─ Yes → Use rskmeans with index_type='IVFFlat'
  │    └─ No  → Continue
  │
  ├─ d > 100 (high-dimensional)?
  │    ├─ Yes → Use multitree_lsh (optimized for high-d)
  │    └─ No  → Continue
  │
  ├─ k > 500 (many clusters)?
  │    ├─ Yes → Use multitree_lsh (scales well with k)
  │    └─ No  → Continue
  │
  └─ Default → Use rskmeans with index_type='FastLSH'

Detailed Comparison

Feature Matrix

Feature	kmeanspp	rskmeans	afkmc2	multitree_lsh	Winner
Speed (n=100K)	⭐	⭐⭐⭐⭐⭐	⭐⭐⭐⭐	⭐⭐⭐⭐	rskmeans
Quality	⭐⭐⭐⭐⭐	⭐⭐⭐⭐⭐	⭐⭐⭐⭐	⭐⭐⭐⭐	Tie: kmeanspp, rskmeans
Setup Difficulty	⭐⭐⭐⭐⭐	⭐⭐⭐	⭐⭐⭐⭐	⭐⭐⭐⭐⭐	kmeanspp
High-d (d>100)	⭐⭐	⭐⭐⭐⭐	⭐⭐⭐	⭐⭐⭐⭐⭐	multitree_lsh
Many k (k>500)	⭐	⭐⭐⭐⭐⭐	⭐⭐⭐	⭐⭐⭐⭐	rskmeans
Memory Usage	⭐⭐⭐⭐⭐	⭐⭐⭐	⭐⭐⭐⭐	⭐⭐⭐	kmeanspp
Determinism	⭐⭐⭐⭐⭐	⭐⭐⭐⭐⭐	⭐⭐⭐⭐	⭐⭐⭐⭐⭐	All good
Tuning Required	⭐⭐⭐⭐⭐	⭐⭐⭐	⭐⭐⭐⭐	⭐⭐⭐⭐	kmeanspp

Performance Benchmarks

Dataset: n=100,000, d=100, k=200

# Approximate timing on modern CPU
Algorithm           Time      Quality (k-means cost)
─────────────────────────────────────────────────────
kmeanspp            45.2s     1.234e6  (baseline)
rskmeans (FastLSH)   2.1s     1.238e6  (+0.3%)
rskmeans (IVFFlat)   1.8s     1.235e6  (+0.1%)
afkmc2               3.5s     1.245e6  (+0.9%)
multitree_lsh        2.8s     1.248e6  (+1.1%)

Speedup: All fast algorithms are 15-25× faster with <2% quality loss.

Use Case Recommendations

Text Clustering (TF-IDF, Word2Vec)

Characteristics: High-dimensional (d=300-10K), sparse, many documents

Recommended:

from kmeans_seeding import multitree_lsh

# Excellent for text
centers = multitree_lsh(X, n_clusters=k,
                       n_trees=6,
                       random_state=42)

Alternative:

from kmeans_seeding import rskmeans

# Also good, especially with FAISS
centers = rskmeans(X, n_clusters=k,
                  index_type='LSH',
                  random_state=42)

Image Clustering (Features/Embeddings)

Characteristics: Medium-high dimensional (d=512-2048), dense

Recommended:

from kmeans_seeding import rskmeans

centers = rskmeans(X, n_clusters=k,
                  index_type='IVFFlat',  # Best for dense data
                  max_iter=50,
                  random_state=42)

Customer Segmentation

Characteristics: Low-medium dimensional (d=10-50), moderate size

Recommended:

from kmeans_seeding import afkmc2

# Simple and effective
centers = afkmc2(X, n_clusters=k,
                chain_length=200,
                random_state=42)

Alternative (if very large):

from kmeans_seeding import rskmeans

centers = rskmeans(X, n_clusters=k,
                  index_type='FastLSH',
                  random_state=42)

Time Series / Sensor Data

Characteristics: Medium dimensional (d=20-100), sequential patterns

Recommended:

from kmeans_seeding import rskmeans

# Good balance for time series
centers = rskmeans(X, n_clusters=k,
                  index_type='FastLSH',
                  max_iter=50,
                  random_state=42)

Biological / Genomic Data

Characteristics: Very high-dimensional (d > 1000), specialized

Recommended:

from kmeans_seeding import multitree_lsh

# Scales to very high dimensions
centers = multitree_lsh(X, n_clusters=k,
                       n_trees=8,
                       random_state=42)

Small Datasets (n < 10K)

Recommended:

from kmeans_seeding import kmeanspp

# Fast enough, no approximation needed
centers = kmeanspp(X, n_clusters=k, random_state=42)

Quality vs Speed Tradeoff

Fastest (Slight Quality Loss)

# ~1% quality loss, maximum speed
from kmeans_seeding import rskmeans

centers = rskmeans(X, n_clusters=k,
                  index_type='HNSW',  # Fastest index
                  max_iter=20,         # Few iterations
                  random_state=42)

Balanced (Recommended)

# <0.5% quality loss, very fast
from kmeans_seeding import rskmeans

centers = rskmeans(X, n_clusters=k,
                  index_type='FastLSH',  # Fast, no FAISS needed
                  max_iter=50,            # Good quality
                  random_state=42)

Best Quality (Slower)

# Near-perfect quality, still 10× faster than k-means++
from kmeans_seeding import rskmeans

centers = rskmeans(X, n_clusters=k,
                  index_type='Flat',  # Exact search
                  max_iter=100,       # Many iterations
                  random_state=42)

Exact (Slowest)

# Perfect quality, no approximation
from kmeans_seeding import kmeanspp

centers = kmeanspp(X, n_clusters=k, random_state=42)

Common Patterns

Pattern 1: Try Fast First

from kmeans_seeding import rskmeans
from sklearn.cluster import KMeans

# Try fast initialization
centers = rskmeans(X, n_clusters=k,
                  index_type='FastLSH',
                  random_state=42)

kmeans = KMeans(n_clusters=k, init=centers, n_init=1)
labels = kmeans.fit_predict(X)

# If quality insufficient, upgrade to better index
centers = rskmeans(X, n_clusters=k,
                  index_type='IVFFlat',  # Better quality
                  max_iter=100,
                  random_state=42)

Pattern 2: Multiple Runs

from kmeans_seeding import rskmeans
from sklearn.cluster import KMeans

best_inertia = float('inf')
best_model = None

for seed in range(10):
    centers = rskmeans(X, n_clusters=k,
                      index_type='FastLSH',
                      random_state=seed)

    kmeans = KMeans(n_clusters=k, init=centers, n_init=1)
    kmeans.fit(X)

    if kmeans.inertia_ < best_inertia:
        best_inertia = kmeans.inertia_
        best_model = kmeans

labels = best_model.labels_

Pattern 3: Progressive Refinement

from kmeans_seeding import multitree_lsh, rskmeans
from sklearn.cluster import KMeans

# Stage 1: Quick initialization
centers = multitree_lsh(X, n_clusters=k,
                       n_trees=2,
                       random_state=42)

# Stage 2: Refine with k-means
kmeans = KMeans(n_clusters=k, init=centers, max_iter=10)
kmeans.fit(X)

# Stage 3: Final refinement with better init
centers = rskmeans(X, n_clusters=k,
                  index_type='IVFFlat',
                  random_state=42)

kmeans = KMeans(n_clusters=k, init=centers, n_init=1)
labels = kmeans.fit_predict(X)

FAQ

Q: Which algorithm is fastest?

A: rskmeans with index_type='HNSW' is typically fastest, but FastLSH is excellent without needing FAISS.

Q: Which algorithm has best quality?

A: kmeanspp (exact) and rskmeans with index_type='Flat' produce near-identical quality.

Q: What if I don’t have FAISS?

A: Use rskmeans with index_type='FastLSH' or multitree_lsh - both work without FAISS.

Q: For very large datasets (n > 1M)?

A: Use rskmeans with index_type='IVFFlat' and consider sampling for initialization.

Q: For very high dimensions (d > 1000)?

A: Use multitree_lsh with n_trees=8 - it’s specifically optimized for high-d.

Q: Does the algorithm choice really matter?

A: For small data (n < 10K): No, use kmeanspp

For large data: Yes! 10-100× speedup with minimal quality loss.

Summary Table

Your Situation	Recommended Algorithm	Configuration
Default / Unsure	rskmeans	index_type='FastLSH'
Small data (n<10K)	kmeanspp	(no params)
Text / Sparse	multitree_lsh	n_trees=6
Images / Dense	rskmeans	index_type='IVFFlat'
Many clusters (k>500)	rskmeans	index_type='IVFFlat'
High-d (d>100)	multitree_lsh	n_trees=6-8
No FAISS	rskmeans	index_type='FastLSH'
Maximum speed	rskmeans	index_type='HNSW', max_iter=20
Best quality	rskmeans	index_type='Flat', max_iter=100

See Also

• RS-k-means++: Rejection Sampling - Detailed RS-k-means++ documentation

• AFK-MC²: Adaptive Fast k-MC² - Detailed AFK-MC² documentation

• Fast-LSH k-means++ - Detailed Fast-LSH documentation

• Standard k-means++ - Detailed k-means++ documentation