DBSCAN finds clusters by looking for regions where points are close together. Its key test is whether a point has enough nearby dataset points to anchor a cluster. Given a radius ε and a threshold minPoints, a point is a core point when at least minPoints points, including the point itself, lie within distance ε of it. With minPoints = 3, it needs at least two other points in that radius. section 12.3.1
Figure 12.9 Core points, directly reachable points, and reachable points, given a radius ϵ and a threshold minPoints (the minimum number of points in a core region) equal to 3; hence, core points need to have at least two neighbors within distance ϵ.
The diagram distinguishes core points from points that are merely reachable when minPoints is 3. section 12.3.1
That test determines how a cluster grows. Every point within ε of a core point is directly reachable from it and joins its cluster. If a newly reached point is also a core point, its neighbors can extend the cluster in turn. A reached point that is not a core point joins the cluster but does not extend it. Chains of core points can therefore connect dense regions; points unreachable from any core point are marked as noise. section 12.3.1 section 12.3.2
Figure 12.10 A few steps of the main loop of DBSCAN. When core points are processed (the first three steps in the figure) all their undiscovered neighbors are added to current cluster and to a set (not a queue) of points to be processed. Conversely, when the current point being processed is not a core point, like v in the last step, then no further action is taken.
The illustrated DBSCAN loop adds undiscovered neighbors when it processes a core point, but takes no further action for a non-core point. section 12.3.2
To implement the test, run a range query for each point to find all dataset points within its ε-radius neighborhood, then compare the count with minPoints. A k-d tree can speed up these queries. Checking every point against the entire dataset instead gives O(n²) running time; if each indexed range query takes O(log n), the stated comparison is O(n log n). Range queries can still take O(n) in the worst case, so that improvement is conditional. section 12.3.3
Partitioning the data introduces another constraint: a core point near a shard boundary may be misclassified if some of its neighbors sit in another shard. In MapReduce DBSCAN, extending each grid cell by ε preserves the border points needed for local neighborhood checks. When neighboring shards are combined, a shared margin point triggers a cluster merge only if it is a core point in at least one shard; a non-core point alone does not connect the clusters. section 13.4
