Miao, Chen2016-04-292016-04-292016-04-29http://hdl.handle.net/10222/71591The compressed web graph and social networks structures proposed by Hernandez and Navarro (Compressed representations for web and social graphs. Knowl. Inf. Syst. 40(2): 279-313 (2014)) support more queries than alternative approaches, including in-neighbor, out-neighbour, and mining queries. Their main strategy is to extract dense subgraphs from the given graph, and encode them using succinct data structures such as wavelet trees. Previous experimental studies on wavelet trees, however, test performance using textual data, which are drastically different from the data generated from web graphs. We thus engineer wavelet tree implementations for compressed web graph and social network structures. In particular, we propose a new wavelet tree encoding approach called combined encoding which can provide better time/space tradeoffs than previous approaches when used in Hernandez and Navarroa's framework to represent web graphs.enThesis