NEARBY appears to not sort correctly

[rshura]

I have this simple test case, using version 1.9.0:

DROP test
SET test 1 OBJECT '{"type":"Point","coordinates":[-149.831200065,61.1181799835]}'
SET test 2 OBJECT '{"type":"Point","coordinates":[-149.831220014,61.1185399862]}'
SET test 3 OBJECT '{"type":"Point","coordinates":[-149.832450058,61.1169899628]}'
SET test 4 OBJECT '{"type":"Point","coordinates":[-149.832280073,61.1170899589]}'
NEARBY test LIMIT 3 DISTANCE POINT 61.1177399755 -149.831590075

this returns:

{
   "elapsed" : "65.708µs",
   "count" : 3,
   "ok" : true,
   "objects" : [
      {
         "distance" : 53.22,
         "object" : {
            "type" : "Point",
            "coordinates" : [
               -149.831200065,
               61.1181799835
            ]
         },
         "id" : "1"
      },
      {
         "distance" : 91.15,
         "object" : {
            "type" : "Point",
            "coordinates" : [
               -149.831220014,
               61.1185399862
            ]
         },
         "id" : "2"
      },
      {
         "id" : "4",
         "distance" : 81.23,
         "object" : {
            "coordinates" : [
               -149.832280073,
               61.1170899589
            ],
            "type" : "Point"
         }
      }
   ],
   "cursor" : 0
}

I was expecting to get the points in the nearest-first order, according to the docs. Instead I get results that are 53, 91, and 81 meters away from the center of the search. Is this a bug, or am I missing something obvious here? Thanks in advance for any help!

Alex

[tidwall]

Hi Alex,

Thanks for bringing this to my attention.

I've seen fringe cases where points fall slightly out of order, but this is usually when points are close to the poles and are separated by more distance than you're showing. This behavior is a quirk of translating R-tree mercator coordinates and WGS84.

In your case the points are pretty close and it makes sense that the system should be returning them in order.

I'll need to investigate further and I'll keep you posted.

[rshura]

Thanks for a quick response!

Here's my original issue that seems like a bigger problem, but I might be missing something obvious, so maybe you can clue me in. I'm working on a dataset which has lots of addresses in the US mapped. Within that dataset, if I ask for NEARBY within 1000 meters from San Francisco, I get reasonably close matches, out of order as documented:

NEARBY addr LIMIT 3 DISTANCE POINT 37.774 -122.4194 1000

   "objects" : [
      {
         "id" : "102297964",
         "distance" : 996.63,
         "object" : {
            "type" : "Point",
            "coordinates" : [
               -122.409430007,
               37.7782699931,
               238082
            ]
         }
      },
      {
         "object" : {
            "coordinates" : [
               -122.417999329,
               37.7664985741,
               238031
            ],
            "type" : "Point"
         },
         "distance" : 843.16,
         "id" : "168389898"
      },
      {
         "object" : {
            "coordinates" : [
               -122.415985158,
               37.775356276,
               240532
            ],
            "type" : "Point"
         },
         "id" : "225177097",
         "distance" : 335.89
      }
   ]

However, if I ask for NEARBY without the radius specified, I'm expecting to get 3 closest points. Instead I'm getting some points on the East Coast. Those are also somewhat out of order between each other, but most importantly, why am I not getting San Francisco's points as the closest 3? Is this expected?

NEARBY addr LIMIT 3 DISTANCE POINT 37.774 -122.4194

   "objects" : [
      {
         "id" : "22157410",
         "distance" : 3616511.74,
         "object" : {
            "coordinates" : [
               -82.1618195716,
               34.1841506911,
               2722
            ],
            "type" : "Point"
         }
      },
      {
         "object" : {
            "type" : "Point",
            "coordinates" : [
               -84.4879800081,
               45.620376966,
               2754
            ]
         },
         "distance" : 3234760.87,
         "id" : "171454755"
      },
      {
         "object" : {
            "coordinates" : [
               -79.3628900405,
               41.8403299944,
               2870
            ],
            "type" : "Point"
         },
         "id" : "137636811",
         "distance" : 3666906.52
      }
   ]

[tidwall]

