3 ms·
Frustratingly light on detail, but the possible connections to http://arxiv.org/abs/1404.0703 http://arxiv.org/abs/1404.0703 are intriguing.
by jamii 11y ago
Frustratingly light on detail, but the possible connections to http://arxiv.org/abs/1404.0703 http://arxiv.org/abs/1404.0703 are intriguing.
- jamii 11y agoSpecifically, the linked paper models indexes on a table as sets of n-dimensional volumes showing where rows aren't. It then gives a join algorithm that is asymptotically instance-optimal (up to a poly-log factor) ie better than any previous result. Unfortunately it relies on efficiently representing and querying the set of volumes built up during the query process and the data structure used in the paper is ridiculously impractical. I haven't seen an implementation yet that managed to tame the constant factors. Perhaps seeing how the OP models volumes/constraints would help.