DBSCAN clustering algorithm implemented in Apache Spark (MapReduce Framework) for geographical data.

Input: input_file.csv with format (id,lat,long), minPts, epsilon (in meters)

Output: output_file.csv with format (id,lat,long,cluster_id)

Note: This Algorithm use a KD-Tree for a fast computation of all neighbors under a given distance of a point (ball search).

DBSCAN (Density-based spatial clustering of applications with noise) is a clustering algorithm that clusters points according to a notion of density, i.e. points in a dense areas are grouped together.

The density metric is specified in terms of how many neighbors (minPts) a point must at least have at most distance epsilon in order to create a dense area that will form a cluster.

Based on this definition we can have tree different type of points:

• Core Points: points that have at least minPts that are at most epsilon far from it. They define a cluster.

• Density-reachable Point: points that don't have mintPts neighbors under epsilon, but they have a core-point as neighbor. They belong to the same cluster of the core-point.

• Noise: points that doesn't have neither MinPts points close up to distance epsilon nor a core point in its epsilon-neighborhood. This point are marked as noise since they are not in a sufficiently dense area.