A simple solution to Geoquery oplog

Please let me know if there are better solutions. I am in need of a good solution, this is what I will use for the time being.


Your problem: Livequery documents within radius R of a lat-lng coordinate pair.

Meteor’s Problem: Live Geoqueries like $near, $within, etc. are not oplog-enabled and are not suitable for high traffic applications.

Simple Solution: If you want to find documents near a certain point, you don’t need to use geoqueries. One way around this is to store the lat-lng point in your document like this:

var yourDocument = {
  name: "John Doe",
  occupation: "Actor",
  lat: 39.564,
  lng: 134.342
};

Suppose we want to find a document near {lat: 38.456, lng: 133.332}.

A simple way to do it:

var point = {lat: 38.456, lng: 133.332};
var dist = 5; //miles
var dLat = milesToLat(dist);
var dLng = milesToLng(dist);
//returns document above
People.findOne({
  lat: {
    $lte: point.lat + dLat, 
    $gte: point.lat - dLat
  },
  lng: {
    $lte: point.lng + dLng, 
    $gte: point.lng - dLng
  }
}) 

The above code will find documents within an approximately square region around the point, which may be good enough for many purposes. The main advantage is that Meteor can handle this query with the oplog (I think…). Another subtle advantage is in observer reuse:

var myLocation = {lat: 39.5561, lng: 145.6764}
var yourLocation = {lat: 39.5562, lng: 145.6766}
/*
  Theory: Note how our locations are very close. Querying once 
  for each precise location will not allow us to take advantage of 
  observer reuse. If we approximate the locations as the same 
  location, then we can take advantage of Meteor's observer reuse.
  Querying around a roundedLocation will likely show us the 
  same documents that would have been shown to us if we had 
  instead both queried around our exact Locations.
*/
var roundedLocation = {lat: 39.56, lng: 145.68};

Again, the disadvantage is losing accuracy in favor of performance.
Rounding a coordinate pair to four significant figures still gives us a delta of less than a mile for most locations.

For example, if I want to find nearby car repair shops, I don’t care if I accidentally get some results which are a half mile further than a more precise solution would have given me.

By combining a $lte, $gte approach with value rounding, we can get pretty decent geoqueries!


Please let me know if there are better solutions. I am in need of a good solution, this is what I will use for the time being.

5 Likes

This is a great optimization! As with all optimizations, it may not cater to all cases, but it does not make it any less clever!

1 Like

That is pretty clever!

What are the functions for milesToLat and milesToLng, if you don’t mind me asking.

1 Like

Given any latLng coordinate pair, we can vary it a little by delta, and
figure out how many miles there are per dLat and per dLng. This is just
from the earth’s geometry. R is earth’s radius in miles.

dMile = radians(dLat)*R
dMile = cos(radians(lat))*radians(dLng)*R

But, we are interested in the inverse function.

Note that the degrees function is the inverse of the radians function.

So, inverting both equations gives us:

dLat = degrees(dMile/R)
dLng = degrees(dMile/R*cos(radians(lat)))

dLng is undefined at the poles if dMile is anything but zero, meaning that
the distance between longitude lines at the poles is zero.

For all other coordinates (where lat != 90 or -90), dMile can be set to 1
since we’re interested in the conversion rate between miles and lat/lng.

So we get:

dLat = degrees(1/R)
dLng = degrees(1/R_effective), where R_effective = R*cos(radians(lat))

I’m on my phone so I won’t write the code, but those two equations are
basically it. Let me know if there’s any math errors. Basically, the nuance
here is that the distance between longitude lines is a function of
latitude, meaning it will change depending on where you are on earth.
Distance between latitude lines doesn’t change because of how latitude is
defined. If you check out the globe and look at the lines, you notice that
longitude lines converge at the poles (hence, have zero distance from each
other there, and increasing distance as we go towards the equator), and
latitude lines stay equidistant from each other.

1 Like

For anyone who wants a visual understanding of what this can do for you:

The following image shows


Each blip is a user. All users in the same-color areas are approx. as being at the same location. I did not use the equations above to dynamically calculate the bin size. Then, we can show the exact same results for each of those users – fully reactive, no polling, since we query the results using $lte and $gte. As a user reactively moves from bin to bin, we send them an entirely new data set.

Number of users in that big circle: 10000. Number of queries: 384. Queries run per user per hour: 1 or peanuts.

Without this:

Number of users in that big circle: 10000 Number of queries: 10000, Queries run per user per hour: hundreds, if no throttling… since Geolocation.latLng() spams itself.

Showing users local restaurants within a mile makes no sense if you use a bin size of 2 miles. Since, then you’ll approx. their location farther than the results shown would be! That is why it’s only useful to do this binning if your need for location precision is low.

But hey – even if you bin within 20 meters, it would be amazing. Imagine trying to run an ENTIRELY NEW QUERY for every step that someone takes… what a waste of resources.

Binning like this is optional only if you wanna reuse observers?..

PROBLEM:

Welcome to Northern Greenland, where the majority of our users are coming from:

This is why we need to use the equations mentioned above… we need to account for the fact that longitude lines converge at the north pole, meaning the distance between them goes to zero.

If the bins are approximately square, then the solution is a good approximation to querying in a circle of radius R. Thankfully, the regions are mostly square between the socially important latitude regions [-60,60]. It just so happens that the cosine function doesn’t vary appreciably over [-60,60]. That means, we don’t need to use the equations in my previous post.

just kidding about northern greenland. if you operate in N greenland, don’t use this binning thing, jut throttle your queries by requiring that distance(newCoords,oldCoords) > someDistance

still, every user will have a new query run for each of them. binning helps us fix that.

this is all my notes, please add.

2 Likes

Hello friend, is it to solve with your idea the search by distance through the geolocation?

Hey, sorry for not getting back to you sooner. I don’t quite understand your question.

Ok, no problem thanks for reply, the question was if you had managed to work that idea or algorithm that you created for the search seemed great, I need to perform a search of people through its location by means of ranges in previously assigned distances if He finds them then notifying each of them.

It sounds like you want to be able to do a search around a user’s location?
If you use the approximation above, you will sacrifice accuracy for
performance. I developed a very basic library for doing some common
geospatial math. It’s called geomath. You will have to write the query code
manually. Also I’m not sure about your use case and your requirements, can
you be more specific?

OK if it is correct is a search for people that are in the range of distances assigned by the user and there then assign values return to those users a notification indicating that you are near.

I for example income 5 miles or kilometers and assigned other filters as tastes (music, food, books) I give look there he must notify the users through the push that I’m in their range and meet their tastes.

can show geomath to give you a look it have in one place hosted.?

Oh I think I understand. You have a slider where the user can specify a distance range (e.g. 0-5 or 5-10, etc.), and you are querying some user posts geotagged within that range. I think that these ranges are “rough” enough, and you will be able to benefit from using an approximation method, instead of a geoquery. This $lte/$gte approximation method is not for people who need exact polygon queries. It seems like you don’t really need exact polygon queries.

If it is correct is something like the image that I attached, does not need to be something so accurate in the location, just think that it could be through a study in distances to add a little to that error that you say is generated
.

I should also mention that if you need to query a distance range, e.g. with r_min and r_max, you can modify your query to query a square annulus by using $and! You can express this in your query usingthe square method: “find a document which is in this larger square, but not in this smaller sqaure”, and voila, you have queried a square annulus.

Hello @streemo I understand theoretically what you say but if you have an example of the more detailed code I would greatly appreciate it.