News for hackers. Stuff that matters.
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.
Re:Geometric Search Trees by yorwba on Thursday September 19, 2024 @02:55PM (#41595084)
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.