Fast and Compact Web Graph Representations

The Project

This projects deals with space efficient representations for Web graphs.

Web Graphs

A Web graph corresponds to the graph obtained by considering pages in the Web as nodes and links among these pages as directed edges. For example, consider the following pages:

• Page A: points to pages C, D and F.
• Page B: points to pages A, D and E.
• Page C: points to pages A, D and E.
• Page D: points to pages B, C and F.
• Page E: points to pages A, B and C.
• Page F: points to page B.

The resulting graph for this set would be:

Compressed Data Structures

A compressed data structure aims at representing some data in compressed form while supporting queries over the data without decompressing it all. In the case of Web graphs, we are interested in representing the graphs in little space while supporting fast navigation.