Bug in nearBy() calculation? about geo-nearby HOT 9 CLOSED

Hello!
That's not a bug. You can read how it works in links below.
https://github.com/yinqiwen/ardb/wiki/Spatial-Index
arjunmehta/node-geo-proximity#12

tl;dr:
The larger the radius - the less accuracy. That's why is recommended to use array instead of single radius value.
It's a price for fast performance.

from geo-nearby.

Ok, that's good news! Can you say a bit more about the array argument? I
did try using an array to pass in a range, but my results were the same.

On Thursday, October 27, 2016, Alexey Bystrov [email protected]
wrote:

Hello!
That's not a bug. You can read how it works in links below.
https://github.com/yinqiwen/ardb/wiki/Spatial-Index
arjunmehta/node-geo-proximity#12
arjunmehta/node-geo-proximity#12

tl;dr:
The larger the radius - the less accuracy. That's why is recommended to
use array instead of single radius value.
It's a price for fast performance.

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
#1 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/ADgUyijmioUWSDufZE7018_PC4lWjPJNks5q4IxMgaJpZM4KhvZb
.

from geo-nearby.

Due to the nature of Geohash and 2D Spatial index, a range of distances is more accurate than single distance.

For example: there is file fixture5.json in test/fixtures folder.
The code below will cause next output.

const dataFive = require('./test/fixtures/fixture5.json');
const geo = new Geo(dataFive, { sort: true });
geo.limit(0).nearBy(-33.87, 151.2, 100000);

Output:

[ { i: undefined, g: 3252286958958578 },
  { i: undefined, g: 3252293339827155 },
  { i: undefined, g: 3252304056694520 },
  { i: undefined, g: 3252304640688864 },
  { i: undefined, g: 3252306408869163 },
  { i: undefined, g: 3252306537127870 },
  { i: undefined, g: 3252306875619798 },
  { i: undefined, g: 3252312726776733 },
  { i: undefined, g: 3252315412968989 },
  { i: undefined, g: 3252316502937030 },
  { i: undefined, g: 3252316781384376 },
  { i: undefined, g: 3252320515702462 },
  { i: undefined, g: 3252320644203520 },
  { i: undefined, g: 3252320679490297 },
  { i: undefined, g: 3252320950624051 },
  { i: undefined, g: 3252342689746688 },
  { i: undefined, g: 3252342876095427 } ]

If we change single distance to a range of distances ([250, 100000]), elements and their numbers isn't change but their order is changed.

const dataFive = require('./test/fixtures/fixture5.json');
const geo = new Geo(dataFive, { sort: true });
geo.limit(0).nearBy(-33.87, 151.2, [250, 100000]);

Output:

[ { i: undefined, g: 3252342876095427 },
  { i: undefined, g: 3252320515702462 },
  { i: undefined, g: 3252320644203520 },
  { i: undefined, g: 3252320679490297 },
  { i: undefined, g: 3252342689746688 },
  { i: undefined, g: 3252316502937030 },
  { i: undefined, g: 3252320950624051 },
  { i: undefined, g: 3252312726776733 },
  { i: undefined, g: 3252315412968989 },
  { i: undefined, g: 3252316781384376 },
  { i: undefined, g: 3252286958958578 },
  { i: undefined, g: 3252293339827155 },
  { i: undefined, g: 3252304056694520 },
  { i: undefined, g: 3252304640688864 },
  { i: undefined, g: 3252306408869163 },
  { i: undefined, g: 3252306537127870 },
  { i: undefined, g: 3252306875619798 } ]

It happens because nearBy function called several times for every distance of range, gradually increasing the distance and reducing accuracy.
tl;dr: if you want more accurate output - use a range of distance (array).

from geo-nearby.

If I used an array like [250, 100000] does that mean that a point less
than 250m away would be excluded?

Is one method faster?

On Thursday, October 27, 2016, Alexey Bystrov [email protected]
wrote:

Due to the nature of Geohash and 2D Spatial index, a range of distances is
more accurate than single distance.

For example: there is file fixture5.json
https://github.com/strikeentco/geo-nearby/blob/master/test/fixtures/fixture5.json
in test/fixtures folder.
The code below will cause next output.

const dataFive = require('./test/fixtures/fixture5.json');const geo = new Geo(dataFive, { sort: true });geo.limit(0).nearBy(-33.87, 151.2, 100000);

Output:

[ { i: undefined, g: 3252286958958578 },
{ i: undefined, g: 3252293339827155 },
{ i: undefined, g: 3252304056694520 },
{ i: undefined, g: 3252304640688864 },
{ i: undefined, g: 3252306408869163 },
{ i: undefined, g: 3252306537127870 },
{ i: undefined, g: 3252306875619798 },
{ i: undefined, g: 3252312726776733 },
{ i: undefined, g: 3252315412968989 },
{ i: undefined, g: 3252316502937030 },
{ i: undefined, g: 3252316781384376 },
{ i: undefined, g: 3252320515702462 },
{ i: undefined, g: 3252320644203520 },
{ i: undefined, g: 3252320679490297 },
{ i: undefined, g: 3252320950624051 },
{ i: undefined, g: 3252342689746688 },
{ i: undefined, g: 3252342876095427 } ]

