基于BV算法的Web Graph压缩问题的研究

发布时间：2018-04-29 18:02

本文选题：网络图压缩 + 幂律分布　；参考：《西安电子科技大学》2014年硕士论文

【摘要】：互联网中的网页及其超链接可建模为一个庞大的有向图，称为Web Graph。Web Graph的分析研究可应用于网页排名、检测网络垃圾信息、发现社区和镜像站点等。然而，这项研究受阻于需要把巨大的图存储到外存上，从而影响有效地随机访问结点。因此，把Web Graph压缩存储到内存的研究具有十分重要的意义。 Web Graph具有本地性和相似性，且服从幂律分布。BV算法采用Zeta-k编码，是最有效的Web Graph压缩方案之一。基于BV算法，本文提出了两种改进的Web Graph压缩算法：近似最优引用序列的压缩算法和合并最优引用序列的压缩算法。二者均采用引用压缩，其关键是选取最优引用序列。不同的是，前者不再局限于滑动窗口内部，可以实现沿着结点的引用链回溯搜索近似全局的最优引用序列；后者则是通过合并固定数目的结点生成块结点，用来作为块内结点的最优引用序列。本文选用五组测试数据分别对三种压缩算法进行测试。主要的测试内容包括两个基本点：存储每条链接所用的比特位和随机访问每个结点所用的时间。最后，通过比较和分析三种算法的实验结果，，表明改进后的方法提高了压缩效果，而且缩短了结点引用链的长度，提高了随机访问结点的效率。
[Abstract]:The web pages and their hyperlinks in the Internet can be modeled as a huge directed graph. The analysis and research called Web Graph.Web Graph can be applied to the ranking of web pages, the detection of web spam, the discovery of community and mirror sites, and so on. However, this study is hampered by the need to store large graphs on external memory, thus affecting efficient random access nodes. Therefore, it is of great significance to compress Web Graph into memory. Web Graph is one of the most effective Web Graph compression schemes, because it is local and similar, and Zeta-k coding is used in the following power law distribution. BV algorithm. Based on BV algorithm, this paper proposes two improved Web Graph compression algorithms: approximate optimal reference sequence compression algorithm and merging optimal reference sequence compression algorithm. Both of them adopt reference compression, and the key is to select the optimal reference sequence. The difference is that the former is no longer confined to the sliding window and can be traced back along the node's reference chain to search the approximate global optimal reference sequence, while the latter is to generate block nodes by merging a fixed number of nodes. Used as an optimal sequence of references within a block. In this paper, five groups of test data are selected to test the three compression algorithms. The main tests include two basic points: the bits used to store each link and the time taken to randomly access each node. Finally, by comparing and analyzing the experimental results of the three algorithms, it is shown that the improved method improves the compression effect, shortens the length of the node reference chain, and improves the efficiency of random access nodes.
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.092

【共引文献】