Big Data Processing & Distributed Clustering

Apache SparkDatabricks

The problem

DBSCAN finds arbitrarily shaped clusters and handles noise well, but its naive form has quadratic time complexity, making it unusable directly on 23 million GPS points. The real question was not whether Spark could distribute the workload, it was how to split millions of spatial points into partitions small enough to cluster without either destroying the spatial structure DBSCAN depends on or silently hiding the load-balancing problems that make distributed systems fail in practice.

My approach

  • Diagnostic choice: outliers detected by the IQR method were capped and flagged rather than removed outright, specifically to test whether a partitioning strategy would naturally isolate them into sparser regions on its own, a more informative question than simply cleaning them out before any analysis.
  • Trade-off, two partitioning strategies compared head to head. Grid partitioning assigned points to fixed-size cells in about 6 seconds, but split the data into 85,069 grids of which only 1,592 held enough points to cluster meaningfully, most cells were unusably sparse. KD-Tree partitioning took roughly 5 minutes, since a Decision Tree Classifier had to be trained just to assign all 23 million points to their correct partition, but it produced far more balanced partitions and noticeably better local cluster cohesion.
  • A real dead end, caught and explained: batching large partitions by sorting on altitude and slicing into chunks produced a silhouette score of roughly -0.9, a strongly wrong clustering. The cause was diagnosed rather than just discarded, DBSCAN was treating each batch as its own isolated dataset instead of samples drawn from one continuous space, fracturing what should have been single clusters across batch boundaries.
  • Fix: switching to KMeans-based batching, grouping each large partition into spatially coherent sub-batches before running DBSCAN, corrected this. Batching was still necessary given memory constraints, but batching by spatial coherence rather than by an arbitrary sort order preserved the structure DBSCAN needed to see.
  • Hyperparameter strategy scaled to the problem size: small-sample experiments used a visual elbow method to pick eps and min_samples by eye, but that does not scale to hundreds of batches. For the full run, eps was instead set from the 90th percentile of k-nearest-neighbor distances per batch, and min_samples scaled logarithmically with batch size, a heuristic that adapts automatically instead of requiring a human to look at a plot for every batch.
  • Honest limitation surfaced directly: KD-Tree's balanced partitions mix outliers in with dense regions by construction, since it does not segregate sparse areas the way Grid does. That meant DBSCAN itself had to identify noise within mixed partitions rather than starting from pre-isolated outliers, a real limitation of the approach rather than something worked around silently.

Results

  • KD-Tree partitioning achieved a global silhouette score of -0.2658 versus -0.2884 for Grid, and a dramatically better local silhouette score of -0.3235 versus -0.7147, confirming that balanced partitions preserved cluster structure noticeably better at the local level.
  • Grid partitioning was faster and isolated more true outliers before clustering even began, roughly 2.5 million points flagged as noise versus 3.5 million under KD-Tree, a genuine speed-versus-structure trade-off rather than one method being strictly better.
  • Correcting the batching strategy from altitude-sorted to KMeans-based fixed a silhouette score of approximately -0.9 into a workable clustering result.

What I would do differently

The altitude-based batching approach was a reasonable first attempt, but the failure mode, DBSCAN losing its sense of a single continuous dataset once split into arbitrarily ordered chunks, was foreseeable in hindsight. Next time, I would batch by spatial coherence from the very first attempt rather than by convenience of sort order, and reserve the naive approach for a quick sanity check rather than a real experimental run, since a wrong silhouette score on a 23M-row run is an expensive way to learn that lesson.