Isn’t this just a trie with only two levels? It seems to me that this technique isn’t particularly unknown, as it’s taught in most elementary CS courses.
I think it would be fair to say that it's a kind of funny trie-hash-table hybrid. What's neat though is that it manages to achieve better space bounds than either a trie or a hash table would on their own.
I didn't invent the algorithmic idea --- it's basically a simplification of a data structure that was published in ICALP 2003 [1]. As far as I know, the idea of combining hash tables and tries in this kind of way (despite being incredibly simple!) doesn't appear in either the theoretical or experimental literature prior to that.
I'd be interested in any other earlier sources that people might have.
not quite, as the 2nd level is a hash table which is very un-trie-like. it shares the idea that you don't store the implicit bits known by the address of the first level like a trie.
I didn't invent the algorithmic idea --- it's basically a simplification of a data structure that was published in ICALP 2003 [1]. As far as I know, the idea of combining hash tables and tries in this kind of way (despite being incredibly simple!) doesn't appear in either the theoretical or experimental literature prior to that.
I'd be interested in any other earlier sources that people might have.
[1] Raman, Rao. Succinct Dynamic Dictionaries and Trees. https://link.springer.com/chapter/10.1007/3-540-45061-0_30. ICALP, 2003.