Model
Pattern matching state explodes
State is O(keys × partial matches), rather than O(keys). Bounding mechanisms are all about pruning.
- Candidate events
- candidate B events seen after an A
How it behaves
One input on the horizontal axis, the others held fixed.
Data table
| Candidate B events k | Partial matches |
|---|---|
| 0 | 1 |
| 0.375 | 1.3 |
| 0.75 | 1.68 |
| 1.13 | 2.18 |
| 1.5 | 2.83 |
| 1.88 | 3.67 |
| 2.25 | 4.76 |
| 2.63 | 6.17 |
| 3 | 8 |
| 3.38 | 10.4 |
| 3.75 | 13.5 |
| 4.13 | 17.4 |
| 4.5 | 22.6 |
| 4.88 | 29.3 |
| 5.25 | 38.1 |
| 5.63 | 49.4 |
| 6 | 64 |
| 6.38 | 83 |
| 6.75 | 108 |
| 7.13 | 140 |
| 7.5 | 181 |
| 7.88 | 235 |
| 8.25 | 304 |
| 8.63 | 395 |
| 9 | 512 |
| 9.38 | 664 |
| 9.75 | 861 |
| 10.1 | 1.12K |
| 10.5 | 1.45K |
| 10.9 | 1.88K |
| 11.3 | 2.44K |
| 11.6 | 3.16K |
| 12 | 4.1K |
| 12.4 | 5.31K |
| 12.8 | 6.89K |
| 13.1 | 8.93K |
| 13.5 | 11.6K |
| 13.9 | 15K |
| 14.3 | 19.5K |
| 14.6 | 25.3K |
| 15 | 32.8K |
| 15.4 | 42.5K |
| 15.8 | 55.1K |
| 16.1 | 71.5K |
| 16.5 | 92.7K |
| 16.9 | 120K |
| 17.3 | 156K |
| 17.6 | 202K |
| 18 | 262K |
| 18.4 | 340K |
| 18.8 | 441K |
| 19.1 | 572K |
| 19.5 | 741K |
| 19.9 | 962K |
| 20.3 | 1.25M |
| 20.6 | 1.62M |
| 21 | 2.1M |
| 21.4 | 2.72M |
| 21.8 | 3.53M |
| 22.1 | 4.57M |
| 22.5 | 5.93M |
| 22.9 | 7.69M |
| 23.3 | 9.98M |
| 23.6 | 12.9M |
| 24 | 16.8M |
| 24.4 | 21.8M |
| 24.8 | 28.2M |
| 25.1 | 36.6M |
| 25.5 | 47.5M |
| 25.9 | 61.5M |
| 26.3 | 79.8M |
| 26.6 | 103M |
| 27 | 134M |
| 27.4 | 174M |
| 27.8 | 226M |
| 28.1 | 293M |
| 28.5 | 380M |
| 28.9 | 492M |
| 29.3 | 638M |
| 29.6 | 828M |
| 30 | 1.07B |
Worked examples, recomputed
Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.
Where it appears
Each mechanism states it in its own names. The general symbol each name stands for is shown with it.
- Streaming
What does it cost to remember, when the input never ends?