HackerPapers

arXiv:1202.4961cs.DB

Strongly universal string hashing is fast

Owen Kaser, Daniel Lemire

Abstract

We present fast strongly universal string hashing families: they can process data at a rate of 0.2 CPU cycle per byte. Maybe surprisingly, we find that these families---though they require a large buffer of random numbers---are often faster than popular hash functions with weaker theoretical guarantees. Moreover, conventional wisdom is that hash functions with fewer multiplications are faster. Yet we find that they may fail to be faster due to operation pipelining. We present experimental results on several processors including low-powered processors. Our tests include hash functions designed for processors with the Carry-Less Multiplication (CLMUL) instruction set. We also prove, using accessible proofs, the strong universality of our families.

arXiv comments
Software is available at http://code.google.com/p/variablelengthstringhashing/ and https://github.com/lemire/StronglyUniversalStringHashing
Journal reference
Computer Journal (2014) 57 (11): 1624-1638
DOI
doi:10.1093/comjnl/bxt070
Subjects
cs.DBDatabases cs.DSData Structures and Algorithms

On Hacker News

Linked by 2 identifiable commenters in 2 comments across 2 threads, from Feb 2012 to Apr 2015.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. An simple AES-based random number generator 1 comment

    • Turns out that only clmul is needed to produce fast hash functions, even strongly universal ones. http://arxiv.org/abs/1202.4961

      scaramangaView on HNParent context

  2. Fast strongly universal hashing algorithms over variable-length strings 1 comment

    • The paper is available -> http://arxiv.org/abs/1202.4961 """We present fast strongly universal string hashing families: they can process data at a rate of 0.2 CPU cycle per byte. Maybe surprisingly, we find that these families---though they requires a large buffer of random…

      adulauView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.