[SERVER-15576] Floating-point inaccuracy when unhashing GeoHash to box Created: 08/Oct/14  Updated: 25/Oct/14  Resolved: 17/Oct/14

Status: Closed
Project: Core Server
Component/s: Geo
Affects Version/s: 2.7.7
Fix Version/s: 2.7.8

Type: Bug Priority: Major - P3
Reporter: Siyuan Zhou Assignee: Siyuan Zhou
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Backwards Compatibility: Fully Compatible
Operating System: ALL
Participants:

 Description   

Assume P is the lower left corner of a geohash. We hash and unhash the point in the following way.

// hash
h = hash(p) = (p - min) / scale
// h.x and h.y should be integers with a rounding error.
 
// unhash
p_approx = h * scale + min

Due to the floating-point accuracy, p != p_approx. As a result, it is possible that the box unhash(hash(p)) doesn't contain p. The following script gives an example.

db.geo_precision.drop();
 
db.geo_precision.insert({loc: [-7201198.6497758823, 0.10000000000000001]});
var min = [ -7201198.65, 0.095 ];
var max = [ -7201198.64977588, 0.11 ];
// The document lives in the box defined by min and max.
assert.eq(1, db.geo_precision.find({loc: {$within: {$box: [min, max]}}}).count());
 
// 2d index should return the same result. But failed with 2.7.7.
db.geo_precision.ensureIndex({loc: "2d"}, {min: -100000000.3, max: 100000000.3, bits: 32});
assert.eq(1, db.geo_precision.find({loc: {$within: {$box: [min, max]}}}).count());

In the above example, the point is outside the box of its geohash, so with a carefully constructed query, the covering of the query contains that document but doesn't intersect with the box of geohash. Thus the covering will exclude the GeoHash that contains the document and return no documents.

To guarantee the point is alway contained by the box of its GeoHash, we should expand the box by a small error bound when unhashing geohash to box. Since the unhashed boxes are only used by the following the functions, expanding the box will keep the same contract.

// Return true if we are confident that this region contains the box.
R2Region::fastContains(const Box& other);
// Return true if we are confident that this region disjoints with the box.
R2Region::fastDisjoint(const Box& other);

This regression bug is introduced by the covering of 2d shapes in 2.7.



 Comments   
Comment by Githook User [ 17/Oct/14 ]

Author:

{u'username': u'visualzhou', u'name': u'Siyuan Zhou', u'email': u'siyuan.zhou@mongodb.com'}

Message: SERVER-15576 Floating-point inaccuracy when unhashing GeoHash to box
Branch: master
https://github.com/mongodb/mongo/commit/4e10def7b1ea9da02a5218d592073ff2587544cd

Generated at Thu Feb 08 03:38:24 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.