Within that dataset, if I ask for NEARBY within 1000 meters from San Francisco, I get reasonably close matches, out of order as documented:

This is normal behavior.

When a radius is provided the system performs a standard INTERSECTS on the outer boundary of the radius. This will always return back an accurate list but the results will come back in an undefined order. Adding the "LIMIT 3" is basically requesting "give me any 3 points inside the specified radius".

However, if I ask for NEARBY without the radius specified, I'm expecting to get 3 closest points. Instead I'm getting some points on the East Coast. Those are also somewhat out of order between each other, but most importantly, why am I not getting San Francisco's points as the closest 3? Is this expected?

Something is wrong here. I would like to reproduce the issue on my side asap. You mentioned this is with version 1.9.0. What's the operating system?

Thanks

[rshura]

It's on linux, kernel 3.13.0-123-generic, x86_64. Ubuntu trusty.

The dataset is pretty big, some 150 million points. How do we get it to your side?

[tidwall]

Thanks for the OS info. As for data, perhaps just a smaller segment is all I need. Would it be possible to extract a couple thousand random points around 45.620, -84.487 & 37.774, -122.419?

Hopefully I can identify the issue with just this data to start.

[hctareq]

@tidwall will the z values be significant for you for this test dataset we'll grab?

[tidwall]

@hctareq yes the Z coordinate is needed too.

[rshura]

Looks like the z-value is directly responsible. Here's the minimal test case:

DROP test
SET test 1 OBJECT '{"type":"Point","coordinates":[-84.4767280575,45.6304059969,100]}'
SET test 2 OBJECT '{"type":"Point","coordinates":[-122.399150021,37.7620299719,200]}'
NEARBY test LIMIT 3 DISTANCE POINT 37.774 -122.4194

produces

   "objects" : [
      {
         "id" : "1",
         "object" : {
            "coordinates" : [
               -84.4767280575,
               45.6304059969,
               100
            ],
            "type" : "Point"
         },
         "distance" : 3235674.8
      },
      {
         "object" : {
            "type" : "Point",
            "coordinates" : [
               -122.399150021,
               37.7620299719,
               200
            ]
         },
         "distance" : 2222.57,
         "id" : "2"
      }
   ],

[rshura]

Interestingly, if I use 1 and 2 or 10 and 20 instead of 100 and 200 then I don't see the bug. Seems like a large-enough z-value triggers the bug. As if after some z-value, the sorting was done on that instead of distance.

[tidwall]

I think you may have identified the root of the bug. The kNN operation works strictly on the coordinates stored in the 3D R-tree. The X and Y are -180 to 180 / -90 to 90 and the Z axis is unbounded and represented as meters. The kNN algorithm does a direct line of sight distance calculations from point to point in (XYZ). Because XY uses degrees and Z uses meters the result of the calculation won't represent point to point at ground level.

For example, here's an image of a bunch of cities on a 3D R-tree with elevation, but in mercator projection. You can see that the "height" of the Z axis can sometimes be taller than an entire continent is long.

Thus in the current state the kNN operation is not reliable when a meters Z coordinate is used. I consider this a bug of the system as Z is mostly used for elevation data in meters.

I have an idea that might fix the problem for the long term. But in the meantime the only workarounds that come to mind are to remove all Z coordinate or make Z coordinates tiny, such as millimeters/micrometers.

If this is the case then it should be easy to test on my side without the need for extra data. I'll see what I can do to turn out a patch asap.

[tidwall]

make Z coordinates tiny, such as millimeters/micrometers.

Scratch that, I mean to use a measurement system that is much larger, in order to make the values smaller. For example using kilometers or maybe x10000 will make the Z coordinate less signifigant during kNN operations.

[hctareq]

