algorithm - 从大表中消除 "bad"项目的多维过滤器？

Question

我有一个包含 N 个项目的大表，每个项目有 M (M>=3) 个不同的属性， 我必须从这个表中删除所有项目，因为同一个表包含一个在所有属性上得分相等或更好的项目。

我有一个 algorithm (python)已经解决了它，但它对输出敏感并且最坏情况约为。 O((n²+n)/2) 当没有项目被移除时。 这对我的项目来说太慢了(其中 100,000 个项目的数据集，每个项目有 8 个属性并不少见)，所以我需要接近 O(m*n log n) 最坏情况的东西，但我不知道这个问题是否可以这么快就解决了。

示例问题案例及其解决方案:

  [higher value = better]
    Singing  Dancing  Acting
 A    10        20     10
 B    10        20     30
 C    30        20     10
 D    30        10     30
 E    10        30     20
 F    30        10     20
 G    20        30     10

解雇所有表现与候选人相同或相同的候选人 在所有学科中都做得更好。

解决方法:
- A 被解雇，因为 B、C、E、G 在所有学科中的表现均等或更好。
- F 被解雇，因为 D 在所有学科中的表现均等或更好。

是否存在有效解决该问题的算法，它是什么？

Answer 1

一般的答案是将记录排列成一棵树，并在每个节点处记录位于该节点下的记录的每列中的最大值。然后，对于每条记录，从树的顶部向下追逐它，直到您知道它是否被支配，如果可能的话，使用每个节点处的注释跳过整个子树。 (不幸的是，您可能必须搜索一个节点的两个后代)。当您删除一条记录作为主导时，您可能能够更新其上方节点中的注释 - 因为这不需要涉及重新平衡树，所以它应该很便宜。您可能希望至少获得比原始代码更快的速度。如果我对多维搜索的内存是正确的，您可能希望从 N^2 到 N^(2-f)，其中 f 随着维数的增加而变小。

创建这种树的一种方法是在一个维度的中值处重复拆分记录组，循环遍历每个树级别的维度。如果您对每个这样的拆分使用类似快速排序的中值搜索，您可能希望树构造花费您 n log n 的时间。 (kd树)

对此的一个调整因素不是一直向下 split ，而是在组大小达到某个 N 或更少时停止 split 。