Engineering Wavelet Tree Implementations for Compressed Web Graph Representations

Summary form only given: We study compressed representations of web graphs. Among previous work, the solution by Hernandez and Navarro [1] supports more queries than alternative approaches, including in-neighbour queries, out-neighbour queries and a set of 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, and more engineering work is needed for the data generated from web graphs.Our strategy is to use different implementations to encode bit vectors at different levels of the wavelet trees constructed for dense subgraphs, based on the observation that bit vectors at top levels are more compressible than the rest. These implementations are considered: RRR, practical implementations [2] of the structure by Raman et al. [3]; RLEG, a bit vector structure based on run-length and Elias gamma codes [4]; and Plain, an uncompressed representation with low overheads [5]. Two specific approaches are used to combine them: The first approach encodes bit vectors using RRR starting from the root of a wavelet tree, until a level for which Plain uses less space is reached. Then, starting from this level downwards, Plain is used to encode bit vectors. The second approach uses RLEG, RRR and Plain in a similar top-down fashion, and different tradeoffs can be achieved by using different block sizes for RLEG.We implemented these approaches with code from [1, 4] and the compact structures library libcds (http://recoded.cl/), to encode data sets from the WebGraph Framework project (http://webgraph.di.unimi.it/). We obtained a rich set of time/space tradeoffs that can not be achieved using a single bit vector structure for all levels. The following three tradeoffs are particularly interesting: A new encoding scheme that decreases the space cost of Hernandez and Navarro's structure by 9% to 19% (more than 13% for all but one graph), while only doubling query time; a new scheme that decreases the space cost by 4% to 12% (10% or more for most graphs), with roughly the same query time; and a new scheme that decreases the space cost and the query time by about 2% and 1%-9% (5% or more for most graphs), respectively.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.