If we change single distance to a range of distances ([250, 100000]),
elements and their numbers isn't change but their order is changed.

const dataFive = require('./test/fixtures/fixture5.json');const geo = new Geo(dataFive, { sort: true });geo.limit(0).nearBy(-33.87, 151.2, [250, 100000]);

Output:

[ { i: undefined, g: 3252342876095427 },
{ i: undefined, g: 3252320515702462 },
{ i: undefined, g: 3252320644203520 },
{ i: undefined, g: 3252320679490297 },
{ i: undefined, g: 3252342689746688 },
{ i: undefined, g: 3252316502937030 },
{ i: undefined, g: 3252320950624051 },
{ i: undefined, g: 3252312726776733 },
{ i: undefined, g: 3252315412968989 },
{ i: undefined, g: 3252316781384376 },
{ i: undefined, g: 3252286958958578 },
{ i: undefined, g: 3252293339827155 },
{ i: undefined, g: 3252304056694520 },
{ i: undefined, g: 3252304640688864 },
{ i: undefined, g: 3252306408869163 },
{ i: undefined, g: 3252306537127870 },
{ i: undefined, g: 3252306875619798 } ]

It happens because nearBy
https://github.com/strikeentco/geo-nearby/blob/master/main.js#L60
function called several times for every distance of range, gradually
increasing the distance and reducing accuracy.
tl;dr: if you want more accurate output - use a range of distance
(array).

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
#1 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/ADgUyoSDS_f7rhSWxxosxOyXUGGMAMgWks5q4NC8gaJpZM4KhvZb
.

from geo-nearby.

If I used an array like [250, 100000] does that mean that a point less
than 250m away would be excluded?

No, it doesn't.
For [250, 100000] library will search point in next distances:
252.9, 510.02, 1015.8, 2236.5, 3866.9, 8749.7, 15664, 33163.5, 72226.3, 150350
If limit is set, library will search using distances from above, while the number of found points hasn't reached the limit.

Is one method faster?

Yes, but if data set is sorted and binary search is used ({ sorted: true } option), the time difference is small.
Little more info about speed and performance is here: #2 (comment)

from geo-nearby.

Thank you for your replies.

A possible enhancement might be to store the latlng along with the id and
geohash when creating the db, and then add either another search method or
a search option that does the haversine distance calculation and filters
the results to only contain those points within the actual search radius.
This would make the library more user friendly, imho.

On Thursday, October 27, 2016, Alexey Bystrov [email protected]
wrote:

If I used an array like [250, 100000] does that mean that a point less
than 250m away would be excluded?

No, it doesn't.
For [250, 100000] library will search point in next distances:
252.9, 510.02, 1015.8, 2236.5, 3866.9, 8749.7, 15664, 33163.5, 72226.3,
150350
If limit is set, library will search using distances from above, while the
number of found points hasn't reached the limit.

Is one method faster?

Yes, but if data set is sorted and binary search is used ({ sorted: true }
option), the time difference is small.
Little more info about speed and performance is here: #2 (comment)
#2 (comment)

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
#1 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/ADgUysEBlt1Y0GS6gUVJ9zdt1y6FU2PTks5q4RbHgaJpZM4KhvZb
.

from geo-nearby.

Thank you for your interest and suggestions.

I was thinking about increasing accuracy, but right now I don't have enough time for this.
Also adding new properties to data set will cause to additional memory usage, that's why right now data set only contains id and geoHash. Using geoHash we can find closest location and with id we can get additional information from any other resource/db (Redis, MySQL, file etc.)

from geo-nearby.

Well, the increased memory usage could simply be documented. Let the user
weigh the costs, etc. I found a small npm module, called haversine-distance
I think, that does the calculation and is easy to use.

The data set I'm loading into geonearby actually has the latlng included.
Because it also has the 'i' and 'g' properties, it gets loaded unmodified.
When I call the nearBy() method I get back objects ready to filter. It
works amazingly well.

On Thursday, October 27, 2016, Alexey Bystrov [email protected]
wrote:

Thank you for your interest and suggestions.

I was thinking about increasing accuracy, but right now I don't have
enough time for this.
Also adding new properties to data set will cause to additional memory
usage, that's why right now data set only contains id and geoHash. Using
geoHash we can find closest location and with id we can get additional
information from any other resource/db (Redis, MySQL, file etc.)

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
#1 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/ADgUyvm7CKGhF7lCJc0GRQI9dXGg-2uwks5q4R0sgaJpZM4KhvZb
.

from geo-nearby.

If I understood you correctly, you can use code below for your purposes:

const haversine = require('haversine-distance');
const geo = new Geo(dataSet, { sorted: true });
geo
  .limit(0)
  .nearBy(-33.87, 151.2, [250, 100000])
  .filter(el => haversine(
    { latitude: -33.87, longitude: 151.2 },
    { latitude: el.lat, longitude: el.lon }
  ) <= 100000);

Where 100000 is max distance.

from geo-nearby.