# Cohesive Subgraph Identification in Weighted Bipartite Graphs
## 4 Index-Based Solution
### Time-Improved Method
To shrink the index space without sacrificing much efficiency, we introduce three novel index structures, i.e., \((1)\) RowIndex: by utilizing the nested property of \((k,\omega)\)-core, we compress each _row_ of the index; \((2)\) OptionIndex: by comparing the shrink size of compression in _row_ and _column_, we select the better compression direction; \((3)\) UnionIndex: by considering both _row_ and _column_ compression, we conduct the union operations on cells of the index. In addition, the corresponding query algorithms are presented. #### 4.3.1 Rowindex

According to the nested property in Lemma 1, we know that \(C_{k,\omega}\) is always a subset of \(C_{k,\omega-1}\). Thus, we resort to the RowIndex by compressing _row_ of the index, since it can avoid storing a single node many times. Given a specific \(k\), we say that all the \((k,*)\)-cells are in the \(k\)-th row, where the symbol \"\(*\)\" represents any possible value of \(\omega\). The main difference between RowIndex and the index structure proposed above is that we only store each node \(u\in U\) in the \((k,\omega_{max,k}(u))\)-cell, instead of putting it into \((k,\omega_{i})\)-cells where \(0\leq\omega_{i}\leq\omega_{max,k}(u)\). Thus, we only need to deposit each node at most once in each _row_ of the index, which can save space from the redundant copies of nodes. Meanwhile, we also record the shrink direction (i.e., \"\(\rightarrow\)\") in the _shrink_, which is a direction table. As the procedure of RowIndex is easy to understand, we omit its pseudo-codes in the context. RowIndex Query Algorithm: Given query parameters \(k\) and \(\omega\), we first locate the \((k,\omega)\)-cell. Then, we collect all the nodes contained in the \((k,\omega_{i})\)-cell where \(\omega\leq\omega_{i}\leq\omega_{max}\), and output them together as the resulting \((k,\omega)\)-core. As shown in Table 1, for \(k=1\), the \((1,1)\)-cell containing nodes \(\{u_{1},u_{2},u_{3},u_{4},v_{1},v_{2},\)\(v_{3},v_{4},v_{5}\}\) can be compressed to the \((1,3)\)-cell and the \((1,5)\)-cell. That is, nodes \(u_{4},v_{4}\) only need to be saved in the \((1,3)\)-cell and nodes \(u_{1},u_{2},u_{3},v_{2},v_{3}\) only need to be stored in the \((1,5)\)-cell. Thus, only the remaining nodes \(v_{1}\) and \(v_{5}\) are stored in the \((1,1)\)-cell. Obviously, RowIndex saves a lot of space. When querying the \((2,3)\)-core, we first locate the \((2,3)\)-cell and output nodes in the \((2,3)\)-cell and \((2,4)\)-cell together. Thus, we have \(C_{2,3}=\{u_{1},u_{2},v_{2},v_{3}\}\). #### 4.3.2 OptionIndex

As discussed above, RowIndex utilizes the nested property to reduce the redundant storage for each node in each _row_ of the index. Similarly, we can construct ColumnIndex to compress each _column_ of the index in the same manner, which also enjoys the same space cost. Naturally, it is possible that certain cells may compress more storage by ColumnIndex than RowIndex. That is, _column_ compression may contribute more to space saving for some cells. Motivated by this, we devised the OptionIndex structure, which is constructed by traversing all cells one by one. Specifically, when visiting a specific cell, we first compared the compression size of different compression directions, i.e., RowIndex or ColumnIndex, and then selected the better one to reduce more space. For example, in Table 1, the compression size is 7 if we use RowIndex to shrink the \((1,1)\)-cell to the \((1,2)\)-cell with shrink direction \"\(\rightarrow\)\". Additionally, the compression size is 8 if we use ColumnIndex to shrink the \((1,1)\)-cell to the \((2,1)\)-cell with shrink direction \"\(\downarrow\)\". Since ColumnIndex shrinks more than the RowIndex for the \((1,1)\)-cell, we chose ColumnIndex and shrank \((1,1)\)-cell to the \((2,1)\)-cell. Similarly, we chose RowIndex for the \((1,4)\)-cell, as RowIndex saves a space of five nodes while ColumnIndex saves four. The details of the construction procedure for OptionIndex are shown in Algorithm 3.