CS Paper Radar

CT-Miner: Fast and Coarse-Grained Time-Series Pattern Mining via Cartesian Trees

Hyundong Jin, Hyunki Hong, Yo-Sub Han

cs.DS cs.LG ·submitted 2026-10-04 15:53 UTC · v1
code/data

Abstract

Time series often contain recurring structural patterns, and efficiently mining such patterns into compact representations is essential for scalable analysis of long sequences. Cartesian tree (CT) equivalence provides a well-established structural abstraction that preserves hierarchical order structure while discarding exact values and fine-grained ordinal variations. By grouping multiple ordinal patterns into a shared structural form, CT equivalence offers a principled way to compress recurring temporal structure. However, mining frequent CT-equivalent patterns at scale remains computationally expensive. A naive pairwise approach repeatedly constructs and counts CT representations over subsequences, requiring $O(n^4)$ time for a sequence of length $n$, which severely limits its applicability to long sequences. We propose a new Cartesian pattern mining algorithm based on a Cartesian suffix tree that compactly organizes CT-equivalent subsequences and reuses shared structural information. Our method reduces exhaustive CT-pattern occurrence collection from $O(n^4)$ to $O(n^2)$ time, and we formally prove the correctness and complexity bounds. We further show that this computational gain translates into effective compact representations. Across diverse time-series datasets, a small set of mined CT patterns preserves meaningful clustering structure, and comparisons with finer-grained order-preserving representations show that CT equivalence reduces redundant ordinal distinctions under limited feature budgets. Our implementation is available at https://github.com/hyundong98/CT-Miner .

Closest papers

Nearest neighbours by meaning across the whole index.

Inductive Process Discovery from Partially Ordered Event Data

cs.DB ·2026-08-20 ·Humam Kourani, Tom Breuer, Gyunam Park, Wil M. P. van der Aalst
similarity 0.62
Abstract

The Inductive Miner (IM) family is a prominent class of process discovery techniques, combining efficient recursive decomposition with soundness-by-construction guarantees. However, IM techniques usually assume traces to be totally ordered sequences of activity occurrences. This assumption is convenient, but can introduce systematic bias: activities may have durations, events may share coarse timestamps, or the data may constrain only some event pairs. Forcing such executions into arbitrary sequences hides inherent concurrency and may introduce sequential dependencies that were never observed as causal constraints. Partial orders provide a more faithful representation, but integrating them into IM discovery is challenging because standard abstractions are sequence-based; directly reusing them would require linearizing each partial order, which becomes prohibitively expensive under high concurrency. We introduce a lifting of IM discovery from total orders to partially ordered traces. Instead of redesigning the miner and its cut detection logic, we redefine the trace abstraction layer and the recursive projections to operate directly on partial orders. The approach is conservative over totally ordered traces, avoids linearization explosion, and preserves the recursive structure and guarantees that make IM attractive. Experimental results show that the proposed lifting avoids the combinatorial overhead of linearization, reduces sensitivity to arbitrary tie-breaking in timestamped event data, and allows process behavior to be learned from fewer observations by preserving concurrency at the trace level.

0.17

Rondo: Unsupervised Discovery of Recurring Temporal Structure

cs.LG cs.AI ·2026-09-26 ·Yingtian Shi, Ankith Chandra, Thomas Plötz
similarity 0.60
Abstract

Many real-world time series data exhibit structural properties at multiple scales, from short, recurring units to complex sequences composed of these units. Unsupervised discovery of both these components and structure enables the design of intelligent systems that help interpret temporal data, thereby limiting the amount of costly human annotations required. Existing modeling approaches typically overlook the hierarchical structure inherent to many time series, treating recurring patterns at different temporal scales as independent structures. Moreover, most assume access to the complete data sequence and treat discovery as a static process, limiting their ability to evolve as new observations arrive. We introduce Rondo, an unsupervised approach for modeling recurring hierarchical structure in continuous temporal streams. By explicitly constructing vocabularies of reusable units and their recurring compositions, Rondo captures structure shared across complex temporal patterns while refining and expanding its discoveries as the stream evolves. Evaluations on temporal sequences spanning diverse domains and data modalities show that Rondo outperforms existing unsupervised recurrence-discovery baselines, with particularly pronounced advantages in limited-data and continual-stream settings. These capabilities provide a stronger foundation for recurring-pattern discovery, scalable behavior understanding, and adaptive intelligent systems operating on long, unlabeled temporal streams.

