A margin region is the boundary area retained around a shard so distributed DBSCAN can detect clusters crossing adjacent shard borders. A shard includes its cell plus points within distance ϵ of every border, producing an expanded region whose sides extend by 2ϵ. section 13.4
Margin points support cross-shard reconciliation:
- Track core points within distance ϵ of a cell border, or within 2ϵ of a shard border. section 13.4
Four-cell MapReduce DBSCAN
Each extended cell receives a mapper, while each adjacent-cell pair receives a reducer. Reducers inspect shared margin points and merge clusters when either side identifies a core point; excessive ϵ can make the margin unrealistically large.
