java - Find relationship between gps data -

10 million user gps data, structure like:

userid startgps endgps 

one user has 2 gps, start point , end point. if distance of 2 points different user larger 1km. we'll defined there users potentially close relation.

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 

how find these relation fast?

one possible algorithm use spacial 'buckets' reduce computation time. not special threading tricks, reduce lot amount of user compare (depending of size of bucket).

the idea put in same 'buckets' every user not far each other, , create index on 'buckets' allow adjacent 'buckets' @ low cost.

let assume have

class user{     long userid;     gps start;     gps stop; } class gps{     long x;     long y; } 

first create class indexed user :

class bucketentity implements comparable<bucketentity>{  user origin;  long x;  long y } class bucket extends set<bucketentity { } 

for each user create 2 bucketentity, 1 'start' , 1 'end'. store thoses bucketentity specialy indexed data structure allow easy retrival of nearest other bucketentity.

class index extends concurrenthashmap{ // overload 'put' implementation correctly manage bucket (null initialy, etc...) }

all need implements 'hash' (and 'equals' method in bucketentity class. specification 'hash' , 'equals' same if 2 bucketentity if not far each other. want able compute 'hash' function of bucket spacialy adjacent bucket, given bucketentity.

to correct behavior 'hash' , 'equals' nice/fast solution 'precision reduction'. in short if have 'x = 1248813' replace 'x=124' (divide 1000) changing gps-meter precision gps-kilometer precision.

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 'int' not enouph correctly hash data // if have create own implementation of map // special "long hashcode()" support. int hashcode() {      // put 'x' bits in hight level, , 'y' bits in low level.      // 'x' , 'y' don't conflict.      // take extra-care of value of 'scall' relativly data , max value of 'int'. scall == 10000 should maximum.      return (this.x / scall) * scall + (this.y / scall); } 

as can see in hashcode() method, bucket close each other have near hashcode(), if give bucket, can compute spacialy adjacents bucket hashcode().

now can bucketentity(ies) in same bucket given bucketentity. adjacent bucket need create 9 virtual bucketentity 'get()' bucket/null around bucket of bucketentity.

   list<bucketentity> shortlisttocheck = // list not 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() buckets match 9 virtual bucketentry(can null). each of user of given 9 buckets, compute distance way provide in question.

then play 'scall'. has can see, there no real constraint on multi-threading here. maybe next level of algorithm optimization adaptative/recursive bucket-size based on adaptative scalling-size.