TRAKNN: Efficient Trajectory Aware Spatiotemporal kNN for Rare Meteorological Trajectory Detection

Imagine you are trying to find the most unusual weather patterns in Europe over the last 75 years.

Usually, meteorologists look at the weather like a photograph. They take a snapshot of the sky on a single day and ask, "Is this day weird?" But extreme weather—like a massive storm or a heatwave—isn't a single photo; it's a movie. It's a sequence of events that plays out over several days. A storm doesn't just appear; it builds, moves, and fades.

The problem is that looking at millions of "movies" (sequences of days) to find the rarest ones is like trying to find a specific needle in a haystack the size of a mountain, but you have to compare every single needle to every other needle. Doing this with standard computers usually takes forever or requires supercomputers.

Enter TRAKNN. Think of it as a super-smart, high-speed librarian that can scan 75 years of weather movies in minutes on a regular laptop.

Here is how it works, broken down with simple analogies:

1. The "Sliding Window" Trick (The Movie vs. The Photo)

Most weather studies look at one day at a time. TRAKNN looks at chunks of time.

The Analogy: Imagine you are watching a movie. Instead of freezing the frame at 2:00 PM, you watch a 5-minute clip. TRAKNN slides this 5-minute "clip" across the entire 75-year history of weather data.
The Goal: It asks, "Has this specific 5-day weather movie ever happened before?" If the answer is "No, this exact sequence has never occurred," it's a rare trajectory.

