# Characterizing Situations of Dock Overload in Bicycle Sharing Stations
## 3 Methodology
### Mining Occupancy Monitoring Patterns
#### 3.2.3 The OMP-Miner Algorithm  
Algorithms 1 and 2 report the pseudo-code of the algorithm we devised to extract OMPs. It consists of the following three main phases:Phase 1: Creation of a compact in-memory representation of the occupancy level transactional dataset (Algorithm 1, line 1). * Phase 2: Mining of all the critical and normal o-itemsets including nearby stations according to the spatial constraint _maxdist_ (Algorithm 1, line 2). * Phase 3: Generation of the OMPs on top of the mined o-itemsets and computation of their criticality and intermittence levels (Algorithm 1, lines 3-7). To implement the o-itemset mining phase of the proposed methodology, we exploited an itemset-based approach relying on the state of the art FP-growth algorithm [29]. The main advantage of the FP-growth based approach is the selective generation of the candidate o-itemsets, which prevents the time- and memory-consuming candidate generation phase adopted by the a priori strategy [30]. ```
0:\(\mathcal{T}\): occupancy level dataset in transactional format
0:maxdist: maximum distance between two stations in the same OMP
0:\(\mathcal{TP}\): set of time periods \(TP_{1},\ldots,TP_{q}\)
0:\(\mathcal{P}\): the set of OMPs for each time period in \(\mathcal{TP}\)
1:\(\mathcal{F}\)PTree\(\leftarrow\) FP-tree(\(\mathcal{T}\)) { Create the initial FP-tree from \(\mathcal{T}\) }
2:\(\mathcal{F}\)\(\leftarrow\) O-ITESETMining(\(FPTree\), _maxdist_, \(\varnothing\)) { Recursive projection-based o-itemset mining function} { Generate OMPs on top of the mined o-itemsets in \(\mathcal{F}\)}
3:\(\mathcal{F}_{normal}\): normal o-itemsets \(I_{N}\) in \(\mathcal{F}\)
4:\(\mathcal{F}_{critical}\): critical o-itemsets \(I_{C}\) in \(\mathcal{F}\)
5:\(\mathcal{H}\): Hash map with keys \(\langle I_{N},TP_{k}\rangle\) storing the criticality values of each normal o-itemset \(I_{N}\in\mathcal{F}_{normal}\) for each period \(TP_{k}\)
6:card_value[]: vector storing in the \(k\)-th element the number of transactions in \(\mathcal{T}\) associated with period \(TP_{k}\)
7:\(\mathcal{P}\) = ComputeOMPintermittence(\(\mathcal{F}_{critical}\),\(\mathcal{H}\),card_value)
8:return\(\mathcal{P}\)
```  
**Algorithm 1** OMP-Miner(\(\mathcal{T}\), _maxdist_, \(\mathcal{TP}\))  
Phase 1 entails storing the measurements reported in the transactional representation \(\mathcal{T}\) of the original dataset into a compact tree-based structure. To accomplish this task, we exploit the prefix-tree data structure adopted by FP-Growth, namely the FP-tree, to store the transactional dataset \(\mathcal{T}\). In our context, each node of the tree contains an o-item together with the frequency of the o-item in the path. A transaction in \(\mathcal{T}\) is stored in the FP-tree as a path connecting o-items corresponding to the same time period. Figure 2 reports the FP-tree that represents the transactional dataset \(\mathcal{T}\) in Table 2. For the sake of compactness and readability Overloaded and Normal conditions in o-items are denoted as \(O\) and \(N\), respectively. The key advantage of scanning the FP-tree index instead of the original dataset in the o-itemset mining process is that in the FP-tree multiple dataset transactions containing the same o-items are stored in the same path. For example, the FP-tree path \([\langle s_{1},O,TP_{1}\rangle,\langle s_{2},O,TP_{1}\rangle,\langle s_{3},O, TP_{1}\rangle]\) represents transaction with TID equal to TID\({}_{1}\), but subpath \([\langle s_{1},O,TP_{1}\rangle,\langle s_{2},O,TP_{1}\rangle]\) represents a common part in transactions with TIDs equal to TID\({}_{1}\) and TID\({}_{2}\). The FP-tree is built as follows (Algorithm 1, line 1). For each o-item in \(\mathcal{T}\), its frequency is computed and stored in a data structure called Header Table. O-items are ordered in the Header Table by decreasing value of their frequency, and they are linked to the FP-tree nodes including them. For the sake of compactness, in Figure 2 only a portion of the whole Header Table is shown.