计算机学院系列讲座菁英论坛第49期——Subtree mode and applications

报告题目(Title)：Subtree mode and applications

时间(Date & Time)：2026.4.8; 10:00-11:30 am

地点(Location)：理科二号楼2736（燕园校区）#腾讯会议：796-292-597

主讲人(Speaker)：Grigorios Loukides

邀请人(Host)：Yinjun Wu （吴垠鋆）

报告摘要(Abstract)：

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, for any given k =O(1), in the optimal O(N) time. 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. They also show that it is effective in pattern mining, sequence-to-database search, and two biological applications, namely viral sequence classification and phylogenetic tree annotation.

This work is to appear in IEEE ICDE 2026 and its pre-print version can be found at: https://arxiv.org/pdf/2511.01376.

主讲人简介(Bio)：

Grigorios Loukides is an Associate Professor at the Department of Informatics, King's College London. His research interests are on data management and mining with a focus on algorithms. His work has investigated several problems on complex data such as graphs, time-series, and strings. He has published more than 150 papers in prestigious venues such as PVLDB, ICDE, TKDE, and KDD. 

欢迎关注计算机学院微信公众号，了解更多讲座信息！

北京大学计算机学院