# Characterizing Situations of Dock Overload in Bicycle Sharing Stations
## 3 Methodology
### Mining Occupancy Monitoring Patterns
#### 3.2.3 The OMP-Miner Algorithm
The algorithm backtracks to FP-tree represented in Figure 2 to target the extraction of the o-itemsets including the o-item which precedes item \(\langle s_{3},O,TP_{1}\rangle\) in the Header Table. Figure 2: The FP-tree representing the example transactional occupancy level dataset (Table 2). Phase 3 aims at generating OMPs by properly combining the critical and normal o-itemsets mined at Phase 2 and stored in sets \(\mathcal{F}_{critical}\) and \(\mathcal{F}_{normal}\), respectively (Algorithm 1, lines 3 and 4). For each critical o-itemset \(I_{C}\in\mathcal{F}_{critical}\), an OMP \(P\) is generated with criticality and intermittence value computed according to Equations (1) and (2), respectively. For instance, the critical o-itemset \(\{\langle s_{3},O,TP_{1}\rangle,\langle s_{2},O,TP_{1}\rangle\}\) with frequency equal to 1 and the normal o-itemset \(\{\langle s_{3},N,TP_{1}\rangle,\langle s_{2},N,TP_{1}\rangle\}\) with frequency equal to 1 are mined during Phase 2 from the running example dataset in Table 2. Those two o-itemsets are related to time period \(TP_{1}\), which is associated with four transactions in the running example dataset. Given those two o-itemsets and the number of transactions associated with \(TP_{1}\), the OMP-Miner algorithm extracts the OMP \(\{s_{3},s_{2}\}\) associated with \(TP_{1}\) with criticality equal to 1 and intermittence equal to 2. To efficiently compute the pattern intermittence value, the normal o-itemsets and their corresponding frequency values are stored in a hash map data structure. Given a critical o-itemset \(I_{C}\), the frequency of the corresponding normal o-itemset \(I_{N}\) including the same stations is returned by the hash map given the key \(\langle I_{N},TP_{k}\rangle\) (Algorithm 1, line 7). Figure 3: O-itemset mining example. ```
1:\(FPTree\), an FP-tree
2:maxdist: maximum distance between two stations in the same o-itemset
3:\(I^{*}\), the set of o-items with respect to which \(FPTree\) has been generated
4:\(\mathcal{F}\), the set of o-itemsets extending \(I^{*}\)
5:\(\mathcal{F}\leftarrow\emptyset\)
6:for all o-item \(i^{*}\)=\(\langle s_{j},o_{i}^{j},TP_{i}\rangle\) in the header table of \(FPTree\)do
7:\(I\gets I^{*}\cup\{i^{*}\}\) [Generate a new o-itemset \(I\) by joining o-itemset \(I^{*}\) and o-item \(i^{*}\) ]
8:\(\mathcal{F}\leftarrow\mathcal{F}\cup\{I\}\)
9:STATE \(CondPaths_{I}\leftarrow\) selectConditionalPaths(\(FPTree\), \(I\)) { Select \(I^{*}\)s conditional paths}
10:\(PrunedCondPaths_{I}\leftarrow\) applyConstraints(\(CondPaths_{I}\), \(I\)) [Prune o-items \(k^{*}\)=\(\langle s_{k},o_{i}^{k},TP_{i}\rangle\) such that \(\exists\langle s_{x},o_{i}^{x},TP_{i}\rangle\in I\)] distance(\(s_{k},s_{x}\))\(>\)_maxdist_ or \(o_{i}^{k}\
eq o_{i}^{x}\)
11:\(FPTree_{I}\leftarrow\)createFP-tree(\(FPTree\), \(I\)) {Build \(I^{*}\)s conditional FP-tree}
12:if\(FPTree_{I}\
eq\emptyset\)then
13:\(\mathcal{F}\leftarrow\mathcal{F}\cup\)O-ITEMSETMining(\(FPTree_{I}\), maxdist, \(I\)) { Recursive mining}
14:endif
15:endfor
16:return\(\mathcal{F}\)
```  
**Algorithm 2** O-ITEMSETMining(\(FPTree\), _maxdist_, \(I^{*}\))