For superset queries of small sets with keys that are high in the ordering, I notice that the algorithm has to explore every branch of the trie that's lower (than the lowest key) in the ordering, which in that case is most of the branches. So I'm wondering if it would be worth maintaining three copies of the set trie internally, each one uses a different hashing of the keys (which each have a different, random order). A key that's high in the natural ordering is unlikely to be high in both of the other orderings as well. The smallest of three random values will usually be below average, usually it will be quite small.
Each key has three hashings. The new algorithm would only search in the trie corresponding to the lowest of the key's hashings.
I wrote a little deno script to find out how much of an impact this could make. Here's its output. And like, once you have 6 copies (6 hashings), 84% of keys will have a minimum hashing that's lower than MAX_KEY/4 (in the lowest 25% of all keys).
The impact of keeping multiple copies for avoiding being high is much greater, with 9 hashings, none of the 500 trials lacked a hash that was lower than MAX_KEY/2. This feels like an off by one bug??
Regardless, that's my thought budget for this expended for the day. I might come back and implement this and think more about whether this would be practical, but I might not. (It'll depend on whether it turns out that I can really use set tries in what I'm doing.)
For superset queries of small sets with keys that are high in the ordering, I notice that the algorithm has to explore every branch of the trie that's lower (than the lowest key) in the ordering, which in that case is most of the branches. So I'm wondering if it would be worth maintaining three copies of the set trie internally, each one uses a different hashing of the keys (which each have a different, random order). A key that's high in the natural ordering is unlikely to be high in both of the other orderings as well. The smallest of three random values will usually be below average, usually it will be quite small.
Each key has three hashings. The new algorithm would only search in the trie corresponding to the lowest of the key's hashings.
I wrote a little deno script to find out how much of an impact this could make. Here's its output. And like, once you have 6 copies (6 hashings), 84% of keys will have a minimum hashing that's lower than
MAX_KEY/4(in the lowest 25% of all keys).The impact of keeping multiple copies for avoiding being high is much greater, with 9 hashings, none of the 500 trials lacked a hash that was lower than MAX_KEY/2. This feels like an off by one bug??
Regardless, that's my thought budget for this expended for the day. I might come back and implement this and think more about whether this would be practical, but I might not. (It'll depend on whether it turns out that I can really use set tries in what I'm doing.)