mining.alpha: the Alpha miner enumerates all 2ⁿ activity subsets #37

Open
opened 2026-10-06 13:50:55 +00:00 by ffrauenberger · 0 comments
Owner

Severity: improvement (high: the app hangs for about a minute at 14 activities in an XOR fan-out)

Where

  • app/mining_algorithms/alpha_mining.py:17, :46-60, :298-309
  • app/mining_algorithms/alpha_mining.py:66-76 — maximality step in generate_set_yl
  • app/mining_algorithms/alpha_mining.py:116 — second computation in generate_graph

Problem

subsets = itertools.chain.from_iterable(
    itertools.combinations(unique_events, r) for r in range(1, len(unique_events) + 1))
subsets_in_choice = [s for s in subsets if self.__is_set_in_choice(s, choice)]
for a, b in itertools.product(subsets_in_choice, subsets_in_choice): ...
  • Every subset of the filtered activities is generated (2ⁿ − 1): 20 activities give about 10⁶ subsets, 30 give about 10⁹.
  • The filtered list is then crossed with itself, which is quadratic in the number of independent subsets.
  • _calculate_filtered_model_state() already runs in __init__, so the cost is paid as soon as the user clicks Mine, with the default filters, before anything can be reduced.

Corrections from the review

  • The maximality step dominates for an XOR fan-out. In s → {m1…mk} → e, XL has about 2·2ᵏ pairs, and generate_set_yl compares all of them pairwise (:69-76).
  • The limits are lower than "20 activities":
    Log shape Activities XL / YL time
    XOR fan-out 12 0.4 s / 3.3 s
    XOR fan-out 14 4.8 s / 47.5 s
    Sequence 18 14.4 s
    Sequence 20 > 60 s
  • The cost is paid twice. Once in __init__ (:17), when the page loads, outside the spinner. Then again in generate_graph (:116), also when no threshold changed.

Related: #31.

Fix

  1. Generate only maximal pairs. Start from causal pairs ({a},{b}). Extend A with activities that are in # with all of A and causal to all of B, and B the same way. Keep only pairs that cannot be extended. This gives YL directly and removes the O(|XL|²) loop.
  2. Exclude self-loop activities during generation (see #15).
  3. Compute once: drop the call in __init__ (:17), or skip the call at :116 when recalculate_model_filters reports no change.
  4. Guard: the model raises a dedicated exception when there are more filtered activities than a limit (about 15 until the rewrite). The controller catches it next to InvalidNodeNameException (base_algorithm_controller.py:242) and suggests stronger filters. The model does not call Streamlit (#31).

Check

New tests/mining_algorithms/alpha_mining_test.py:

  • YL of the new code equals known results on small logs (sequence, XOR, AND, fan-out)
  • a 25-activity sequence and a 14-activity fan-out finish in well under a second

from issues/PERF-001-alpha-miner-enumerates-all-subsets.md (code analysis of commit 6bcc646, 2026-10-03), corrected by the review in verdicts-claude/PERF-001-alpha-miner-enumerates-all-subsets.md

**Severity:** improvement (high: the app hangs for about a minute at 14 activities in an XOR fan-out) ## Where - `app/mining_algorithms/alpha_mining.py:17`, `:46-60`, `:298-309` - `app/mining_algorithms/alpha_mining.py:66-76` — maximality step in `generate_set_yl` - `app/mining_algorithms/alpha_mining.py:116` — second computation in `generate_graph` ## Problem ```python subsets = itertools.chain.from_iterable( itertools.combinations(unique_events, r) for r in range(1, len(unique_events) + 1)) subsets_in_choice = [s for s in subsets if self.__is_set_in_choice(s, choice)] for a, b in itertools.product(subsets_in_choice, subsets_in_choice): ... ``` - **Every** subset of the filtered activities is generated (2ⁿ − 1): 20 activities give about 10⁶ subsets, 30 give about 10⁹. - The filtered list is then crossed with itself, which is quadratic in the number of independent subsets. - `_calculate_filtered_model_state()` already runs in `__init__`, so the cost is paid as soon as the user clicks *Mine*, with the default filters, before anything can be reduced. ### Corrections from the review - **The maximality step dominates for an XOR fan-out.** In `s → {m1…mk} → e`, XL has about 2·2ᵏ pairs, and `generate_set_yl` compares all of them pairwise (`:69-76`). - **The limits are lower than "20 activities":** | Log shape | Activities | XL / YL time | |---|---|---| | XOR fan-out | 12 | 0.4 s / 3.3 s | | XOR fan-out | 14 | 4.8 s / 47.5 s | | Sequence | 18 | 14.4 s | | Sequence | 20 | > 60 s | - **The cost is paid twice.** Once in `__init__` (`:17`), when the page loads, outside the spinner. Then again in `generate_graph` (`:116`), also when no threshold changed. Related: #31. ## Fix 1. Generate only maximal pairs. Start from causal pairs `({a},{b})`. Extend `A` with activities that are in `#` with all of `A` and causal to all of `B`, and `B` the same way. Keep only pairs that cannot be extended. This gives YL directly and removes the O(|XL|²) loop. 2. Exclude self-loop activities during generation (see #15). 3. Compute once: drop the call in `__init__` (`:17`), or skip the call at `:116` when `recalculate_model_filters` reports no change. 4. Guard: the model raises a dedicated exception when there are more filtered activities than a limit (about 15 until the rewrite). The controller catches it next to `InvalidNodeNameException` (`base_algorithm_controller.py:242`) and suggests stronger filters. The model does not call Streamlit (#31). ## Check New `tests/mining_algorithms/alpha_mining_test.py`: - YL of the new code equals known results on small logs (sequence, XOR, AND, fan-out) - a 25-activity sequence and a 14-activity fan-out finish in well under a second --- from `issues/PERF-001-alpha-miner-enumerates-all-subsets.md` (code analysis of commit 6bcc646, 2026-10-03), corrected by the review in `verdicts-claude/PERF-001-alpha-miner-enumerates-all-subsets.md`
Sign in to join this conversation.
No milestone
No assignees
1 participant
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set

Reference
ffrauenberger/ProcessIntel#37
No description provided.