Mining Weather-Dependent High-Value Event Patterns from One Reusable Prefix Tree

Pattern mining finds recurring sequences of events in logs. The "high-utility" variant ranks those sequences by how much value or damage they carry instead of how often they occur. Today these miners treat value as fixed. A traffic jam near a school costs the same on a mild day as during a stagnant heat wave, and a pump trip costs the same at midnight as at peak electricity price. In physical systems, though, the consequence of an event depends on outside conditions such as weather, holidays and grid load, which forecasting researchers call exogenous variables. Analysts rarely ask one question. They ask a family of them: which event sequences matter most during heat waves, during rain, on holidays, or under this quarter's price curve.

Existing miners can answer each such question only by rebuilding their search from scratch with re-priced values. This note proposes a fix that indexes once and answers many queries. A prefix tree is a tree in which sequences sharing a beginning share a path. We store at each node of this tree a small histogram of the node's pruning bound, broken down by exogenous context bin. Any query that re-weights value by context can then compute a sound, query-specific bound at each node from that histogram, and so prune the shared tree without re-mining. The claim is that context-binned bounds turn exogenous-conditioned utility mining from a re-run-per-question workload into an index-then-query workload. The proposal also tests empirically whether the patterns this exposes differ from frequent and globally high-value ones.

Where the directions stand and what is actually missing

Three lines of work meet here. On the tree side, prefix sharing compresses set and sequence collections to roughly one sixth of a list representation (Hoffmann et al.), and lets a whole subtree be discarded once its prefix fails a test. RASP extends this to prefix-tree forests that tolerate jitter in event timing and adapt to a memory budget. It runs on precipitation and traffic data, but it counts frequencies, and it treats weather only as more event tokens.

On the utility side, value is non-monotone: a cheap item can join a pattern whose total value is large. Search therefore relies on upper bounds that overestimate the value of any extension of a prefix. Three miners supply these bounds and are the ones we reuse. HUSP-SP introduces the Tighter Reduced Sequence Utility (TRSU) bound with early pruning. UMEpi introduces the Episode-Weighted Utilization bound for episodes, meaning event sequences with simultaneous events, inside a maximum time window. SUMU supplies occupancy-based bounds. All three compute value from static, in-database quantities. UMEpi and HUSP-SP both list evolving valuations as open. The nearest relative to context-dependent value is on-shelf utility mining (Chunkai Zhang et al.), which normalizes value by an item's active selling period. That is a time-based correction, not one driven by outside conditions.

On the exogenous side, ST-ResNet and ExoST show that weather and calendar signals matter and need dedicated handling. Both are neural regressors, however, and produce no symbolic patterns. STRAP keeps a memory of historical patterns but retrieves them with flat nearest-neighbour search and no notion of value.

One point must be conceded up front, because it shapes the whole proposal. Quantitative utility miners such as HUSP-SP already accept a different value for every occurrence. If the analyst has a single, known pricing of events by context, they can compute those per-occurrence values in advance and run HUSP-SP unchanged. Putting exogenous context into a single mining run is therefore not, by itself, a research contribution. The open problem is the query family. Each new regime or pricing function invalidates the precomputed values and every bound derived from them. No existing structure shares work across those queries. A miner that keeps one fixed tree (see Targeted Mining Precise-positioning Episode Rules) does reduce 565,000 rules to 11 on BIKE. But it restricts which patterns are returned, not how events are priced, and it uses frequency rather than value.

Core Claim

