  Cohesive subgraph mining in bipartite graphs becomes a popular research topic
recently. An important structure k-bitruss is the maximal cohesive subgraph
where each edge is contained in at least k butterflies (i.e., (2,
2)-bicliques). In this paper, we study the bitruss decomposition problem which
aims to find all the k-bitrusses for k >= 0. The existing bottom-up techniques
need to iteratively peel the edges with the lowest butterfly support. In this
peeling process, these techniques are time-consuming to enumerate all the
supporting butterflies for each edge. To relax this issue, we first propose a
novel online index -- the BE-Index which compresses butterflies into k-blooms
(i.e., (2, k)-bicliques). Based on the BE-Index, the new bitruss decomposition
algorithm BiT-BU is proposed, along with two batch-based optimizations, to
accomplish the butterfly enumeration of the peeling process in an efficient
way. Furthermore, the BiT-PC algorithm is devised which is more efficient
against handling the edges with high butterfly supports. We theoretically show
that our new algorithms significantly reduce the time complexities of the
existing algorithms. Also, we conduct extensive experiments on real datasets
and the result demonstrates that our new techniques can speed up the
state-of-the-art techniques by up to two orders of magnitude.
