@michaelcadilhac , I thought a bit about having an array of "buckets" for a fixed number of dimensions. This seems orthogonal to kdtrees since it does not speed up dominance queries (it does empirically, just not theoretically). The reason is that if we nest k-ary trees then it seems hard to balance the resulting tree.
I propose we add a bucket_backed.hh implementation of antichains to try the idea out. This would be an alternative to vector_backed.hh in which we fix a dimension to have a vector of k buckets for that one dimension.
I believe I have this already implemented; I'm experimenting with it at this point. I'm playing with several parameters, including:
How to pick the dimension that gets bucketed? Every time a new antichain is created, we have an opportunity to change the dimension, for instance based on the first (few) vectors inserted.
When iterating the antichain (this is done when searching for critical signals), what's the order in which we want to list the buckets? It seems "fair" to start at the middle bucket.
@michaelcadilhac , I thought a bit about having an array of "buckets" for a fixed number of dimensions. This seems orthogonal to kdtrees since it does not speed up dominance queries (it does empirically, just not theoretically). The reason is that if we nest k-ary trees then it seems hard to balance the resulting tree.
I propose we add a
bucket_backed.hh
implementation of antichains to try the idea out. This would be an alternative tovector_backed.hh
in which we fix a dimension to have a vector ofk
buckets for that one dimension.