一种高效的分位数算法/数据结构，允许对随着时间不断增加的样本进行更新？

Question

我正在寻找一种高效的分位数算法，它允许样本值随时间的变化而进行“插入”或替换。

假设我有1-n项的值。我想将这些值放入一个可以高效存储它们的分位数算法中。但是在未来的某个时刻，item-i的值会增加。我想删除item-i的原始值并替换为更新后的值。具体用例是用于流式系统，其中样本值随时间增加。

我看到最接近此类算法的是t-Digest数据结构。它可以高效地存储样本值。唯一缺少的是删除和替换样本值的能力。

我还查看了Apache Quantiles Datasketch - 它也存在相同的问题 - 没有办法删除和替换样本。

编辑：经过更深思熟虑，不一定需要删除旧值并插入递增的值。如果有一个限制只能更新值的约束条件，可能会更容易地重新计算内部状态。

- marathon

---

你好，你最终采用了什么方法？我也在寻找类似的解决方案来解决我的问题。我已经查看了OrderStatisticsTree和https://gist.github.com/robertobarreda/e4e8ee29ec36867b6452。 - Ayush Chauhan

Answer 1

如果更新时间O(log n)和分位数计算时间O(log n)对您可接受，那么解决方案之一是实现任何类型的自平衡二叉树（Splay树、AVL树、红黑树），同时在树结构的同时保留一个HashMap<Key, Node>（或者如果您知道您的键是例如数字0至n-1，则可以只使用一个数组来达到相同的目的）。您还需要为每个给定节点保留子树中节点的数量（这是所有提到的自平衡树都可以实现的——这是对所有更新节点的方法（如旋转等）的小改动）。

使用关键字K和新值V进行更新的伪代码示例：

Node node = find_node_in_hash_map_by_key(K); # O(1)
delete_node_keeping_subtree_counts_valid(node); # O(log n)
add_new_node_keeping_subtree_counts_valid(K, V); # O(log n)

由于每个节点中都包含子树的大小信息，因此获取分位数 q 也可以在 O(log n) 的时间复杂度内完成，因为它基本上通过大小访问第 i 个元素所需的时间也是 O(log n)。该操作的伪代码如下：

# i-th element requested
node = root
while true:
    left = node.left_subtree
    left_count = 0
    if left is not None:
        left_count = left.nodes_count
    if i < left_count:
        node = left # select i-th element in the left subtree
    elif i == left_count:
        return node.value # we have exactly i elements in left subtree, so i-th value is in the current node
    else:
        i -= left_count + 1 # select element i - left_count - 1 from the right subtree
        node = node.right

我不知道有什么好的开源JAVA解决方案可以用于这种数据结构，但编写自己的AVL树并不难（甚至Splay树应该是最容易的，只是它们的最坏情况复杂度不是O(log n)，但平均情况下它们应该很好）。

- Alexander Pivovarov

Answer 2

我们可以保留一个从变量名到值的映射和一个SortedMap（搜索树），其中键由值和名称组成（例如value +“_”+ name，或具有这两个字段的Comparable对象），以便排序的键也是排序的值，但我们还可以拥有唯一的键，以便能够删除旧的值+变量名并引入新的值+变量名。这是HBase中使用的一种技术，与持久TreeMap（自平衡二叉搜索树）没有太大区别。

然后计算分位数或百分位数就是扫描结构的问题。

当更新速率相对于分位数请求的低速率很高时，这是有效的。

当请求分位数的频率不是很低时，我没有什么好的想法，也许可以使用一组堆结构，这种结构也以一种使删除更有效的方式进行索引，例如 https://dev59.com/ZWoy5IYBdhLWcg3wN7UX:~:text=4%20Answers&text=Actually%2C%20you%20can%20remove%20an,parent%20of%20the%20old%20item。

- NicuMarasoiu