📊 statistics

Scalable inference of spatial regions and temporal signatures from time series

This paper proposes a scalable, nonparametric framework based on the minimum description length principle that jointly infers spatially contiguous regions and representative temporal drivers from time series data without requiring a priori constraints on the number of regions.

Original authors: Jiayu Weng, Alec Kirkley

Published 2026-05-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jiayu Weng, Alec Kirkley

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, chaotic room filled with hundreds of people, each holding a walkie-talkie. Every person is talking, but they aren't just making random noise; they are following specific scripts. Some people are reciting the same story at the same time, others are singing a different song, and some are just static.

Your goal is to figure out: Who is in which group, and what is the "main story" each group is telling?

This is exactly what the paper by Jiayu Weng and Alec Kirkley tackles, but instead of people in a room, they are looking at data points across a map (like air quality sensors or vegetation trackers) that change over time.

Here is a simple breakdown of their solution:

1. The Problem: The "Static" vs. The "Movie"

Most old ways of grouping things on a map are like looking at a single photograph. They ask, "Who looks similar right now?" If two neighbors have the same temperature today, they get grouped together.

But the real world is a movie, not a photo. Two neighbors might look different today but behave exactly the same way over the next year (e.g., both get hot in summer and cold in winter). Old methods often ignore this "movie" aspect, or they try to force groups to be neighbors even if their stories don't match. They also usually require you to guess how many groups there are before you start (e.g., "Let's find 5 groups"), which is like trying to sort a deck of cards by guessing there are exactly 4 suits before you even look at them.

2. The Solution: The "Compression" Trick

The authors use a clever idea from information theory called the Minimum Description Length (MDL) principle. Think of this as a game of compression, like turning a huge, uncompressed video file into a small MP4.

They ask: "What is the shortest way to describe all this data to a friend?"

To do this, they propose a two-part story for every group (region) they find:

The "Driver" (The Script): A single, representative time series that acts as the "main character" or the "script" for that whole region.
The "Notes" (The Differences): A short list of notes explaining how the actual people in that group deviate from the script.

If a group of sensors all follow the same pattern perfectly, you only need to send the "Driver" script once. That's a huge saving! If you have to describe every single sensor individually, the file size (the description length) stays huge.

The Magic: The computer automatically tries to find the grouping that makes the "file size" as small as possible.

If you group too many different things together, the "Notes" about their differences become huge, and the file gets big.
If you make too many tiny groups, the "Driver" scripts become too numerous, and the file gets big again.
The "sweet spot" is the perfect balance. The computer finds this sweet spot automatically, meaning you don't have to guess how many groups there are.

3. The "Neighborhood" Rule

There is one strict rule in their game: Neighbors must stay neighbors.
You can't group two sensors together just because they have similar stories if they are on opposite sides of the map. They must be physically connected, like a chain of houses.

To do this efficiently, they treat the map like a tree. Imagine a tree where every branch is a sensor. The algorithm starts with every sensor as its own tiny branch. Then, it looks at neighboring branches and asks, "If I glue these two together, does the total file size get smaller?" If yes, it glues them. It keeps doing this, merging branches into bigger and bigger clusters, until gluing them any further would make the file size worse.

4. What They Found (The Results)

They tested this on two real-world "movies":

California Air Quality: They looked at daily air pollution data. Their method found groups of cities that moved together. For example, it correctly identified a long, polluted valley (the San Joaquin Valley) as one group and coastal cities as another. It even found that these groups change shape depending on the season, something old "photo" methods miss.
Hong Kong Vegetation: They looked at plant growth data. The method separated the dense, green mountains from the concrete city centers and the small islands. It found that the "green" areas have a specific seasonal rhythm, while the "city" areas stay flat and low.

They also compared their method to a standard tool called "K-means." The standard tool often created "islands" of data—grouping a city in the north with a city in the south just because they had similar numbers, even though they weren't neighbors. The new method kept the regions contiguous (all touching), creating maps that actually look like real-world regions.

5. Why It's Fast

Usually, trying to find the perfect group for thousands of data points takes forever (like trying to solve a puzzle by trying every single piece in every single spot).

The authors' method is like a smart, greedy puzzle solver. It makes the best local move at every step. Because of the way they built the math (using that "tree" structure), it can handle hundreds of thousands of data points very quickly. It's fast enough to run on a standard laptop, even for massive datasets.

Summary

In short, this paper gives us a new, automatic way to draw maps based on how things change over time, not just how they look right now. It finds natural "neighborhoods" where the "stories" (time series) are similar, creates a simple "script" (driver) for each neighborhood, and does it all without needing a human to guess how many neighborhoods exist. It turns a messy, complex dataset into a clean, compressed, and understandable map.

Problem Statement
Regionalization, the task of partitioning a spatial domain into geographically contiguous regions with similar characteristics, is a fundamental tool for spatial analysis, policy-making, and resource management. However, existing approaches face significant limitations when applied to modern spatiotemporal datasets. Traditional regionalization methods typically rely on static spatial snapshots or time-aggregated variables, failing to capture the temporal dimension inherent in data such as air quality monitoring, vegetation indices, and climate records. Conversely, standard time series clustering methods often ignore spatial structure or enforce spatial continuity through ad hoc regularization terms that require tuning hyperparameters. Furthermore, most existing methods require the number of regions to be specified a priori, a constraint that can introduce bias, obscure heterogeneity at small scales, or create spurious structures in noisy data. There is a need for a principled, scalable, and fully nonparametric framework that can simultaneously infer spatial partitions and representative temporal patterns from evolving time series without requiring user-specified parameters.

