查找GPS數據

Question

千萬用戶的GPS數據，結構等之間的關係：

userId 
startGps 
endGps 

一個用戶有兩個GPS，開始點和結束點。如果距離不同用戶的兩點距離大於1km。我們將在那裏定義用戶可能密切的關係。

userA startGpsA endGpsA 
userB startGpsB endGpsB 

function relation(userGpsA A, userGpsB B) 
    if(distance(A.startGps , B.startGps) > 1km || distance(A.startGps , B.endGps) > 1km || distance(A.endGps , B.endGps) > 1km) 
     return A,B 
    return null 

我怎麼能找到這些關係快？

Answer 1

一個可能的算法使用空間「桶」來減少計算時間。 它不會做特殊的線程技巧，但會減少大量的用戶比較（取決於存儲桶的大小）。

這個想法是把每個已經彼此距離不遠的用戶放在同一個「桶」中，並創建一個「桶」的索引，以便以較低的成本獲得相鄰的「桶」。

假設我們有

class User{ 
    long userId; 
    GPS start; 
    GPS stop; 
} 

class GPS{ 
    long x; 
    long y; 
} 

首先，我們創建了索引的用戶類：

class BucketEntity implements Comparable<BucketEntity>{ 
User origin; 
long x; 
long y 
} 
class Bucket extends Set<BucketEntity { 
} 

爲每一個用戶，我們將創建兩個BucketEntity，一個用於「開始」和一個「端」。我們將把BucketEntity存儲到一個特殊的索引數據結構中，以便輕鬆回溯最近的其他BucketEntity。

class Index extends ConcurrentHashMap<BucketEntity,Bucket> { 
     // Overload the 'put' implementation to correctly manage the Bucket (null initialy, etc...) 
} 

所有我們需要的是工具「哈希」（以及BucketEntity類「等於」方法。該規範對「散」和「等於」是是相同的，如果兩個BucketEntity如果他們不對於給定的BucketEntity，我們還希望能夠計算與另一個桶空間上相鄰的Bucket的「散列」函數。

要獲得'hash'和'equals的正確行爲'一個好的/快速的解決方案就是'精確度降低'，簡而言之，如果你有'x = 1248813'，你用'x = 124'（除以1000）代替它，就像改變你的GPS精度到gps-公里精度。

public static long scall = 1000; 
boolean equals(BucketEntity that) 
{ 
    if (this == that) return true; 
    if (this.x/scall == that.x/scall && 
     this.y/scall == that.y/scall) 
     return true; 
    return false; 
} 

// Maybe an 'int' is not enough to correctly hash your data 
// if so you have to create you own implementation of Map 
// with a special "long hashCode()" support. 
int hashCode() 
{ 
    // We put the 'x' bits in the high level, and the 'y' bits in the low level. 
    // So the 'x' and 'y' don't conflict. 
    // Take extra-care of the value of 'scall' relatively to your data and the max value of 'int'. scall == 10000 should be a maximum. 
    return (this.x/scall) * scall + (this.y/scall); 
} 

正如你在hashCode（）方法中看到的那樣，彼此靠近的Bucket真的接近hashCode（），如果我給你一個Bucket，你也可以計算出空間鄰接Bucket hashCode（）。

現在你可以得到與你的BucketEntity在同一個Bucket中的BucketEntity（ies）。要獲得相鄰的存儲桶，您需要創建9個虛擬BucketEntity，以將BucketEntity的Bucket包圍在get（）Bucket/null中。

List<BucketEntity> shortListToCheck = // A List not a Set ! 
    shortListToCheck.addindex.get(new BucketEntity(user, (x/scall)+1 , (y/scall)+1))); 
    shortListToCheck.addindex.get(new BucketEntity(user, (x/scall)+1 , (y/scall)))); 
    shortListToCheck.addindex.get(new BucketEntity(user, (x/scall)+1 , (y/scall)-1))); 
    shortListToCheck.addindex.get(new BucketEntity(user, (x/scall)+1 , (y/scall)+1))); 
    shortListToCheck.addindex.get(new BucketEntity(user, (x/scall) , (y/scall)))); 
    shortListToCheck.addindex.get(new BucketEntity(user, (x/scall)-1 , (y/scall)-1))); 
    shortListToCheck.addindex.get(new BucketEntity(user, (x/scall)-1 , (y/scall)+1))); 
    shortListToCheck.addindex.get(new BucketEntity(user, (x/scall)-1 , (y/scall)))); 
    shortListToCheck.addindex.get(new BucketEntity(user, (x/scall)-1 , (y/scall)-1))); 

的get（）匹配9虛擬BucketEntry所有的水桶（可以爲null）。 對於給定的9個桶中的每個用戶，真正按照您在問題中提供的方式計算距離。

然後玩'scall'。你可以看到，這裏的多線程沒有真正的約束。也許下一級算法優化是基於自適應縮放大小的自適應/遞歸桶大小。