A nearest-neighbor search may become too slow as its dataset grows, even when the search algorithm itself is efficient. A dataset split, or sharding, divides the data into pieces that can be searched or processed separately. The choice of split depends on both the time available and the result the application needs. section 11.3.1
Choose a split that fits the operation:
- For nearest-neighbor search, geographical sharding may fit the application. If it does not, randomly shard the data, search shards in parallel with an approximate algorithm, and choose the best solution returned. Faster answers can come at the cost of accuracy. section 11.3.1
- For DBSCAN, do not simply assign each point to one arbitrary shard. A point’s ε-neighborhood may span shards, causing a core point to go unrecognized and changing the clustering result. section 13.4
A spatial split makes distributed DBSCAN possible while preserving the local context it needs. Divide the domain into cells, then extend each cell by ε in every direction. Each shard contains its cell’s points plus points in that border margin; points near a boundary can therefore have their ε-neighborhood available during local clustering. This deliberately duplicates margin points rather than treating shard boundaries as barriers. section 13.4
The MapReduce workflow is:
- Create the extended grid shards and record adjacent shards and margin points. section 13.4
- Run DBSCAN on each shard with a mapper. section 13.4
- Use reducers for adjacent shard pairs to reconcile margin points: clear an inconsistent noise designation when a point is core in either shard, or merge the clusters identified across shards. Combine the results afterward. 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 cells show why a split for DBSCAN needs overlap: without the ε-wide margin, boundary points can lose neighbors. section 13.4
Sharding is not the same as partitioning clustering. A shard is a division used to carry out computation; flat clustering produces non-overlapping groups as its output. Extended DBSCAN shards can overlap even though the clustering results must later be reconciled. More overlap adds margin-point work, while an unextended split risks incorrect local results. The supplied workflow gives no general running-time bound; its benefit depends on how much work stays within shards relative to their borders. section 12.1.2 section 13.4