2. The "Math Magic" (Why it's so fast)

Normally, comparing two 5-day weather movies is hard because you have to check Day 1 vs. Day 1, Day 2 vs. Day 2, etc. If you have 27,000 days of data, the number of comparisons is astronomical.

TRAKNN uses a clever shortcut called Recurrence.

The Analogy: Imagine you are comparing two long lines of people.
- The Old Way: You compare Person A to Person B, then A+1 to B+1, then A+2 to B+2... all the way down the line. If the line gets longer, you do more work.
- The TRAKNN Way: You realize that if you already compared the first 4 people, you only need to check the new person entering the line and the old person leaving it.
The Result: Whether the weather movie is 1 day long or 100 days long, the computer does roughly the same amount of work. This is why it can run on a standard laptop instead of a supercomputer.

3. The "Rarity Score"

Once TRAKNN has compared every weather movie to every other one, it gives each day a Rarity Score.

The Analogy: Think of a crowded party. If you walk in and everyone looks exactly like you (same clothes, same haircut), you are common. But if you walk in and no one looks like you, you are rare.
TRAKNN calculates how "far away" a specific weather pattern is from all other patterns in history. The further away it is, the higher the score.

4. Did it work? (The Real-World Test)

The authors tested this on European sea-level pressure data (basically, how heavy the air is pressing down, which drives wind and storms).

The Result: The "rarest" movies TRAKNN found weren't just random noise. They turned out to be real, massive storms.
The "Cluster" Discovery: When they grouped the rarest events together, they found distinct "personality types" of storms:
- Type A: High pressure in the north, low in the south.
- Type B: The exact opposite.
- Type C: A giant low-pressure system covering all of Europe.
The Match: These rare patterns matched up perfectly with historical records of actual windstorms and disasters.

Why does this matter?

No Supercomputers Needed: You don't need a billion-dollar machine to study climate change; you can do it on a standard office laptop.
No Pre-Set Rules: The computer doesn't need to be told what a "storm" looks like. It just finds what is statistically weird, which is great because climate change might create weird new patterns we haven't seen before.
Better Predictions: By understanding the "movies" of the past, we can better understand the "movies" of the future.

In a nutshell: TRAKNN is a tool that turns the weather from a stack of photos into a library of movies, then uses a mathematical shortcut to instantly find the most unique, never-before-seen stories in that library. It helps us understand the "rare" weather events that cause the most damage.

1. Problem Statement

The paper addresses the challenge of detecting rare atmospheric trajectories in large-scale, multi-decadal spatio-temporal datasets (e.g., daily sea-level pressure maps over Europe spanning 75 years).

The Gap: Traditional climate studies often focus on instantaneous atmospheric states (single snapshots). However, extreme weather events (windstorms, heatwaves) are processes that evolve over several days. Capturing the temporal evolution (trajectory) of spatial fields is crucial for characterizing these events.
The Challenge: Performing an exhaustive, exact similarity search (k-Nearest Neighbors or kNN) on continental-scale datasets with tens of thousands of time steps and high spatial resolution is computationally prohibitive.
- Standard approaches suffer from quadratic scaling ( $O(n^2)$ ) in the number of time steps.
- Existing libraries (like FAISS) often rely on approximate indexing or specialized hardware, failing to exploit the temporal overlap inherent in sliding-window trajectory construction, leading to redundant computations and high memory usage.
Goal: Develop a fully unsupervised, data-agnostic framework that enables exact geometric rarity detection of short trajectories on standard workstations (CPU/GPU) without prohibitive memory requirements.

2. Methodology: TRAKNN

The authors propose TRAKNN (TRajectory Aware KNN), a framework that decouples computational complexity from trajectory length using a recurrence-based approach.

A. Problem Formulation

Data: A sequence of spatial fields $X = \{X_1, \dots, X_n\}$ , where each $X_t$ is a matrix of size $h \times w$ .
Trajectory: A trajectory $T^{(d)}_t$ of duration $d$ is a sequence of $d$ consecutive fields: $(X_t, \dots, X_{t+d-1})$ .
Distance Metric: The squared Euclidean distance (Frobenius norm) between two trajectories is the sum of squared differences of their constituent spatial fields.
Rarity Score: A trajectory is considered rare if its average distance to its $k$ -nearest neighbors (excluding overlapping time windows) is high.

B. Algorithmic Innovations

The algorithm consists of two main optimized stages:

Efficient Spatial Distance Computation (Batched GeMM):
- Instead of computing pairwise distances naively, the algorithm precomputes the squared norms of all spatial fields.
- It reformulates the distance calculation $\|X_i - X_j\|^2 = \|X_i\|^2 + \|X_j\|^2 - 2\langle X_i, X_j \rangle$ as a Batched General Matrix-Matrix Multiplication (GeMM).
- By exploiting symmetry ( $S_{i,j} = S_{j,i}$ ), it computes only the upper triangular batches, maximizing FLOP utilization on modern hardware (CPU/GPU).
Constant-Time Trajectory Distance Recurrence:
- This is the core innovation. Consecutive trajectories $T^{(d)}_i$ and $T^{(d)}_{i-1}$ share $d-1$ spatial fields.
- The distance between two trajectories can be updated in $O(1)$ time using a recurrence relation:
  $D(T^{(d)}_i, T^{(d)}_j) = D(T^{(d)}_{i-1}, T^{(d)}_{j-1}) - S_{i-1, j-1} + S_{i+d-1, j+d-1}$
- This eliminates the need to re-sum distances for every trajectory, making the cost of computing all trajectory distances independent of the trajectory length $d$ .

C. Complexity Analysis

Time Complexity: Dominated by the initial spatial distance matrix calculation, scaling as $O(hw \cdot n^2)$ . The trajectory distance computation itself is $O(n^2)$ , independent of $d$ .
Memory Complexity: Requires storing the $n \times n$ spatial distance matrix and the data itself, scaling as $O(\max(hw, n) \cdot n)$ .
Hardware: Designed to run efficiently on standard laptops/workstations with 32GB RAM and consumer-grade GPUs (e.g., NVIDIA RTX).

3. Key Contributions

Unsupervised Framework: A generic method for detecting geometrically rare trajectories in gridded spatio-temporal data, independent of specific physical variables.
Exact Recurrence Algorithm: Derivation of an exact algorithm that makes computational cost independent of trajectory duration, enabling exhaustive analysis.
Scalability: Implementation of CPU and CPU+GPU versions that allow multi-decadal analysis on standard hardware, outperforming state-of-the-art libraries like FAISS in memory efficiency for long trajectories.
Validation: Demonstration on 75 years of European sea-level pressure (SLP) data, proving that detected rare trajectories correspond to physically coherent anomalies and known extreme events.

4. Experimental Results

A. Performance Evaluation

Scalability: TRAKNN maintains nearly constant computation time as trajectory length ( $d$ ) increases, whereas FAISS (a standard similarity search library) sees linear memory growth and fails to scale to longer trajectories on standard hardware.
Memory Efficiency: For a 75-year dataset ( $n \approx 27,000$ ) with trajectory length $d=2$ , FAISS required >20GB RAM (failing on 8GB GPUs), while TRAKNN used only 6GB regardless of $d$ .
Speed: On CPU, TRAKNN slightly outperformed FAISS; on GPU, it matched FAISS for $d=1$ but remained efficient for larger $d$ .

B. Case Study: European Sea-Level Pressure (1950–2025)

Intrinsic Dimensionality: Analysis showed that despite high ambient dimensions (~50,000 grid points), the intrinsic dimensionality of the trajectory space is very low (saturation at ~18–21 for $d \ge 5$ ). This validates the use of Euclidean distance in this high-dimensional space.
Dimensionality Reduction: Applying PCA (reducing dimensions from 50k to ~33) yielded nearly identical rankings of rare trajectories (Spearman correlation 0.99), confirming that raw Euclidean distance is sufficient and robust.
Composite Analysis: The top 100 rare trajectories were clustered into three distinct, physically coherent regimes:
1. High pressure over Northern Europe / Low pressure in the South.
2. The inverse pattern (Low North / High South).
3. A large low-pressure regime covering most of Europe.
  These correspond to known large-scale circulation patterns, not random noise.
Extreme Event Matching:
- The method successfully identified dates associated with extreme windstorms from independent databases (XWS, CLIMK-WINDS, EM-DAT).
- Trajectory Length Impact: Longer trajectories ( $d=5, 7$ ) significantly improved the detection of winter windstorms (which evolve over days), whereas $d=1$ was better suited for instantaneous temperature extremes.
- Significance: The detection rate for meteorological storms was significantly higher than random chance (e.g., 12/100 hits vs. 0.7 expected for random).

5. Significance and Conclusion

Paradigm Shift: TRAKNN shifts the focus from static "snapshots" to dynamic "trajectories," allowing for a more accurate characterization of extreme weather evolution.
Accessibility: By enabling exact, exhaustive searches on standard hardware, the method democratizes high-resolution climate analysis, removing the need for supercomputing resources or approximate heuristics.
Interpretability: The approach is fully data-driven and unsupervised, yet the results align strongly with physical mechanisms and historical extreme event records.
Future Work: The authors suggest extending the method to out-of-core computation for even larger datasets and integrating trajectory-based analogues into flow-analogue analysis for climate attribution.

In summary, TRAKNN provides a mathematically rigorous and computationally efficient solution to a long-standing bottleneck in climate science: the ability to systematically find rare, multi-day atmospheric patterns in massive datasets without sacrificing exactness or requiring specialized infrastructure.