Compact representation of Web graphs with extended functionality

摘要: The representation of large subsets the World Wide Web in form a directed graph has been extensively used to analyze structure, behavior, and evolution those so-called graphs. However, interesting graphs are very their classical representations do not fit into main memory typical computers, whereas required algorithms perform inefficiently on secondary memory. Compressed drastically reduce space requirements while allowing efficient navigation compressed form. While most basic operation is retrieve successors node, several important require support for extended queries, such as finding predecessors checking presence link, or retrieving links between ranges nodes. Those seldom supported by representations. This paper presents k^2-tree, novel based compact tree structure that takes advantage empty areas adjacency matrix graph. only retrieves symmetric fashion, but also it particularly check specific nodes, list ranges. Compared best literature supporting successor predecessor our technique offers least usage (1-3 bits per link) fast ([email protected] neighbor retrieved) sharply outperforming others queries. general interest can be compress other kinds data structures.