Я забыл ответить на свой вопрос. Я наконец-то реализовал версию алгоритма DBSCAN MapReduce. Вы можете найти этоhere (Hadoop).

Это псевдокод того, как это работает:

function map(P, eps, MinPts)
    if P is unvisited then
        mark P as visited
        NeighborPts = regionQuery(P, eps)
        if sizeof(NeighborPts) < MinPts then
            do nothing
        else
            mark P as clusterized
            prepare the key
            create new cluster C
            C.neighborPoints = NeighborPts
            C.points = P
            emit(key, C)

function reduce(key, clusters, eps, MinPts)
    finalC is the final cluster
    for all C in clusters do
        finalC.points = finalC.points ∪ C.points
        for all P in C.neighborPoints do
            if P′ is not visited then
                mark P′ as visited
                NeighborPts′ = regionQuery(P′,eps)
                if sizeof(NeighborPts′) ≥ MinPts then
                    NeighborPts = NeighborPts ∪ NeighborPts′
                end if
            end if
            if P′ is not yet member of any cluster then
                add P′ to cluster C
            end if

Google для "параллельного DBSCAN", и вы найдете ряд статей, обсуждающих, как распараллелить этот алгоритм. Обычно это немного меняет алгоритм, например, для этого потребуется объединение кластеров.

Предварительная кластеризация Canopy также может быть хорошим шагом предварительной обработки для DBSCAN.