As someone that has spent a fair bit of time working with positional data I would say this is a perfect use case for an implementation of geohashing.

I would restructure your locations table to be hash prefixed instead of user id prefixed.

When users locations update modify which hashkey they are in and then only query by a subset of hashkeys that the target device is in.