6

以下は仮説です。ブール値の結果を生成する文字列類似関数 ( string_sim) と、2 つの緯度/経度座標間の距離がしきい値を下回っているかどうかを判断する別の関数 ( geo_dist)があるとします。

あいまい結合を使用して、これらの条件でマージすることにしました。

merge(LHS, RHS, by=string_sim(LHS$string, RHS$string) & geo_dist(LHS$lat, LHS$lon, RHS$lat,RHS$lon))

内部では、data.table はデカルト積を比較する必要があります...すべての行を他のすべての行と非対称に比較します。これは、中規模のデータセットでは数兆に上る巨大な数になる可能性があります。したがって、比較関数にデータを送信する際には、整数制限を回避するために、それぞれに与えられた 20 億セル未満の複数のプロセスを利用して、分割統治戦略を使用する必要がある場合もあります。基本的に、ベクトルのセクションを断片にマップしてから関数に送信する必要があります (これは map-reduce のように聞こえ始めています)。

ユーザーが賢く、結合コマンドを繰り返し適用することで時間を節約したいとします。最初は、等値条件など、実行するのに最もコストがかからないものから始めます。

merge(LHS, RHS, by=list(LHS$first_initial == RHS$first_initial, string_sim(LHS$string, RHS$string) & geo_dist(LHS$lat, LHS$lon, RHS$lat,RHS$lon)))

このような機能が欲しいです。少し時間がかかりましたが、data.table を使用してこれを行うコードをいくつかハックしました。パッケージには、将来このようなものが付属する可能性があります。

編集:これをよりdata.tableネイティブな方法で表現させてください。最初に変数を定義して等値に一致させます。

setkey(LHS, first_initial)
setkey(RHS, first_initial)

次に、ベクター スキャンに続いてバイナリ マージを実行します。

LHS[RHS][string_sim(string, string.1) & geo_dist(lat, lon, lat.1,lon.1)]

または、最もコストのかかる操作を最初に実行することもできます。以下の方が早いと思います。

LHS[RHS][geo_dist(lat, lon, lat.1,lon.1)][string_sim(string, string.1)]

ただし、LHS が 2,000 万行、RHS が 2,000 万行の場合、システムが過負荷になる可能性があります。これを防ぐには、分割統治法を使用して LHS と RHS を分割する必要がありました。バックエンドでプロセスを並列化するためのより効率的な方法があれば、そのすべてを行う必要はないと思います。

コードは次のとおりです。

joiner <- function(x,y, reduce=quote( x[map$x][y[map$y],nomatch=0] ), chunks = 100000, mc.cores = getOption("cores")){
    require("multicore")
    require("data.table")
    map_function <- function(x_N,y_N, chunks){  
        x_partitions = ceiling(x_N/chunks)
        x_parts = (0:x_partitions)*chunks 
        x_parts[length(x_parts)]=x_N            
        y_partitions = ceiling(y_N/chunks)
        y_parts = (0:y_partitions)*chunks 
        y_parts[length(y_parts)]=y_N            
        MAP = vector("list",x_partitions*y_partitions )
        index = 0
        for(i in 1:x_partitions){
            for(j in 1:y_partitions){
                index = index +1
                MAP[[index]] = list(
                        x = (x_parts[i]+1):x_parts[i+1],
                        y = (y_parts[j]+1):y_parts[j+1]
                )
            }
        }
        return(MAP) 
    }

    if(missing(y)){
        y=x
    } 

    reducer_function <- function(map, reduce, x,y){
            eval(reduce)
    }

    collector = mclapply(map_function(nrow(x),nrow(y),chunks=chunks),reducer_function,reduce, x,y, mc.cores=mc.cores)   
    collector = rbindlist(collector)
    return(collector)   
}
D = data.table(value=letters, row_id = sample(1:100,26)); D= rbind(D,D); setkey(D,value)
joiner(D); joiner(D,chunks=10); D[D] # they are all the same, except the key is gone
4

0 に答える 0