Succinct trie

[daniel-j-h]

We need a succinct trie to compress a hierarchy of cells where we cover graph nodes based on their location.

The cells could then look like quadkeys, recursively dividing the space.

Neighboring cells

• 120230
• 120231
• 120232
• 120233

and their parent cell 12023.

With a succinct tree we can efficiently store this hierarchy in a compact way.

See https://labs.mapbox.com/what-the-tile/

Here is a good introduction http://stevehanov.ca/blog/?id=120

Depends on rank/select for trie traversal

• https://github.com/tinygraph/tinygraph/issues/14

[daniel-j-h]

Fast Compressed Tries through Path Decompositions could be interesting