Skip to content
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

Better tokens suggestion #11

Open
ppKrauss opened this issue Apr 30, 2022 · 3 comments
Open

Better tokens suggestion #11

ppKrauss opened this issue Apr 30, 2022 · 3 comments
Labels
enhancement New feature or request

Comments

@ppKrauss
Copy link

ppKrauss commented Apr 30, 2022

Hi @aaliddell, good work! s2cell is a good project to test new efficient geocodes. This issue is a concept-proof suggestion.

As you say at s2-tokens,

S2 tokens can be considered analogous to the Geohash encoding system, (...). However, unlike Geohash, you cannot just chop off characters from a high precision S2 token to get a parent lower precision token, since the trailing 1 bit in the cell ID would not be set correctly in most cases.

Well, it's a "one bit problem", let's fix this bit! All the cell ID, except face prefix, is a good hiearchical code: each 2 bits (so base4 number) represents a hierarchical level... I think we can fix it by answering "Do we need all 32 bits for all applications?"

There are some application for the level30 bit? it is a cell of ~8 mm of side (0.008 m!)... Let's check a real life application, as addresses: the uncertainty ranges from 3 meters (urban areas) to 15 meters (rural areas), as illustrated below.

... So we can discard a bit! We can do a bitwise operation of rotate right in the 32 bits integer representation, interpretating it as a adding a 0-bit to the face, resulting in 4 bits instead 3 bits as face identifier.

Using your level-1 example, 00101100...000, after rotate will be 00010110...000. Your level29 example, 001011101...00100, will be 0001011101...0010.

We can encode/decode this cell ID representation (the "hierarchical token" - htk) to original token (otk) using rotate:

  • otk2htk(oID) rotate right
  • htk2otk(hID) rotate left

What do you think?

@aaliddell
Copy link
Owner

Hi, an interesting idea. I’m not sure I see how shifting right will let you drop chars from the output token though, as the issue that prevents blind truncation is the trailing 1 bit that needs to be placed correctly. Without updating the trailing bit position, IIRC you end up with either invalid cell IDs or incorrect ‘parents’. See comments about trailing but here: https://docs.s2cell.aliddell.com/en/stable/s2_concepts.html#cell-id

However, I think there may be some adaptation of this idea that could work. I haven’t figured it out, but it’d require converting a cell ID to a non-standard ‘truncatable cell ID’.

You may also want to discuss this with the proper upstream S2 owners, rather than this derivative repo.

@aaliddell aaliddell added the enhancement New feature or request label May 17, 2022
@ppKrauss
Copy link
Author

ppKrauss commented Feb 14, 2023

I’m not sure I see how shifting right will let you drop chars from the output token though

The use of "hierarchical hexadecimals" with space-filling curves was illustrated here, selecting base 16h. To produce hierarchical S2 tokens, it is a two-step procedure:

  1. Convert binary representation.
  2. Base4 or base16h conversion, for human representation.

The step1 is more than a bit-shift when dealing with a leaf cell, we need to transform (truncate) leafs to the level 29:

image

Remember that in real life we never use less than 1 m², because it is GPS error, map error, etc.

The step2 is not a direct 64bits positive integer conversion, I suggest to convert it into a bit-string. The trailing 1 bit is a "cut here for a bit-string representation".

@aaliddell
Copy link
Owner

Would you be able to put together demo code of converting a cell ID to a truncatable string token using this method? I think I see now where you are heading, but this is also best addressed to the S2 mailing list since any different token spec would need wider discussion: https://groups.google.com/g/s2geometry-io?pli=1

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

2 participants