Suppose a clustering job splits nearby points across two machines. A point near the split may appear isolated on each machine, even though it has enough neighbors in the full dataset to belong to a dense region. The missing information is its local neighborhood. section 13.4
The ε-neighborhood of a point consists of points within distance ε of it. In DBSCAN, ε sets the radius of a dense region. A point is a core point when its ε-neighborhood contains at least minPoints points; the stated counting convention includes the point itself. section 12.4.1
This definition makes an ordinary partition unsafe: splitting the data can scatter a point’s neighbors across shards and cause a core point to be missed. Counting neighbors in a distributed job is possible, but DBSCAN also explores relationships between points and their neighbors. section 13.4
For grid-based MapReduce DBSCAN, preserve neighborhoods at shard boundaries:
- Divide the domain into cells, then extend each cell by ε in every direction to form an overlapping shard. section 13.4
- Run DBSCAN on each extended shard, then reconcile clusters and noise classifications using points in the margins of adjacent shards. section 13.4
Figure 13.12 Sharding data for MapReduce DBSCAN (MR-DBSCAN). After dividing the domain into equally sized cells, for each shard we need to include all points in one cell, plus all the points within a distance equal to ϵ from its borders. In practice, instead of the cells, we take a rectangle obtained by stretching the cell further in all directions, and each of the sides will measure like the corresponding cell’s side plus 2ϵ. This way, core points close to the cells’ borders will have their ϵ-neighborhood contained in either shard.
The extended-cell diagram shows why ε-wide margins keep the neighbors of a point near a cell border available to a shard. section 13.4
The same neighborhood also gives core distance a precise meaning: for a core point, it is the distance to the neighbor that meets the minPoints threshold. With minPoints fixed, this is the smallest ε that makes the point a core point; for a non-core point at the chosen ε, core distance is undefined. section 12.4.1
Overlap trades duplicated boundary points and a merging step for safer local clustering. The benefit depends on how many points lie in the margins: a small grid with a large ε can have an unusually high margin fraction. section 13.4