0.24

Real-Time String Indexing in Optimal Time

cs.DS ·2026-11-10 ·Gregory Kucherov, Yakov Nekrich
similarity 0.58
Abstract · 30 pages, 7 figures

In this paper we describe the first fully real-time indexing solution for pattern matching over an arbitrary integer alphabet. Our data structure spends $O(1)$ worst-case time w.h.p. for processing each new letter appended to $T$ and worst-case $O(|P|+occ)$ time for reporting all occurrences of $P$, where $T$ and $P$ are strings over an integer alphabet. The main idea of our solution is a novel representation of the suffix tree, the path-decomposed suffix tree, which does not store the full topology of the suffix tree but instead decomposes it into paths, each stored in a dictionary that encodes parent--child relationships indirectly.

0.39

Motifs in temporal hypergraphs

cs.SI cs.DSphysics.soc-ph ·2026-09-10 ·Quintino Francesco Lotito, Lorenzo Betti, Federico Battiston, Giuseppe Francesco Italiano
similarity 0.58
Abstract

Network motifs, recurrent local patterns of interactions in graphs, provide fundamental insights on the interplay between structure and functionality in complex systems. Many real-world systems are not well represented by traditional static pairwise networks, as interactions may involve groups of nodes, occur over time, or encode directionality. In this paper, we introduce temporal motifs for hypergraphs and directed hypergraphs, extending motif analysis to timestamped many-body interactions. We formalize the corresponding mining problem, study the combinatorial structure of these motifs, and develop exact algorithms for their enumeration. In particular, we propose a dynamic programming algorithm that substantially reduces the computational cost of motif mining, achieving orders of magnitude speedups on empirical datasets. We also introduce a null model for temporal hypergraphs to assess the statistical over- and under-expression of motifs. Applying the proposed framework to real-world datasets from different domains, including face-to-face contacts, scientific collaborations, e-mail exchanges, and Bitcoin transactions, we show that temporal hypergraph motifs reveal distinct forms of local organization across systems. Finally, we demonstrate their use as an exploratory tool through focused case studies on persistent patterns in scientific collaborations and e-mail communications.

0.22

Optimal Pattern-Avoidance Bounds for Binary Search Trees

cs.DS ·2026-11-15 ·Anita Dürr, Arturo Merino, Karol Węgrzycki, Sorrachai Yingchareonthawornchai
theorycode/datahot direction similarity 0.57
Abstract · 37 pages. Submitted to STOC 2027. Publicly available at https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/906.pdf

Self-adjusting binary search trees (BSTs) perform better than balanced BSTs if the access sequence has additional structure. For example, splay trees serve a sequential access sequence in linear time. Pattern avoidance captures regularity in an access sequence and unifies several classic examples of efficient BST access, such as deque and traversal sequences. A central question is how well a BST algorithm can exploit a pattern-avoiding access sequence. We present an online BST algorithm that serves an access sequence avoiding a permutation pattern $π$ in linear time, matching the information-theoretic lower bound. The algorithm does not need to know that pattern $π$ a priori. Our results answer an open problem asked by [Kozma 2016, Problem 44, strong variant]. Previously, the best known offline bound was optimal only for constant-size patterns [Berendsohn, Kozma, and Opler, STOC'24], and the best known online bound was superlinear [Chalermsook, Pettie, Yingchareonthawornchai, SODA'24] even for a constant-size pattern. As a corollary, our BST algorithm yields an optimal sorting algorithm for a pattern-avoiding sequence that supports online insertions. Previously, an optimal sorting algorithm was achieved using a mergesort-like approach [Opler, FOCS'24] in a batch setting. A key technique is to apply recursive split decomposition [Chalermsook, Chuzhoy, Saranurak, ToC'23] jointly in time and space, along with the Marcus-Tardos proof of the Stanley-Wilf conjecture. We show that the framework can be implemented online using $k$-finger BSTs, which is of independent interest. Finally, this framework also yields a constant-factor-approximation FPT algorithm in the offline setting.

