3 ms·

TBH even quadkeys are a fun answer to OPs question, many people aren't aware of them. Simple explanation: If you have data with x y coordinates and you know t

by pacaro 4y ago

TBH even quadkeys are a fun answer to OPs question, many people aren't aware of them. Simple explanation: If you have data with x y coordinates and you know the bounds. To compute the quad key for a point: 1. The key starts as the empty string. (I've also seen it start with "Z" to handle points outside the bounds) 2. Divide the space into 4 quadrants 3. determine which quadrant the point falls in, append a letter (A-D depending on the quadrant) to the key 4. Repeat step 3 using the quadrant bounds (i.e. recursively smaller area) until you have desired accuracy This can then be used to efficiently find points within rectangular bounds.

blueblob 4y ago
From a basic binary search, this is very intuitive. Your explanation was well written.
yellowflash 4y ago
That's how mongodb geospatial indexes work IIRC
- pacaro 4y ago
  It's tried and tested for sure, I first encountered them in 94 but I assume they're much older. A little sleuthing shows that (TIL) they are an application of Z-order curves, which date back to 1906
- soren1 4y ago
  Was about to mention this. If I recall correctly, the 2d-sphere index rounds geospatial coordinates to 5 decimals. Very occasionally, I found it would distort polygon geometries just enough to cause them to become invalid (e.g. overlapping geometries), which causes the index build to fail. In my recent experience working with collections containing million of documents, each containing a geoJSON-style polygon/multipolygon representing a property (i.e. a block of land), I found invalid geometries to occur for about 1 document in 1 million. For a while, I suspected the data-vendor was the cause, however it became more puzzling when other geospatial software confirmed they were valid. Eventually we traced the issue to the 2d-sphere index. A very clever workaround was suggested by a colleague of mine, inspired by [1]. It preserved the original geometries. In each document, we added a new field containing the geometry's extent. A 2d-sphere index was then built on the extent field instead of the original geometry field. Invalid geometries were no longer an issue since we were dealing with much simpler geometries that were substantially larger than the max precision of the index. When running geoIntersects queries on our collection of millions of documents, we did so in 2 steps (aggregation queries): 1. GeoIntersects on the extent field (uses the index). 2. On the result set from the last step, perform geoIntersects on the original geometry field (operates on a much smaller set of records compared to querying the collection directly) [1] https://www.mongodb.com/docs/manual/tutorial/create-queries-that-ensure-selectivity/ https://www.mongodb.com/docs/manual/tutorial/create-queries-...
  - skylabmelody 4y ago
    Seems exactly like broad phase and narrow phase in games physics engine.
    - djmips 4y ago
      The same things get invented over and over again and named different things depending on the field. Sometimes it's not immediately clear that they are the same things mathematically.
zbobet2012 4y ago
A lot of people don't know about the related segment and interval trees. Both efficiently allow you to compute all time ranges that overlap a point. This can be generalized to higher dimensional spaces. For example if you have a set of calendar invites with a start and stop time (say tens of millions of them) and you want to find all invites which span 12pm (that is start before 12 and end after 12) you want an interval tree. https://en.wikipedia.org/wiki/Interval_tree https://en.wikipedia.org/wiki/Interval_tree
Gravityloss 4y ago
Hmm... the quad keys end up looking very much like coordinates. In the regular coordinates, the most significant bit divides the space in half, then the next bit divides those spaces in halves etc... You could get a single "key" by just having a sequence of bits with most significant bit of x coordinate, most significant bit if of y coordinate, second most significant bit of x coordinate, second most significant bit of y coordinate, third....

by pacaro 4y ago

blueblob 4y ago

From a basic binary search, this is very intuitive. Your explanation was well written.

yellowflash 4y ago

That's how mongodb geospatial indexes work IIRC

pacaro 4y ago
It's tried and tested for sure, I first encountered them in 94 but I assume they're much older. A little sleuthing shows that (TIL) they are an application of Z-order curves, which date back to 1906
soren1 4y ago
Was about to mention this. If I recall correctly, the 2d-sphere index rounds geospatial coordinates to 5 decimals. Very occasionally, I found it would distort polygon geometries just enough to cause them to become invalid (e.g. overlapping geometries), which causes the index build to fail. In my recent experience working with collections containing million of documents, each containing a geoJSON-style polygon/multipolygon representing a property (i.e. a block of land), I found invalid geometries to occur for about 1 document in 1 million. For a while, I suspected the data-vendor was the cause, however it became more puzzling when other geospatial software confirmed they were valid. Eventually we traced the issue to the 2d-sphere index. A very clever workaround was suggested by a colleague of mine, inspired by [1]. It preserved the original geometries. In each document, we added a new field containing the geometry's extent. A 2d-sphere index was then built on the extent field instead of the original geometry field. Invalid geometries were no longer an issue since we were dealing with much simpler geometries that were substantially larger than the max precision of the index. When running geoIntersects queries on our collection of millions of documents, we did so in 2 steps (aggregation queries): 1. GeoIntersects on the extent field (uses the index). 2. On the result set from the last step, perform geoIntersects on the original geometry field (operates on a much smaller set of records compared to querying the collection directly) [1] https://www.mongodb.com/docs/manual/tutorial/create-queries-that-ensure-selectivity/ https://www.mongodb.com/docs/manual/tutorial/create-queries-...
- skylabmelody 4y ago
  Seems exactly like broad phase and narrow phase in games physics engine.
  - djmips 4y ago
    The same things get invented over and over again and named different things depending on the field. Sometimes it's not immediately clear that they are the same things mathematically.

zbobet2012 4y ago

A lot of people don't know about the related segment and interval trees. Both efficiently allow you to compute all time ranges that overlap a point. This can be generalized to higher dimensional spaces. For example if you have a set of calendar invites with a start and stop time (say tens of millions of them) and you want to find all invites which span 12pm (that is start before 12 and end after 12) you want an interval tree. https://en.wikipedia.org/wiki/Interval_tree https://en.wikipedia.org/wiki/Interval_tree

Gravityloss 4y ago

Hmm... the quad keys end up looking very much like coordinates. In the regular coordinates, the most significant bit divides the space in half, then the next bit divides those spaces in halves etc... You could get a single "key" by just having a sequence of bits with most significant bit of x coordinate, most significant bit if of y coordinate, second most significant bit of x coordinate, second most significant bit of y coordinate, third....