We assume each sequence $s$ (for example, one day of events across a city's sensors) carries one exogenous context value $x_s$, such as that day's maximum temperature or a holiday flag. We also assume a query is a weight function $w$ that re-prices every event in $s$ by $w(x_s)$. A regime restriction like "heat-wave days only" is the special case where $w$ is an indicator.

We split the range of $x$ into $B$ bins and store at each tree node for pattern $P$ the histogram $H_P(b)$. This is the sum, over sequences containing $P$ whose context falls in bin $b$, of the HUSP-SP bound $\mathrm{TRSU}_s(P)$. For any query $w$ we use

$$\mathrm{UB}_w(P)=\sum_{b=1}^{B}\bar w(b)\,H_P(b),$$

where $\bar w(b)$ is the largest value of $w$ inside bin $b$.

This bound is sound by a short argument. TRSU already upper-bounds the value of every extension of $P$ in each sequence. Multiplying each sequence's contribution by a non-negative weight no smaller than $w(x_s)$ therefore preserves the inequality.

The index works in two phases. The offline phase builds the tree once, pruning only with the bound under the largest weight in the admissible query family. The online phase answers each query by traversing that tree and pruning with $\mathrm{UB}_w$, which costs $O(B)$ per node. Coarse bins loosen the bound and fine bins enlarge the index. That trade-off is what the experiments measure. Context that varies within a sequence, so that each event has its own context, requires per-bin remaining-utility tracking. We treat that as a second-stage extension, not part of the core claim.

Research Program

The first deliverable is the index itself. It extends HUSP-SP's array-based sequence projection with per-node context histograms. It inherits RASP's budget-driven threshold raising so that the offline tree fits a fixed RAM budget, and the online traversal reports each query's exact result set together with its timing. A UMEpi-style episode variant follows, with the same histogram replacing the static episode bound.

The second deliverable is analytic. We will characterize how bound looseness grows with bin width for monotone weight families. We will also give the condition under which the offline tree is guaranteed to contain every answer for every query in the family.

The third deliverable is an empirical test of utility-frequency divergence under context. Do the top value patterns for a regime differ materially from the globally top-value and the most frequent patterns? And are they stable when re-mined on a later period under the same regime?

Baselines

The naive reference point re-runs HUSP-SP from scratch for each query, on sequences whose event values have been multiplied by $w(x_s)$. Its output is exact, so it serves as the correctness oracle; any result set from our method that differs from it is a bug. It is also the strongest existing method. HUSP-SP is reported to be about 4x faster than HUSP-ULL and up to 1,000x faster than USpan (HUSP-SP). For episodes, the corresponding reference is UMEpi+, reported to cut BMS clickstream runtime from over 3,000 seconds to 7 seconds (UMEpi). We found no reported result on Lacuna for workloads of many context-conditioned utility queries, so there is no published number to beat on the actual task. We will establish it ourselves. Both baselines run single-threaded on the same machine and the same sequences, under the same RAM cap and value thresholds, with HUSP-SP's own pruning switches on. Beating them means a lower total time, offline build plus all queries, for a workload of $Q$ queries, at identical outputs. We will report the crossover $Q$, along with memory relative to a single HUSP-SP run.

The post-hoc filtering baseline mines once with every event priced at the family's maximum weight, then re-scores and filters the output for each query. It is the obvious way to share work. It should suffer the explosion that Targeted Mining Precise-positioning Episode Rules documents for unfocused mining, but we will measure this rather than assume it.

The tokenized-context baseline follows RASP's treatment of weather. It appends context bins as items in each sequence and mines with HUSP-SP. This tests whether representing exogenous variables as items suffices.

The key ablation keeps our offline tree but answers queries using only the family-maximum bound, dropping the per-query histogram. This isolates the contribution of context-binned bounds. A second ablation sweeps $B$.

Why not just…?

Why not just precompute context-weighted utilities and run HUSP-SP? For one query this is exactly right, and we use it as the correctness oracle. It becomes a real threat if analysts ask only a handful of questions, or if HUSP-SP is fast enough that re-running is cheap. The crossover experiment settles this directly. If our method only wins beyond hundreds of queries, or if index memory exceeds several single runs, the contribution shrinks to a niche. We will report it that way rather than reframe it.

Why not just add weather as extra items in the sequences? Items add value; they do not multiply the value of other events. A pattern found this way must contain the context token, and its value cannot reflect that the same congestion episode costs more on a stagnant day. It also inflates the alphabet the miner must search. The tokenized-context baseline measures whether this approximation recovers the oracle's top-k under weighted queries; we expect low overlap.

Why not just mine once with maximum weights and filter? With the maximum weight, every bound is as loose as the most expensive regime allows, so the candidate set approaches the low-threshold explosion that Wang et al. describe. The post-hoc filtering baseline quantifies this as candidate counts and peak memory against our per-query traversal.

Why not just use an exogenous-aware neural forecaster such as ExoST? If the goal is predicting a pollution level, ExoST is the right tool. It improves mean relative error by over 20% against models that ignore exogenous data (ExoST). We do not compete on forecasting accuracy. Our output is an exact, enumerable set of event sequences, ranked by regime-specific consequence, which a forecaster does not provide. The divergence and stability checks below test whether that set carries information an analyst could act on.

Proposed Experiments

Runtime and correctness come first. We use BMS clickstream, Retail, Kosarak10k and MSNBC, attaching a synthetic per-sequence context drawn from smooth and heavy-tailed distributions, with workloads of 1 to 1,000 weight functions drawn from monotone and indicator families. These datasets let us compare directly against the setting where HUSP-SP and UMEpi+ report their speedups. Every query's output must match the oracle exactly.

The real-context study uses three datasets. On the Madrid air-quality and traffic benchmarks used by ExoST, a sequence is one station-day of discretized traffic intensity and speed events. Event value is the following hour's NO2 level above a limit, and context is the daily traffic regime together with whatever meteorology accompanies the release. On TaxiBJ, events are grid-cell flow surges, and context is the provided temperature, weather type, wind speed and holiday indicators. The BIKE episodes provide a third setting with calendar context.

On these datasets we report three things. The first is the crossover number of queries and peak memory against the oracle. The second is overlap, measured as Jaccard similarity on top-k, between regime-conditioned, global-value and frequent pattern sets. The third, and decisive, is temporal stability. We mine a regime's top-k on the first portion of the timeline and measure what fraction remain above threshold, under the same regime, on the held-out remainder, compared with the same statistic for global top-value patterns.

The idea fails if either of two things happens. One is that the histogram bound gives under 2x total speedup over re-running HUSP-SP at 100 queries with $B\le 32$. The other is that regime-conditioned patterns are no more stable within their regime than global ones. That second outcome would mean conditioning on exogenous context finds noise rather than structure.