在进一步研究中，以下论文给出了 kD ECDF 问题的有效算法：

本特利，JL（1980 年）。多维分而治之。ACM 通讯，23(4), 214-229。

引入的主要数据结构称为范围树，有点类似于kd 树，但使用空间换时间的权衡来实现更快的范围查询。上述论文的作者 Jon Bentley（以 Programming Pearls 闻名）是这两种数据结构的发明者。

两者都是递归划分一组的二叉树$k$通过沿中值处的坐标轴分割来获得维度点。在 kd 树中，节点的子树沿$d$-th 维，其中$d$循环通过$1\ldots k$沿着树向下移动。在范围树中，子树总是沿第一维拆分，但每个节点都增加了一个$k-1$在剩余维度上定义的维度范围树。

在撰写本文时，上面链接的“范围树”的 Wikipedia 页面指向 CS 讲座（Utrecht U.）比较了大约 2012 年的这两种树类型。这表明这些数据结构本质上仍然是“最先进的” ”。提到了范围树的改进“分数级联”变体，但对于所有点 ECDF 问题，这仅允许通过范围树的重复查询来实现 Bentley 算法的性能。

我不确定是否有更有效的方法来计算数据点的 ECDF ，但以下蛮力方法对于在数据“网格”上计算 ECDF 应该是有效的。它是一维版本的简单概括。

假设您有一个数据集，包括$N$点在$d$尺寸，在给出$N\times d$矩阵$X$. 为简单起见，我假设$X$完全由唯一的数字组成（即一般位置*）。我将在下面的伪代码中使用Matlab表示法，因为这是我对算法的看法，但如果有兴趣，我可以对此进行扩展。

首次计算

$[x_{:,k},I_{:,k}]=\text{sort}[X_{:,k}]$为了$k=1:d$,

在哪里$I$是坐标秩矩阵，并且$x$是坐标网格轴矩阵（大小$N\times d$）。

然后将数据点栅格化到隐含的数据网格中，计算（标准化）直方图为 $P=\text{accumarray}[I,\frac{1}{N},N\times\text{ones[1,d]}]$.

然后将这个“EPDF”整合到每个维度中，得到 ECDF： $P=\text{cumsum}[P,k]$为了$k=1:d$.

现在$P_{i_1,\ldots,i_d}$是采样的 ECDF$x_{i_1,1},\ldots x_{i_d,d}$.

这个算法需要时间$\text{O}[N\log N]$对于每种排序和$\text{O}[N^d]$对于每个总和，所以总成本是$\text{O}[d(N^d+N\log N)]$. 由于网格化 ECDF 本身具有$\text{O}[N^d]$元素，这应该基本上是最优的。

(*不同点的假设可以通过使用来放宽$\text{unique}[]$代替$\text{sort}[]$，以及一些簿记。）