More Like this

1. On the optimal time/space tradeoff for hash tables

   https://doi.org/10.1145/3519935.3519969  

   Bender, Michael A. ; Farach-Colton, Martín ; Kuszmaul, John ; Kuszmaul, William ; Liu, Mingmou ( June 2022 , Proc.\ 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC))
2. Leveraging Caches to Accelerate Hash Tables and Memoization

   https://doi.org/10.1145/3352460.3358272  

   Zhang, Guowei ; Sanchez, Daniel ( October 2019 , Leveraging Caches to Accelerate Hash Tables and Memoization)
3. Towards a Ring Analogue of the Leftover Hash Lemma

   https://doi.org/10.1515/jmc-2020-0076  

   Dachman-Soled, Dana ; Gong, Huijing ; Kulkarni, Mukul ; Shahverdi, Aria ( November 2020 , Journal of Mathematical Cryptology)

   null (Ed.)

   Abstract The leftover hash lemma (LHL) is used in the analysis of various lattice-based cryptosystems, such as the Regev and Dual-Regev encryption schemes as well as their leakage-resilient counterparts. The LHL does not hold in the ring setting, when the ring is far from a field, which is typical for efficient cryptosystems. Lyubashevsky et al . (Eurocrypt ’13) proved a “regularity lemma,” which can be used instead of the LHL, but applies only for Gaussian inputs. This is in contrast to the LHL, which applies when the input is drawn from any high min-entropy distribution. Our work presents an approach for generalizing the “regularity lemma” of Lyubashevsky et al . to certain conditional distributions. We assume the input was sampled from a discrete Gaussian distribution and consider the induced distribution, given side-channel leakage on the input. We present three instantiations of our approach, proving that the regularity lemma holds for three natural conditional distributions. 

   more » « less
4. Effects of Shell Hash on Friction Angles of Surficial Seafloor Sediments near Oysters

   https://doi.org/10.1061/(ASCE)WW.1943-5460.0000716  

   Consolvo, Samuel T. ; Stark, Nina ; Castellanos, Bernardo ; Castro-Bolinaga, Celso F. ; Hall, Steven ; Massey, Grace ( September 2022 , Journal of Waterway, Port, Coastal, and Ocean Engineering)
5. Can Learned Models Replace Hash Functions?

   https://doi.org/10.14778/3570690.3570702  

   Sabek, Ibrahim ; Vaidya, Kapil ; Horn, Dominik ; Kipf, Andreas ; Mitzenmacher, Michael ; Kraska, Tim ( November 2022 , Proceedings of the VLDB Endowment)

   Hashing is a fundamental operation in database management, playing a key role in the implementation of numerous core database data structures and algorithms. Traditional hash functions aim to mimic a function that maps a key to a random value, which can result in collisions, where multiple keys are mapped to the same value. There are many well-known schemes like chaining, probing, and cuckoo hashing to handle collisions. In this work, we aim to study if using learned models instead of traditional hash functions can reduce collisions and whether such a reduction translates to improved performance, particularly for indexing and joins. We show that learned models reduce collisions in some cases, which depend on how the data is distributed. To evaluate the effectiveness of learned models as hash function, we test them with bucket chaining, linear probing, and cuckoo hash tables. We find that learned models can (1) yield a 1.4x lower probe latency, and (2) reduce the non-partitioned hash join runtime with 28% over the next best baseline for certain datasets. On the other hand, if the data distribution is not suitable, we either do not see gains or see worse performance. In summary, we find that learned models can indeed outperform hash functions, but only for certain data distributions. 

   more » « less