论文标题
用双重排序方案压缩两分图
Compressing bipartite graphs with a dual reordering scheme
论文作者
论文摘要
为了在实践中管理大量图，通常有必要求助于图形压缩，旨在减少存储和处理图时使用的内存。文献中已经提出了有效的压缩方法，尤其是对于Web图。在大多数情况下，它们与顶点重新排序的预处理步骤相结合，从而显着提高了压缩率。但是，在考虑其他类型的图表时，这些技术并不那么有效。在本文中，我们专注于两部分图的类别，并通过提出双重排序方案将顶点重新排序阶段适应其特定结构。通过将每组顶点重新排序以最大程度地减少特定分数，我们表明我们可以达到更好的压缩率。我们还建议可以进一步完善这种方法，以使节点排序更适合订购阶段的压缩阶段。
In order to manage massive graphs in practice, it is often necessary to resort to graph compression, which aims at reducing the memory used when storing and processing the graph. Efficient compression methods have been proposed in the literature, especially for web graphs. In most cases, they are combined with a vertex reordering pre-processing step which significantly improves the compression rate. However, these techniques are not as efficient when considering other kinds of graphs. In this paper, we focus on the class of bipartite graphs and adapt the vertex reordering phase to their specific structure by proposing a dual reordering scheme. By reordering each group of vertices in the purpose of minimizing a specific score, we show that we can reach better compression rates. We also suggest that this approach can be further refined to make the node orderings more adapted to the compression phase that follows the ordering phase.
