Istituto di Scienza e Tecnologie dell'Informazione     
Belazzougui D., Boldi P., Ottaviano G., Venturini R., Vigna S. Cache-oblivious peeling of random hypergraphs. In: DCC 2014 - Data Compression Conference (Snowbird, Utah, USA, 26-28 March 2014). Proceedings, pp. 352 - 361. IEEE, 2014.
The computation of a peeling order in a randomly generated hypergraph is the most time- consuming step in a number of constructions, such as perfect hashing schemes, random r-SAT solvers, error-correcting codes, and approximate set encodings. While there exists a straightforward linear time algorithm, its poor I/O performance makes it impractical for hypergraphs whose size exceeds the available internal memory. We show how to reduce the computation of a peeling order to a small number of sequential scans and sorts, and analyze its I/O complexity in the cache-oblivious model. The resulting algorithm requires O(sort(n)) I/Os and O(n log n) time to peel a random hypergraph with n edges. We experimentally evaluate the performance of our implementation of this algorithm in a real- world scenario by using the construction of minimal perfect hash functions (MPHF) as our test case: our algorithm builds a MPHF of 7.6 billion keys in less than 21 hours on a single machine. The resulting data structure is both more space-efficient and faster than that obtained with the current state-of-the-art MPHF construction for large-scale key sets.
URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=6824443&queryText%3DCache-oblivious+peeling+of+random+hypergraphs
DOI: 10.1109/DCC.2014.48
Subject Perfect hash functions
Hypergraph algorithms
Cache-oblivious algorithms
G.2.2 Graph Theory
I.1.2 Algorithms

Icona documento 1) Download Document PDF
Icona documento 2) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional