-
Notifications
You must be signed in to change notification settings - Fork 78
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
[Question] How to efficiently query using H3 #100
Comments
You can do something similar with H3. If you look at the bit layout of an H3 index at the bottom of this page you can see that the highest precision bits for the indexing are at the end. And looking at the resolution table resolution 10 has a long radius of ~66 meters (short radius would be ~57m), so the diameter would be ~132m at max and ~114m at min, so I think that would be the appropriate sizing. This is equivalent to the geohashing approach: indexing your data at resolution 10 and masking all of the bits except the actual resolution bits that you care about for the radius you've decided on based on the resolution table, but the centerpoint would be the center of the fixed hexagon that your query point happened to fall into, which could be up to 66 meters away (if the point just barely fell in the range). If that's fine with you, you can stop here. So I'd recommend indexing your data at resolution 11 and then querying at resolution 11 plus the 1 k-ring around it to reconstruct the same area as a resolution 10 hexagon, but with a better centering around your query point (it will only be off by up to ~25 meters with this approach). If you could use resolution 12 you'd get that error down to just ~1 meter, but that requires too many indexes for firestore, apparently, so you'd have to break your query into two. This is assuming that you can do a list of range queries, though. If possible then you can improve the accuracy for all of the radii (for the chosen resolution query one resolution below plus the k-ring, then bitmask it for your query). If you're further taking the returned list and filtering it to the exact radius the user queried, I would even more highly recommend the k-ring approach -- you only have to filter the outer ring of results, not the inner hexagon (or any inner rings). Here I would recommend going to resolution 12 for your base indexing and then do two queries: the k-ring of 1 around the centerpoint and then the "hexRing" (the hollow ring) of 2 around that; only the second query needs the actual radius filter pass and the amount of post-query filtering you have to do has been cut in ~half. |
In reference to the indexing order, you can see a demonstration here: https://observablehq.com/@nrabinowitz/h3-indexing-order You shouldn't rely on indexing order for range queries, because if you cross the boundary of a coarse-resolution ancestor cell you could get one or more cells in your k-ring with substantially different index numbers, and you wouldn't want all the indexes in between. The rule for H3 is that indexes that are numerically close are geographically close, but the reverse is not necessarily true. |
Thanks for your quick and detailed responses. I've tried to play around with this approach in a sample environment, but I couldn't get it working. Note:
e.g. those are my krings:
which represent the following numbers:
I don't really get where I need |
So you would need to bitmask, because "before" (higher in the numeric representation) the set of index values in the number, there's also a 4-bit field that stores the resolution itself. That would need to be bitmasked out, or replaced with the resolution that you're indexing the data into firestore. The "b" in "8b1e..." is that resolution segment, which is resolution 11. Since firestore is so limited, I would recommend dropping the k-ring idea and querying for a single "index", but storing the indexes in a "chopped" form. Compute the index for each datapoint you're storing, then bitmask everything to zero except the resolution bits, and then only from resolutions 0 to 11. Now when you query for whichever radius is appropriate, you snap the query to the resolution one level "up" from the specified radius and bitmask that H3 index to only the resolution bits that are set. Then you copy that trimmed H3 index and add a bitmask for all of the resolutions below the search resolution down to resolution 11 inclusive and you flip those bits all to 1s. This creates your min-max range that you can use in a compound query: https://firebase.google.com/docs/firestore/query-data/queries#compound_queries Basically So the whole thing is kinda like:
This has the large offset issue. You can resolve that by doing 7 queries with a k-ring one resolution finer, but it looks like it has to be 7 separate queries in firestore because of their strange query limitations. |
Yes, it sucks that they're still so limited after such a long time of "being in beta". @nrabinowitz and @dfellis thank you so much for your explanations, those look like very clever solutions/workarounds to my problem, I'm going to try this now. 👍 EDIT: What |
So the const resMask = [
246290604621824n,
30786325577728n,
3848290697216n,
481036337152n,
60129542144n,
7516192768n,
939524096n,
117440512n,
14680064n,
1835008n,
229376n,
28672n,
3584n,
448n,
56n,
7n,
] The So you'll want to modify that const h3Index = BigInt('0x' + h3.geoToH3(lat, lng, res)) After that put an const myData = await myTable.where('trimmedData', '>=', lowerBoundTrimmedIndex.toString()).where('trimmedIndex', '<=', upperBoundTrimmedIndex.toString()) The |
Hi!
I'm creating an app which shows nearby posts in a customizeable radius (with accuracy of ~100m). I've found h3 to be a very efficient library, but I couldn't quite figure out how to efficiently query my firestore NoSQL database using H3, since firestore is very limited in querying capabilities.
I've currently come up with this solution:
While this does indeed return results for me, it is very inefficient. For this simple query, it actually executes 17 queries (!!) because firestore has a limit of maximum
10
items in an array in thein
query (that's why I'm batching the neighbours into arrays of 10 elements), and I'm comparing for exact matches, so I'm forced to using the same precision for all my h3 hexagons.Using geohashes, I can find by range since they're alphabetically sorted. E.g. I can filter for
bc
->bc~
which gives me all squares that start withbc
.Now let's get to my actual questions:
871e064d5ffffff
->871e06498ffffff
, plus everything in range of871e0649bffffff
->871e06509ffffff
... or in other words "larger than this h3 but smaller than this h3")Thanks for your help!
The text was updated successfully, but these errors were encountered: