java - 查找GPS数据之间的关系

1000万用户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

我怎么能很快找到他们的关系？

最佳答案

一种可能的算法使用空间“桶”来减少计算时间。
它不会做一个特殊的线程技巧，但会减少很多用户的数量进行比较（取决于bucket的大小）。
我们的想法是，将每个距离彼此不远的用户放在同一个“bucket”中，并在“bucket”上创建一个索引，允许以低成本获取相邻的“bucket”。
假设我们有

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 {
}

对于每个用户，我们将创建两个bucketenity，一个用于“start”，一个用于“end”。我们将把这些buckententity存储到一个特殊的索引数据结构中，这样可以方便地检索最近的其他buckententity。

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

我们只需要在BucketEntity类中实现hash（和equals）方法。“hash”和“equals”的规范在两个buckententity中是相同的，如果它们彼此距离不远的话。我们还希望能够计算一个给定buckententity的Bucket的hash函数，该函数与另一个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在同一个桶中的BucketEntity要获取相邻的bucket，您需要创建9个虚拟buckententity to‘get（）’bucket/null，它位于buckententity的bucket周围。

   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虚拟buckettentry匹配的所有bucket（可以为空）。
对于给定9个bucket的每个用户，按照您在问题中提供的方式计算距离。
然后玩“scall”。你看，这里没有多线程的真正限制。下一步的算法优化可能是基于自适应尺度的自适应/递归桶大小。

关于java - 查找GPS数据之间的关系，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43275484/