Methodology
The authors propose a fully nonparametric framework for the regionalization of spatial time series based on the Minimum Description Length (MDL) principle. The core objective is to find a spatial partition and a set of representative "driver" time series that jointly minimize the total description length (codelength) required to encode the dataset.

Formulation: The problem is modeled as an information compression task. The dataset consists of $N$ spatial locations (nodes in an adjacency graph $G$ ) with univariate time series of length $T$ . The data is first discretized into a categorical matrix $Z$ . The total description length $L(Z, C)$ for a partition $C$ is decomposed into:
1. Partition Structure Cost: The cost to transmit the spatial partition, modeled by specifying a spanning tree of the adjacency graph and a cut of that tree to define contiguous clusters.
2. Driver Cost: The cost to transmit the representative driver time series for each cluster.
3. Conditional Encoding Cost: The cost to transmit the member time series within each cluster, conditioned on their respective driver. This utilizes contingency tables to capture the joint distribution between the driver and member series, effectively measuring conditional entropy.
Optimization: Direct minimization over all possible contiguous partitions is computationally intractable. The authors employ a greedy agglomerative merging strategy. Starting with $N$ singleton clusters, the algorithm iteratively merges adjacent regions that yield the largest reduction (or smallest increase) in the total description length.
- Driver Estimation: For any given cluster, the optimal driver is determined via a majority vote estimator, which assigns the most frequent symbol at each time step among the cluster's member series.
- Model Selection: The number of clusters $D$ is not fixed. The algorithm generates a full merge trajectory from $N$ clusters down to 1. The optimal solution is selected as the partition along this trajectory that achieves the minimum description length.
Complexity: The algorithm utilizes a priority queue to manage merge candidates, resulting in a runtime complexity of $O(TN \log N)$ , where $T$ is the time series length and $N$ is the number of spatial nodes. This log-linear scaling allows the method to handle hundreds of thousands of time series efficiently.

Key Contributions

Principled Nonparametric Framework: The method derives regionalization directly from the MDL principle, balancing model complexity against goodness-of-fit without requiring application-specific hyperparameter tuning (e.g., distance thresholds or fixed cluster counts).
Joint Inference: It simultaneously infers spatially contiguous regions and their representative temporal "drivers," allowing interpretable temporal patterns to emerge directly from the data.
Scalability: The proposed agglomerative algorithm is highly efficient, scaling log-linearly with the number of spatial units, making it suitable for large-scale empirical datasets.
Handling of Temporal Dynamics: Unlike static regionalization, this approach captures functional similarity based on shared temporal trajectories, seasonal cycles, and dynamical responses.

Results
The framework was evaluated on both synthetic and real-world datasets:

Synthetic Data: Experiments with planted regional structures demonstrated that the method accurately recovers underlying spatial clusters and driver patterns across a wide range of noise levels, numbers of nodes, and discrete state sizes. The adjusted mutual information (AMI) remained high until noise levels dominated the signal, and the MDL compression ratio closely tracked the recovery accuracy.
Case Study 1: California Air Quality (AQI): Applied to daily AQI categories across 192 monitoring stations in California (2024), the method identified 7 spatially contiguous regions. The resulting clusters aligned with known topographic features (e.g., coastal corridors, inland valleys) and established air-quality basins (e.g., South Coast Air Basin, San Joaquin Valley). The inferred drivers captured distinct seasonal pollution patterns, such as higher summer ozone levels in inland basins. Compared to K-means clustering, the MDL approach produced more coherent, contiguous regions without fragmented or interleaved assignments.
Case Study 2: Hong Kong Vegetation (NDVI): Applied to 16-day NDVI time series (2020–2022) across 939 locations in Hong Kong, the method identified 10 regions. These regions corresponded to distinct land-use and land-form structures, including urban cores (low NDVI), major country parks and mountainous areas (high NDVI), and transitional peri-urban zones. The method successfully handled continuous data by discretizing it, showing stability in results across different discretization resolutions ( $S$ ).
Scalability: Additional tests on NDVI data for Guangdong Province and mainland China (approx. 50,000 sites) confirmed the method's ability to scale to national levels while maintaining interpretability and spatial contiguity.

Significance and Claims
The paper claims that this work provides a principled and scalable framework for spatially contiguous partitioning that overcomes the limitations of existing static or ad hoc methods. By leveraging the MDL principle, the method allows interpretable temporal patterns and homogeneous regions to emerge directly from the data itself, eliminating the need for user-specified hyperparameters regarding the number of regions or the strength of spatial coupling. The authors assert that their approach offers a rigorous basis for data summarization and cross-dataset comparisons, as it is derived from fundamental information-theoretic principles rather than heuristic definitions of distance or density. The successful application to diverse environmental datasets (discrete AQI and continuous NDVI) demonstrates the framework's versatility in extracting meaningful spatiotemporal structure from both categorical and continuous time series.