The docs (http://tile38.com/commands/set/#z-coordinate) mention timestamps as an example use of the Z coordinate, but it sounds like you're saying it's really meant to deal with meters as far as implementation details go. Going forward, do you see that staying the case to be able to compare in tandem with the lat/long dimensions?

[hctareq]

What I'm getting at is whether, longer term, the Z coordinate will be treated as a first class citizen in a 3D R-tree or if things will revert to 2D and the Z coordinate devolves to more of a normal "field." The wording in the docs is:

A z coordinate allows for optimized range queries for values such as Elevation and Timestamps

Now queries can search the z coordinate by treating it as a field:
NEARBY 1 WHERE z -15 130 POINTS 33 -115 100000

Which will look for all points that are within 100 kilometers of 33,-115 and have a z coordinate between -15 and 130. notice the lowercase z in the WHERE clause

[rshura]

Hmm, how can 100 meters of elevation be possibly affecting the distance of several thousand kilometers? In the last test case, the point 3 thousand km away is returned first, while the second point is only 2 km away. The 100 meters of elevation difference should not matter here, right?

[tidwall]

The docs (http://tile38.com/commands/set/#z-coordinate) mention timestamps as an example use of the Z coordinate, but it sounds like you're saying it's really meant to deal with meters as far as implementation details go.

The Z coordinate is used for meters/elevation for many (perhaps most) applications . Though it's occasionally used for speed or time, this is common in fleet-management systems.

What I'm getting at is whether, longer term, the Z coordinate will be treated as a first class citizen in a 3D R-tree or if things will revert to 2D and the Z coordinate devolves to more of a normal "field."

Yes, the plan is to keep the Z coordinate as a first class citizen. Though it's likely that there'll be some options with how the kNN operation works on the data.

[tidwall]

Hmm, how can 100 meters of elevation be possibly affecting the distance of several thousand kilometers?

This is because the Tile38 R-tree stores XY in degrees and Z is user-defined. The kNN operation assumes that XY and Z are all the same unit type. At the equator there're about 111km for every degree.

In the last test case, the point 3 thousand km away is returned first, while the second point is only 2 km away. The 100 meters of elevation difference should not matter here, right?

It matters because the calculation thinks that 100 meters is actually 100 degrees.

For example, the 3D distance for point 1:

(X1, Y1, Z1) = (-122.4194, 37.774, 0)
(X2, Y2, Z2) = (-84.4767280575, 45.6304059969, 100)

distance = 107.244438

and then point 2:

(X1, Y1, Z1) = (-122.4194, 37.774, 0)
(X2, Y2, Z2) = (-122.399150021, 37.7620299719, 200)

distance = 200.000001

So point 1 is coming back closer than point 2.

[rshura]

Ah, that makes sense now. And it definitely sounds like a bug :-)

We're going to work around this by removing z-value and using a separate field, as our values had nothing to do with elevation from the start, just didn't know that affected the distance.

Thanks!

[tidwall]

Yes this is a bug, but now I have some good ideas on how to fix it!

You're welcome and thank you very much for helping out with diagnosing the issue.

[tidwall]

I'm closing this issue and added the new bug entry #196.

[rshura]

Now that we're clear on the impact of Z, the original issue in the first comment is still a problem, in a purely 2D world. Should I open the new issue with just that, or should we re-open this one?

Thanks,
Alex

[tidwall]

The current version of Tile38 performs kNN operations in euclidian space. In order to get accurate ordering we'd need to move to a geodesic structure. This is done by converting 2D points in lat/lon (or 3D points with Z as meters) to a 3D point on a sphere. For example:

becomes

I've been working on this for v2.0 but unfortunately I'm still a ways out.

[tidwall]

In the meantime there may be ways to improve the results quite a bit. Though it's not likely to have perfect ordering in it's current state.

[tidwall]

I'll investigate further and keep you posted.

[tidwall]

I pushed an update to the master branch that provides better distance ordering.
Please let me know if this works for your case.

[rshura]

Everything looks correct now, thanks!

[tidwall]

That's good news. I'm going to close this issue for now, but feel free to reopen if you run into any problems. Thanks a bunch for your help.

[KrishnaPG]

Came across this while looking for z index support. Wondering if the geodesic structure, discussed above, has been adapted.
On similar note, If we need to run a cluster of tile38 servers, each catering to one particular segment of map (so that all queries related to one particular location, goes to one server that caters to that location queries), does tile38 internally manage the servers in the clusters in accordance to geodesic hierarchy and distribute queries in that order? Or the cluster is just master-slave clone copies (each containing the same structure without partition)

[pratibhajose]

what does first citizen mean?. is it that the value of z coordinate will be the final criterion of sorting?