标题： 子树模式和应用 显示英文标题

标题： Subtree Mode and Applications

摘要： 集合中值的众数（即集合中最常见的值）是一个关键的汇总统计量。因此，在一个值数组的给定范围内找到众数非常重要，构建一个解决这个问题的数据结构实际上是著名的范围众数问题。在本工作中，我们引入了子树众数（SM）问题，这是在叶色树中的类似问题，其中任务是计算给定节点的子树中叶节点的最常见颜色。SM受到文本分析和生物学等领域中多个应用的驱动，其中数据是分层的，因此可以表示为（叶色）树。我们的主要贡献是一个针对SM的时间最优算法，该算法在$N$节点树上以$O(N)$时间计算输入树每个节点的答案。我们进一步展示了如何将我们的解决方案适应于节点颜色树，或计算$k$最常见的颜色，在最优$O(N)$时间内，对于任何给定的$k=O(1)$。此外，我们证明了当输入是一个源色有向无环图而不是叶色树时，得到类似快速解决方案的可能性非常低。我们在包含最多73亿个节点的树的真实数据集上的实验表明，我们的算法比基线方法快至少一个数量级，并且更加节省空间。最后，我们展示了案例研究，说明了我们的方法在模式挖掘和序列到数据库搜索应用中的有效性。 显示英文摘要

摘要： The mode of a collection of values (i.e., the most frequent value in the collection) is a key summary statistic. Finding the mode in a given range of an array of values is thus of great importance, and constructing a data structure to solve this problem is in fact the well-known Range Mode problem. In this work, we introduce the Subtree Mode (SM) problem, the analogous problem in a leaf-colored tree, where the task is to compute the most frequent color in the leaves of the subtree of a given node. SM is motivated by several applications in domains such as text analytics and biology, where the data are hierarchical and can thus be represented as a (leaf-colored) tree. Our central contribution is a time-optimal algorithm for SM that computes the answer for every node of an input $N$-node tree in $O(N)$ time. We further show how our solution can be adapted for node-colored trees, or for computing the $k$ most frequent colors, in the optimal $O(N)$ time, for any given $k=O(1)$. Moreover, we prove that a similarly fast solution for when the input is a sink-colored directed acyclic graph instead of a leaf-colored tree is highly unlikely. Our experiments on real datasets with trees of up to 7.3 billion nodes demonstrate that our algorithm is faster than baselines by at least one order of magnitude and much more space efficient. Last, we present case studies showing the effectiveness of our approach in pattern mining and sequence-to-database search applications.