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. |

Abstract (English) |
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 |

1) Download Document PDF |

2) Download Document PDF |

Open access Restricted Private