What algorithm is used to filter out from higher dimensional data points?

Question

I have 4-dimensional data points stored in my MySQL database in server. One time dimension data with three spatial GPS data (lat, lon, alt). GPS data are sampled by 1 minute timeframe for thousands of users and are being added to my server 24x7.

Sample REST/post json looks like,

{
   "id": "1005",
    "location": {
        "lat":-87.8788,
        "lon":37.909090,
        "alt":0.0,
    },
    "datetime": 11882784
}

Now, I need to filter out all the candidates (userID) whose positions were within k meters distance from a given userID for a given time period.

Sample REST/get query params for filtering looks like,

{
    "id": "1001",      // user for whose we need to filter out candidates IDs
    "maxDistance":3,   // max distance in meter to consider (euclidian distance from users location to candidates location)
    "maxDuration":14   // duration offset (in days) from current datetime to consider
}

As we see, thousands of entries are inserted in my database per minute which results huge number of total entries. Thus to iterate over for all the entries for filtering, I am afraid trivial naive approach won't be feasible for my current requirement. So, what algorithm should I implement in the server? I have tried to implement naive algorithm like,

params ($uid, $mDis, $mDay)

1.     Init $candidates = []
2.     For all the locations $Li of user with $uid
3.         For all locations $Di in database within $mDay
4.             $dif = EuclidianDis($Li, $Di)
5.             If $dif < $mDis
6.                 $candidates += userId for $Di
7.     Return $candidates

However, this approach is very slow in practice. And pre calculation might not be feasible as it costs huge space for all userIDs. What other algorithm can improve efficiency?

user_696391 · Answer

You could implement a spatial hashing algorithm to efficiently query your database for candidates within a given area/time.

Divide the 3D space into a 3D grid of cubes with width k, and when inserting a data-point into your database, compute which cube the point lies in and compute a hash value based on the cube co-ordinates.

When querying for all data-points within k of another datapoint d, compute the cube that d sits in, and find the 8 adjacent cubes (+/- 1 in each dimension). Compute the hash values of the 9 cubes and query your database for all entries with these hash values within the given time period. You will have small candidate set from which you can then iterate over to find all datapoints within k of d.

If your value of k can range between 2-5 meters, give your cubes a width of 5.

Timestamps can be stored as a separate field, or alternatively you can make your cubes 4-dimensional and include the timestamp in the hash, and search 27 cubes instead of 9.

What algorithm is used to filter out from higher dimensional data points?

1 Answers