Re:Geometric Search Trees
by carsonfarmer on Thursday September 19, 2024 @12:18PM
(#41593445)
Yes this exactly. Another really simple way to do this, is to use alternating leading and trailing zero counts in the hash in your nested G-trees. Simple, and pretty effective.
Hmmm... if you need to go deeper (because 1/4 of all hashes have zero leading zeros and zero trailing zeros), you can generalize this by converting the hash into its run-length encoding to get a sequence of rank functions where finding values with the same rank for all rank functions is equivalent to finding hash collisions. Very nice.
Re:Geometric Search Trees
by carsonfarmer on Tuesday September 24, 2024 @07:08PM
(#41641958)
Whoah, I totally hadn't taken the thought experiment this far. This is fantastic! I'd like to explore this further, interested in a quick research chat/sync some time? My email is linked from the paper.
If you want to break that up with dummy elements, you now have the problem of choosing those dummies in a history-independent manner efficiently.
But I think their recursive construction with G-trees of G-trees of ... might work if nodes with too many elements are stored as G-trees with a different, independent rank function (e.g. using a hash function with different salt). Producing many nodes with the same ranks should then get exponentially harder as the number of independent rank functions increases.