Fast and scalable minimal perfect hashing for massive key sets

Conference object, Preprint English OPEN
Limasset , Antoine; Rizk , Guillaume; Chikhi , Rayan; Peterlongo , Pierre;
(2017)
  • Publisher: HAL CCSD
  • Subject: [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM] | Algorithms | Computer Science - Data Structures and Algorithms | [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] | [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS] | and phrases Minimal Perfect Hash Functions | Data Structures | Big Data | [ INFO.INFO-BI ] Computer Science [cs]/Bioinformatics [q-bio.QM]

International audience; Minimal perfect hash functions provide space-efficient and collision-free hashing on static sets. Existing algorithms and implementations that build such functions have practical limitations on the number of input elements they can process, due t... View more
  • References (16)
    16 references, page 1 of 2

    Djamal Belazzougui, Paolo Boldi, Giuseppe Ottaviano, Rossano Venturini, and Sebastiano Vigna. Cache-oblivious peeling of random hypergraphs. In Data Compression Conference (DCC), 2014, pages 352-361. IEEE, 2014.

    Djamal Belazzougui, Fabiano C Botelho, and Martin Dietzfelbinger. Hash, displace, and compress. In European Symposium on Algorithms, pages 682-693. Springer, 2009.

    Fabiano C Botelho, Rasmus Pagh, and Nivio Ziviani. Simple and space-efficient minimal perfect hash functions. In Algorithms and Data Structures, pages 139-150. Springer, 2007.

    Fabiano C Botelho, Rasmus Pagh, and Nivio Ziviani. Practical perfect hashing in nearly optimal space. Information Systems, 38(1):108-131, 2013.

    The Computer Journal, 48(2):168-179, 2005. doi:10.1093/comjnl/bxh074.

    Jarrod A Chapman, Isaac Ho, Sirisha Sunkara, Shujun Luo, Gary P Schroth, and Daniel S Rokhsar. Meraculous: de novo genome assembly with short paired-end reads. PloS one, 6(8):e23501, 2011.

    Yupeng Chen, Bertil Schmidt, and Douglas L Maskell. A hybrid short read mapping accelerator. BMC Bioinformatics, 14(1):67, 2013. doi:10.1186/1471-2105-14-67.

    Rayan Chikhi, Antoine Limasset, and Paul Medvedev. Compacting de bruijn graphs from sequencing data quickly and in low memory. Bioinformatics, 32(12):i201-i208, 2016.

    Zbigniew J Czech, George Havas, and Bohdan S Majewski. Perfect hashing. Theoretical Computer Science, 182(1):1-143, 1997.

    Michael L Fredman and János Komlós. On the size of separating systems and families of perfect hash functions. SIAM Journal on Algebraic Discrete Methods, 5(1):61-68, 1984.

  • Related Research Results (2)
  • Related Organizations (1)
  • Metrics
Share - Bookmark