2
$\begingroup$

Problem

I'm looking for a data structure to incrementally maintain a Pareto Front consisting of tuples in the high-dimensional space $(\mathbb{R} \cup \{\pm \infty\})^K$, with the number of dimensions $K \approx 5000$. These tuples are sparse: for any give tuple most (>90%) of the dimensions will have a value equal to either $\pm \infty$. Which dimensions are sparse is different for each tuple. The size of the frontier at any single time will be limited to about 10 million tuples.

The data structure only needs to support one operation: add(new) -> boolean, with the following semantics:

  1. Remove the old tuples dominated by new from the Front if any.
  2. If any old tuple currently in the Front dominates (or is equal to) new, don't do anything and return false.
  3. If no old tuple was found that dominates (or is equal to) new, add new to the Front and return true.

Note that thanks to the transitive property of dominance some of these cases are exclusive: once we have have hit (1) and removed an old tuple we can stop checking for condition (2), and once we have found an example of (2), we can stop looking for case (1) and (3) and exit early.

This operation needs to be as fast as possible, certainly faster then $O(n)$. Only the average case is important, amortization and being weak against adversarial inputs is fine.

In practice for the surrounding setup cases (2) and (3) both happen around 50% of the time, and step (1) removes on average 0.7 old tuples per newly inserted tuple, with the occasional outlier that removes a lot of old tuples.

Explored solutions

I've been tinkering with this for a while, and these are the ideas I've explored so far:

  • A simple unsorted linear list of tuples. This means that the add operation runs in O(n), which is too slow.
    • Changing this list to be sorted by least-recently used doesn't help much: in case of (3) the entire list still needs to be checked.
  • The generalization of quadtrees and octrees don't work because of the curse of conditionality, having $2^K$ children at each level is impossible.
  • A KD-tree. There are some problems with this approach:
    • It's hard to come up with a good ordering of the axes; meaning that even after pruning we still end up visiting a significant fraction of the leaf nodes (~30%).
    • Incrementally updating and removing items from a KD-tree is possible, but it's not clear how to keep the tree balanced. Especially since our updates are biased (the average tuple value will only ever decrease over time).
  • This answer to a similar question doesn't work either, even the dense subset of indices it still too large.

Question

Are there any possible approaches I'm missing?

$\endgroup$
1
  • 2
    $\begingroup$ Nice question! I'm not sure there is any hope. A rough rule of thumb I've heard is that once the number of dimensions exceeds 20 or 30, generally data structures like k-NN trees etc. tend to degenerate to doing a linear scan of most leaves. Maybe someone else will come up with something. $\endgroup$
    – D.W.
    Apr 9 at 4:58

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.