7 papers
Hashing for Sampling-Based Estimation
Anders Aamand, Ioana O. Bercea, Jakob Bæk Tejs Houen +2
Hash-based sampling and estimation are common themes in computing. Using hashing for sampling gives us the coordination needed to compare samples from different sets. Hashing is al…
Locally Uniform Hashing
Ioana O. Bercea, Lorenzo Beretta, Jonas Klausen +2
Hashing is a common technique used in data processing, with a strong impact on the time and resources spent on computation. Hashing also affects the applicability of theoretical re…
A Sparse Johnson-Lindenstrauss Transform using Fast Hashing
Jakob Bæk Tejs Houen, Mikkel Thorup
The \emph{Sparse Johnson-Lindenstrauss Transform} of Kane and Nelson (SODA 2012) provides a linear dimensionality-reducing map in that pres…
Simple Set Sketching
Jakob Bæk Tejs Houen, Rasmus Pagh, Stefan Walzer
Imagine handling collisions in a hash table by storing, in each cell, the bit-wise exclusive-or of the set of keys hashing there. This appears to be a terrible idea: For keys…
Bias Reduction for Sum Estimation
Talya Eden, Jakob Bæk Tejs Houen, Shyam Narayanan +2
In classical statistics and distribution testing, it is often assumed that elements can be sampled from some distribution , and that when an element is sampled, the probabil…
Understanding the Moments of Tabulation Hashing via Chaoses
Jakob Bæk Tejs Houen, Mikkel Thorup
Simple tabulation hashing dates back to Zobrist in 1970 and is defined as follows: Each key is viewed as characters from some alphabet , we have fully random hash functi…
Daisy Bloom Filters
Ioana O. Bercea, Jakob Bæk Tejs Houen, Rasmus Pagh
A filter is a widely used data structure for storing an approximation of a given set of elements from some universe (a countable set).It represents a superset $S'\supseteq…