0.41

Stringological sequence prediction III: layered ziplines and a tradeoff between efficiency and expressivity

cs.FL cs.DScs.LG ·2026-09-17 ·Vanessa Kosoy
similarity 0.56
Abstract

In previous papers, we began the study of sequence prediction algorithms adapted to stringological word complexity measures. In particular, we defined a complexity measure called Arithmetic Repetition Complexity (ARC) which admits a polynomial-time prediction algorithm with a mistake bound quasilinear in the complexity. Here, we show a weaker complexity measure related to ARC that admits an especially efficient prediction algorithm: an algorithm that runs in quasilinear time and polylog space for appropriate highly-structured sequences. The complexity measure is defined via a restricted class of "zipline programs" (a variant of straight-line programs), which we call layered. We thus get a less expressive measure with a more efficient algorithm (compared to our results for ARC), demonstrating a possible tradeoff.

0.47

Parallel Algorithms for Higher-Order Temporal H-Index Computation

cs.DS ·2026-11-06 ·Lutz Oettershagen
similarity 0.55
Abstract

Ranking vertices by importance is a fundamental task in network mining. The H-index provides such a ranking by asking how many neighbors are themselves well connected; its higher-order temporal variant recursively applies this idea over time-respecting neighborhoods in temporal networks. Scaling its computation is difficult because the existing streaming algorithm intertwines temporal processing with H-index order, incurring maximum-degree-dependent costs and exposing little parallelism. We show that the temporal dependencies can instead be resolved once: each edge's time-dependent lookup is mapped to a fixed successor position, turning every H-index order into a parallel gather followed by a segmented suffix-H computation. Based on this reformulation, we derive a linear-work suffix-H algorithm, a parallel multicore CPU implementation, degree-adaptive GPU kernels, and a multi-GPU scheme that exchanges only distinct remotely queried states. Experiments on synthetic and real-world temporal graphs show that the reformulation alone is substantially faster than the streaming algorithm, and that GPUs add order-round speedups exceeding an order of magnitude over our multicore implementation on synthetic inputs with up to one billion temporal edges. On a 636M-edge Reddit network, eight GPUs compute 128 orders in 3.6 s of round time, whereas the streaming algorithm does not finish within an hour even at order 8.

0.30

The Inverse Lyndon Array

cs.DS cs.FL ·2026-09-20 ·Clelia De Felice, Pietro Negri, Manuel Sica, Rocco Zaccagnino, Rosalba Zizza
theory similarity 0.55
Abstract · 21 pages, no figures, SOFSEM conference

The Lyndon array stores, at each position of a word, the length of the longest Lyndon factor starting at that position and plays an important role in combinatorics on words, for example, in the construction of fundamental data structures such as the suffix array. In this paper, we introduce the Inverse Lyndon array, the analogous structure for inverse Lyndon words, namely words that are lexicographically greater than all their proper nonempty suffixes. Unlike standard Lyndon words, inverse Lyndon words may have non-trivial borders, which introduces a genuine theoretical difficulty. We show that the Inverse Lyndon array can be characterized in terms of the next greater suffix array together with a border-correction term, and we prove that this correction coincides with a longest common extension (LCE) value. Building on this characterization, we adapt the nearest-suffix framework underlying Ellert's linear-time construction of the Lyndon array to the inverse setting, obtaining an O(n)-time algorithm for general ordered alphabets. Finally, we show that the Inverse Lyndon array can also be used to reconstruct the canonical inverse Lyndon factorization in linear time.

0.27