Predict crowded areas based on time series data points of latitude and longitude

Question

I have time series location data (latitude/longitude) from users who send their location every minute. Basically the history of different users moving on a map.

+---------+-------------------------+---------------------+  
| user_id |     point(lat,lon)      |        date         |  
+---------+-------------------------+---------------------+  
|     111 | 26.453121,44.297412     | 2020-07-24 13:17:00 |  
|     222 | 26.453155,44.297489     | 2020-07-24 13:17:00 |  
|     111 | 26.453132,44.297455     | 2020-07-24 13:18:00 |  
|     222 | 26.453191,44.297468     | 2020-07-24 13:18:00 |
|     ... |                         |                     |
+---------+-------------------------+---------------------+

Based on this location data I need to predict how many users will be in a certain location.

For example given the point (lat=26.453121,lon=44.297412) (which in the image below is the center of the green circle) and a radius of 30 meters predict how many points (users) will be inside the perimeter based on past data. In the image below I have 3 points (users) inside.

The challenging part is that the center of the area (circle) and the radius are variable parameters and can get any value.

My questions:
Is it feasible to have the center of the circle and the radius as variable parameters? If not then how would someone approach a problem like this?

I am considering making the radius a fixed value but the fact that the center of the circle can be any point on a map is still giving me headaches.

Answer 1

This is a very interesting problem. I would propose the following approach:

• Build a regression model that predicts the lat/long coordinates of a user given a history of lat/long coordinates e.g., a Kalman filter.
• Once you have your regression built, write a function that takes a lat/long coordinate and a radius, and checks if any users are predicted to be within the circle defined by the provided coordinates and radius given the users last location.

I think an "even-better-if" solution would be to fit a model that can simulate "random walks" for users based upon their past behavior. This would allow you to explore questions around how likely it is for users to be in certain locations at certain times.

Answer 2

If the radius would vary it would lead to too many problems:

• There's an infinite number of solutions, your algorithm needs to consider a radius as small as 1 centimeter and as big as the whole earth.
• There's also an infinite number of positions where you could center the circles (”+1 cm right”).
• Let's take a 1-centimeter radius, it could be either empty or maximally crowded, but such a result doesn't make much sense.
• The whole earth radius would always have the same density of people. Again, not useful.

So this leads to problems with defining what “crowded” means and makes the search space unnecessary big.

I'd split the map to a fixed grid of equally sized squares and calculate it per each square. For intermediate squares, you can always interpolate. It also makes defining “crowdy” easier as in the number of people per area you have at least the area fixed.

Computationally, this makes the search space smaller as the grid has a finite size and doesn't consider many intermediate positions. It would also be sparse, so this can be potentially used for some improvements in terms of algorithms and data structures, to improve computation time and space to be used.

It also reveals trivial solution, as you can just COUNT people and GROUP grid. The solution can be easily expanded by grouping by hours, days of the week, months, etc to consider seasonality. Of course, there are many non-trivial solutions as well, but the trivial ones offer a good, cheap start.